Bitwise AND of Numbers Range
Problem
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
left = 5, right = 74def range_bitwise_and(left, right):
while right > left:
right &= right - 1
return rightfunction rangeBitwiseAnd(left, right) {
while (right > left) right &= right - 1;
return right;
}class Solution {
public int rangeBitwiseAnd(int left, int right) {
while (right > left) right &= right - 1;
return right;
}
}int rangeBitwiseAnd(int left, int right) {
while (right > left) right &= right - 1;
return right;
}Explanation
ANDing every number from left to right looks expensive, but there's a neat insight: a bit survives in the AND only if it is 1 in every number of the range. The answer is simply the common high-bit prefix that left and right share, with all the lower bits zeroed.
Why? Any bit position that changes somewhere inside the range must be 0 in at least one number there, so ANDing kills it. Only the leading bits that left and right agree on stay fixed for the whole range.
The code finds that prefix cheaply using right &= right - 1, a classic trick that clears the lowest set bit of right. We repeat this until right drops to or below left; at that point the differing low bits have all been stripped away, leaving exactly the shared prefix.
Example: left = 5 (101), right = 7 (111). Clearing the low bit of 7 gives 6 (110), still > 5; clearing again gives 4 (100), now ≤ 5. The loop stops and the answer is 4, the common prefix 100.