#201 Bitwise AND of Numbers Range
the problem
In plain words
Given two integers left ≤ right, return the bitwise AND of every number from left to right, both ends included.
in left = 5, right = 7
out 4
101 & 110 & 111 = 100.
in left = 0, right = 0
out 0
in left = 1, right = 2147483647
out 0
- 0 ≤ left ≤ right ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBit tricks (shift, mask, lowest set bit)
Counting from left up to right flips every bit below the highest bit where left and right differ, so each of those bits is 0 in some number of the range. The answer is the common binary prefix of left and right, followed by zeros.
solutions
From brute force to optimal
Start with left and AND in each next number, stopping early once the result is 0.
- result = left.
- For x from left + 1 to right (as a long, so x++ can't overflow): result &= x; stop if result == 0.
- Return result.
Up to about 2·10⁹ steps when the answer isn't 0 (for example 2³⁰..2³¹ − 1).
One accumulator.
class Solution { public int rangeBitwiseAnd(int left, int right) { int result = left; for (long x = left + 1L; x <= right && result != 0; x++) { // long: x++ past MAX_VALUE never wraps result &= (int) x; } return result; }}Shift left and right right together until they're equal — that's the shared prefix. Shift it back into place.
- shifts = 0.
- While left ≠ right: left >>= 1; right >>= 1; shifts++.
- Return left << shifts.
At most 31 shifts for a 31-bit non-negative int.
Three ints.
class Solution { public int rangeBitwiseAnd(int left, int right) { int shifts = 0; while (left != right) { // they still differ somewhere left >>= 1; // drop the lowest bit of both right >>= 1; shifts++; } return left << shifts; // the shared prefix, zeros below it }}Dry run
Kernighan's step: while right > left, right &= right − 1. What's left of right is the common prefix.
- While left < right: right &= right − 1.
- Return right.
Each step removes one 1-bit of right: at most 31 steps.
Nothing stored.
class Solution { public int rangeBitwiseAnd(int left, int right) { while (left < right) { right &= right - 1; // erase right's lowest 1-bit until it is no bigger than left } return right; }}in the room
How to say it in the interview
talk track
- Do 5..7 on paper: 101, 110, 111 → 100. The low bits that change die.
- "Every bit below the first difference between left and right flips somewhere in the range, so it's 0 in the AND. The answer is their common prefix."
- Code it: shift both right until equal, count the shifts, shift back. Mention
right &= right − 1as a second way.
traps
for (int x = left; x <= right; x++)with right = Integer.MAX_VALUE: x++ wraps to a negative number and the loop never ends.- Returning
left & right: 5 & 7 = 5, but 6 is in between and clears bit 0 → the answer is 4.
what they ask next
Follow-ups
Bitwise OR of the same range?
The mirror image: the common prefix, followed by all 1s below the first differing bit.
Why does right &= right − 1 work?
Each step drops right's lowest 1-bit and moves right down. Once right ≤ left, the bits still standing are the ones every number in the range shares.
before you submit
Edge cases to test
- left == right → that number itself.
- Crossing a power of two (7..8) → 0.
- right = Integer.MAX_VALUE: an
intloop variable overflows. And 2³⁰..2³¹ − 1 gives 2³⁰, so the AND never reaches 0 early.
practise next
Similar problems
- #191Number of 1 BitsEasyin Bits
- #231Power of TwoEasyin Bits
- #421Maximum XOR of Two Numbers in an ArrayMediumin Tries