Bitwise AND of Numbers Range (LeetCode 201)
You get two integers, left and right, with left <= right. Take every integer from left up to right, including both ends. Combine all of them with the bitwise AND operator. Bitwise AND compares numbers bit by bit and keeps a bit only when every number has a 1 in that place.
Return that single result.
Worked Examples
left = 5, right = 745 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.left = 0, right = 000, so the AND is 0.left = 1, right = 214748364701 and 2. They have no 1 bit in common, so the AND of the whole range is 0.⚖️Formal Constraints & Bounds
0 <= left <= right <= 231 - 1
Core Insight
Counting up from left to right passes the number prefix followed by 0111...1 and then the number prefix followed by 1000...0. These two numbers have no 1 bit in common below the prefix, so the AND clears every lower bit. The answer is the shared prefix followed by zeros: shift both ends right until they are equal, count the shifts, and shift the prefix back left by that count.
Real-World Scenario & Production Applications
In network routing, the addresses of one subnet share their leading bits. The AND of all addresses in an aligned subnet is its network address: the shared leading bits followed by zeros.
Step-by-Step Execution Trace Table
Trace of Example 1: left = 5, right = 7, shift = 0.
| Step | left | right | left != right | shift |
|---|---|---|---|---|
| start | 101 (5) | 111 (7) | yes | 0 |
| after round 1 | 10 (2) | 11 (3) | yes | 1 |
| after round 2 | 1 (1) | 1 (1) | no, stop | 2 |
The ends are equal after two rounds, so the shared prefix is 1. The function returns left << shift = 1 << 2 = 4.
| 1 | shift = 0 |
| 2 | while left != right: |
| 3 | left >>= 1 |
| 4 | right >>= 1 |
| 5 | shift += 1 |
| 6 | return left << shift |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Write left and right in binary. Counting up from left to right changes the low bits many times, but the high bits that the two ends share never change. Any bit below the highest place where the ends differ is 0 in at least one number of the range, so the AND clears it. The answer is the shared prefix, followed by zeros.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number with shifts and masks. Here two numbers are shifted together. The loop while left != right removes the lowest bit of both ends until they are equal, and shift counts the removed bits. The last line, left << shift, shifts the equal value back.
🔑 The Key Idea in the Code
After the loop, left holds only the shared prefix. The prefix must go back to its original place, so the answer is left << shift. Returning left alone gives a number that is 2 ** shift times too small.
Returning
leftwithout shifting it back: after the loop,leftholds only the shared prefix.return leftgives1forleft = 5andright = 7, where the answer isleft << shift = 4.Returning
left & rightof the two ends: a number between the ends can have a 0 where both ends have a 1. For5and7, the number6clears bit 0, so the answer is4, not5.Shifting only
rightin the loop: the loop ends whenleftequalsright. Shifting onlyrightmoves it toward 0 whileleftstays, so the loop never ends whenleftis larger than 0.Looping over every number of the range: the range can hold about 2 billion numbers, but the shift loop runs at most 31 times.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The bitwise AND of all numbers in the range" with right up to 231 - 1: the range can hold about 2 billion numbers, so a loop over the range is too slow, and the answer must come from the two ends alone.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends. The loop stops when they are equal, so left is then the shared prefix, and left << shift restores its place.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Shared Prefix. Counting up from left to right changes every bit below the highest place where the two ends differ, so the AND clears all of those bits. Only the binary prefix that the two ends share survives. I keep a counter, shift, at zero. While left is not equal to right, I shift both right by one and add one to shift. When they are equal, they hold exactly the shared prefix. The trap is the last line: left is only the prefix, so I return left shifted back left by shift, not left itself. For left 5 and right 7 the loop ends with left 1 and shift 2, and the answer is 4. Each round removes one bit from both ends, so the loop runs at most 31 times. That is O of log right time and O of 1 space.
Complexity & Mathematical Proof
O(log right)
Look at the loop. Each round shifts both ends right by one place, so right loses one bit per round. When right has no bits left, both ends are 0 and equal. right has at most 31 bits, so the loop runs at most 31 times. The number of rounds grows with the number of bits of right, which is log right, so time is O(log right).
O(1)
The code keeps three variables, left, right and shift, whatever the size of the range. There is no table and no recursion, so space is O(1).
Derivation Progression
right has at most 31 bits and loses one per round, so at most 31 rounds run.
3 = O(1)
Two shifts and one addition.
Rounds times a constant amount of work.
Variable Definitions
The larger end of the range, at most 2^31 - 1
How many low bits have been removed from both ends
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables left, right and shift
O(1): one integer
Boundary Best / Worst Cases
: the ends are already equal, so the loop does not run.
.
: 31 rounds, for example left = 1 and right = 2147483647.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "bitwise AND of all numbers in this range", a range that can reach . Looping over the range is too slow, so the answer must be read from the two ends. Any bit that changes inside the range is cleared by the AND, so only the binary prefix that the ends share can remain.
, so the range can hold about 2 billion numbers. A loop with a running AND is . The shift loop runs at most 31 times, so it is , and it uses only three variables.
Returning left without << shift gives the prefix without its original place: left = 5, right = 7 returns 1 instead of 4. Returning left & right of the two ends keeps bits that a number inside the range clears: it returns 5 for the same input. In a fixed-width language, left << shift stays below , because it is at most the original left, so it does not overflow.
Bitwise AND of Numbers Range (LeetCode 201)
You get two integers, left and right, with left <= right. Take every integer from left up to right, including both ends. Combine all of them with the bitwise AND operator. Bitwise AND compares numbers bit by bit and keeps a bit only when every number has a 1 in that place.
Return that single result.
Worked Examples
left = 5, right = 745 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.left = 0, right = 000, so the AND is 0.left = 1, right = 214748364701 and 2. They have no 1 bit in common, so the AND of the whole range is 0.⚖️Formal Constraints & Bounds
0 <= left <= right <= 231 - 1
Core Insight
Counting up from left to right passes the number prefix followed by 0111...1 and then the number prefix followed by 1000...0. These two numbers have no 1 bit in common below the prefix, so the AND clears every lower bit. The answer is the shared prefix followed by zeros: shift both ends right until they are equal, count the shifts, and shift the prefix back left by that count.
Real-World Scenario & Production Applications
In network routing, the addresses of one subnet share their leading bits. The AND of all addresses in an aligned subnet is its network address: the shared leading bits followed by zeros.
Step-by-Step Execution Trace Table
Trace of Example 1: left = 5, right = 7, shift = 0.
| Step | left | right | left != right | shift |
|---|---|---|---|---|
| start | 101 (5) | 111 (7) | yes | 0 |
| after round 1 | 10 (2) | 11 (3) | yes | 1 |
| after round 2 | 1 (1) | 1 (1) | no, stop | 2 |
The ends are equal after two rounds, so the shared prefix is 1. The function returns left << shift = 1 << 2 = 4.
| 1 | shift = 0 |
| 2 | while left != right: |
| 3 | left >>= 1 |
| 4 | right >>= 1 |
| 5 | shift += 1 |
| 6 | return left << shift |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Write left and right in binary. Counting up from left to right changes the low bits many times, but the high bits that the two ends share never change. Any bit below the highest place where the ends differ is 0 in at least one number of the range, so the AND clears it. The answer is the shared prefix, followed by zeros.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number with shifts and masks. Here two numbers are shifted together. The loop while left != right removes the lowest bit of both ends until they are equal, and shift counts the removed bits. The last line, left << shift, shifts the equal value back.
🔑 The Key Idea in the Code
After the loop, left holds only the shared prefix. The prefix must go back to its original place, so the answer is left << shift. Returning left alone gives a number that is 2 ** shift times too small.
Returning
leftwithout shifting it back: after the loop,leftholds only the shared prefix.return leftgives1forleft = 5andright = 7, where the answer isleft << shift = 4.Returning
left & rightof the two ends: a number between the ends can have a 0 where both ends have a 1. For5and7, the number6clears bit 0, so the answer is4, not5.Shifting only
rightin the loop: the loop ends whenleftequalsright. Shifting onlyrightmoves it toward 0 whileleftstays, so the loop never ends whenleftis larger than 0.Looping over every number of the range: the range can hold about 2 billion numbers, but the shift loop runs at most 31 times.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The bitwise AND of all numbers in the range" with right up to 231 - 1: the range can hold about 2 billion numbers, so a loop over the range is too slow, and the answer must come from the two ends alone.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends. The loop stops when they are equal, so left is then the shared prefix, and left << shift restores its place.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Shared Prefix. Counting up from left to right changes every bit below the highest place where the two ends differ, so the AND clears all of those bits. Only the binary prefix that the two ends share survives. I keep a counter, shift, at zero. While left is not equal to right, I shift both right by one and add one to shift. When they are equal, they hold exactly the shared prefix. The trap is the last line: left is only the prefix, so I return left shifted back left by shift, not left itself. For left 5 and right 7 the loop ends with left 1 and shift 2, and the answer is 4. Each round removes one bit from both ends, so the loop runs at most 31 times. That is O of log right time and O of 1 space.
Complexity & Mathematical Proof
O(log right)
Look at the loop. Each round shifts both ends right by one place, so right loses one bit per round. When right has no bits left, both ends are 0 and equal. right has at most 31 bits, so the loop runs at most 31 times. The number of rounds grows with the number of bits of right, which is log right, so time is O(log right).
O(1)
The code keeps three variables, left, right and shift, whatever the size of the range. There is no table and no recursion, so space is O(1).
Derivation Progression
right has at most 31 bits and loses one per round, so at most 31 rounds run.
3 = O(1)
Two shifts and one addition.
Rounds times a constant amount of work.
Variable Definitions
The larger end of the range, at most 2^31 - 1
How many low bits have been removed from both ends
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables left, right and shift
O(1): one integer
Boundary Best / Worst Cases
: the ends are already equal, so the loop does not run.
.
: 31 rounds, for example left = 1 and right = 2147483647.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "bitwise AND of all numbers in this range", a range that can reach . Looping over the range is too slow, so the answer must be read from the two ends. Any bit that changes inside the range is cleared by the AND, so only the binary prefix that the ends share can remain.
, so the range can hold about 2 billion numbers. A loop with a running AND is . The shift loop runs at most 31 times, so it is , and it uses only three variables.
Returning left without << shift gives the prefix without its original place: left = 5, right = 7 returns 1 instead of 4. Returning left & right of the two ends keeps bits that a number inside the range clears: it returns 5 for the same input. In a fixed-width language, left << shift stays below , because it is at most the original left, so it does not overflow.