Bitwise AND of Numbers Range
Problem
left ≤ right, compute
left & (left+1) & … & right — the bitwise AND of
every integer in the closed range. The range can contain about two billion numbers,
so walking it one by one is not an option.left = 5, right = 7Output4left = 0, right = 0Output0left = 1, right = 2147483647Output00 ≤ left ≤ right ≤ 231 − 1
Try it yourself
class Solution {
public int rangeBitwiseAnd(int left, int right) {
}
}
left to right flips every bit below
the highest position where they differ, so those bits all become 0. The answer is the
common binary prefix of left and right, padded with
zeros.Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.
Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.
Open the Bit Manipulation guide →Approaches
Brute ForceAND Every Number
O(right − left)Space O(1)Start from left and AND in each following number. Once the
result hits 0 nothing can turn a bit back on, so stop early. Use a
long counter so right = 231−1 doesn’t
overflow the loop.
public int rangeBitwiseAnd(int left, int right) { int result = left; // long counter: x++ past Integer.MAX_VALUE would overflow for (long x = (long) left + 1; x <= right && result != 0; x++) { result &= (int) x; } return result; }
Fine for tiny ranges; up to ~2·109 steps when the result stays non-zero.
BetterDecide Each Bit Independently
O(log right)Space O(1)Bit b runs in blocks: 2b zeros, then 2b
ones. It survives the AND only if the whole range sits inside one block of ones:
both ends have the bit set and right − left <
2b (a longer range must touch a zero).
public int rangeBitwiseAnd(int left, int right) { long span = (long) right - left; int result = 0; for (int b = 0; b < 31; b++) { boolean leftHas = ((left >> b) & 1) == 1; boolean rightHas = ((right >> b) & 1) == 1; // whole range inside one run of ones for bit b if (leftHas && rightHas && span < (1L << b)) result |= 1 << b; } return result; }
Constant work per bit, but always inspects all 31 bits and needs a proof.
OptimalStrip Low Bits of right (Common Prefix)
O(log right)Space O(1)While right > left, right &= right − 1
clears its lowest set bit. Each cleared bit belongs to the part below the common
prefix, so when right drops to ≤ left only the shared
prefix remains — exactly the answer.
public int rangeBitwiseAnd(int left, int right) { while (right > left) { right &= right - 1; // drop the lowest set bit } return right; }
Dry runleft = 5, right = 7
- start1101rleft=1001, right=1101
- step 11100right=1100 (12) > 9
- step 21000right=1000 (8) ≤ 9
- end1000answer = 8
Three lines, stops as soon as the prefix is reached.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | AND Every Number | O(right − left) | O(1) |
| Better | Decide Each Bit Independently | O(log right) | O(1) |
| Optimal | Strip Low Bits of right (Common Prefix) | O(log right) | O(1) |
- Looping with an
intcounter up toInteger.MAX_VALUE— infinite loop on overflow. - Assuming the answer is
left & right— wrong for 5..7 (gives 5, not 4). - Iterating the range without an early exit — billions of steps.
- Write 5, 6, 7 in binary and let the interviewer see the low bits flip.
- State the claim: answer = common prefix of left and right.
- Mention both prefix extractions: shifting and
n & (n − 1).