Algorithm
Problem Name: 201. Bitwise AND of Numbers Range
Problem Link: https://leetcode.com/problems/bitwise-and-of-numbers-range/
Given two integers left and right that represent the range [left, right], return the bitwise
AND of all numbers in this range, inclusive.
Example 1:
Input: left = 5, right = 7 Output: 4
Example 2:
Input: left = 0, right = 0 Output: 0
Example 3:
Input: left = 1, right = 2147483647 Output: 0
Constraints:
0 <= left <= right <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
int rangeBitwiseAnd_1(int m, int n) {
unsigned ans = m;
unsigned k;
unsigned one_index = 0; /* first one's index */
unsigned zero_index = 0; /* first zero after the first one */
while (one_index < 31) {
while (one_index < 31 && (ans & (1 << one_index)) == 0){
one_index ++;
}
zero_index = one_index;
while (zero_index < 32 && ans & (1 << zero_index)) {
zero_index ++;
}
if (zero_index > one_index) {
/* nearest number to make first one to zero */
k = (ans | (1 << zero_index)) >> zero_index;
k = k << zero_index;
if (k > n) return ans; /* rest numbers are useless */
ans &= k;
}
if (ans == 0) return 0; /* it's pointless to continue looping */
one_index ++;
}
return ans;
}
int rangeBitwiseAnd(int m, int n) {
int k = 30;
unsigned ans = m & n;
/* check kth bit, if they are different, set remain bits to zero */
while (k > 0 && (m & (1 << k)) == (n & (1 << k))){
k--;
}
/* there is no need to check 0th bit, we already do m AND n*/
ans >>= k;
ans <<= k;
return ans;
}
int main() {
/* should be 0 */
printf("%d\n", rangeBitwiseAnd(2, 4));
/* should be 2147483644 */
printf("%d\n", rangeBitwiseAnd(2147483645, 2147483647));
/* should be 2147483647 */
printf("%d\n", rangeBitwiseAnd(2147483647, 2147483647));
/* should be 0 */
printf("%d\n", rangeBitwiseAnd(700000000, 2147483641));
/* should be 0 */
printf("%d\n", rangeBitwiseAnd(3, 4));
return 0;
}
Input
left = 5, right = 7
Output
4
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int rangeBitwiseAnd(int left, int right) {
while (right > left) {
right = right & (right - 1);
}
return left & right;
}
}
Input
left = 5, right = 7
Output
4
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const rangeBitwiseAnd = function(m, n) {
while(mInput
left = 0, right = 0
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def rangeBitwiseAnd(self, m, n):
i = 0
while m != n:
m >>= 1
n >>= 1
i += 1
return m << i
Input
left = 0, right = 0
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0201_BitwiseANDOfNumbersRange
{
public int RangeBitwiseAnd(int m, int n)
{
while (m < n)
n = n & (n - 1);
return m & n;
}
}
}
Input
left = 1, right = 2147483647