
Description
The problem is to find the bitwise AND of all numbers in a given range \([left, right]\). The bitwise AND operation is a binary operation that takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, which results in a new binary number.
Intuition
The key observation is that the bitwise AND of a range of numbers is significantly affected by the common prefix in the binary representation of the numbers in that range. If there are differing bits at any position, the result of the AND operation will zero out those positions and all positions to the right.
Approach
- Initialize a
shift
variable to 0. This will keep track of how many bits we need to shift to the right. - While
left
is not equal toright
, right shift bothleft
andright
by 1, and increment theshift
counter. - The above loop helps us to identify the common prefix of the binary representations of
left
andright
. - Once we have the common prefix, left shift
left
byshift
to restore it to its original bit length, but now with all differing bits zeroed out. - Return the result.
Complexity
Time Complexity:
(O(\log(\text{right}))) - In the worst case, we will shift the bits until left
becomes equal to right
, which is approximately the logarithm of right
.
Space Complexity:
(O(1)) - We are using a constant amount of extra space.
Code
C++
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left != right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
};
Python
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left != right:
left >>= 1
right >>= 1
shift += 1
return left << shift
Java
class Solution {
public int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left != right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
}
JavaScript
var rangeBitwiseAnd = function (left, right)
{
var shift = 0;
for (; left != right; left >>= 1, right >>= 1, shift++) { }
return left << shift;
};