Bitwise AND of Numbers Range

Given two integers left and right, return the bitwise AND of all numbers in the inclusive range [left, right]. Naively ANDing every number is too slow for large ranges.

Why this is worth learning

The inclusive range preserves only the common high-bit prefix of its endpoints. Below their highest differing position, the interval necessarily crosses a binary boundary that clears those suffix bits.

Before coding: one-minute experiment

For range [5,7], write the three values in binary and explain the result without iterating through a large range.

Function signature

func RangeBitwiseAnd(left, right int) int

Inputs / outputs

• left, right: range bounds.
• Return: AND of all numbers in the range.

Example

left = 5 (101), right = 7 (111)
Range AND = 100 (4)

Constraints

• 0 <= left <= right <= 2^31 - 1

Core idea (near-solution)

Directly ANDing every integer is correct but the inclusive range can contain billions of values. Endpoint AND alone is faster but wrong: 5 and 7 both end in 1, while the interior 6 clears that bit. Locate the highest differing position of the endpoints. Above it all values share a prefix; at and below it the interval crosses a boundary supplying zeroes. This justifies discarding the entire suffix rather than enumerating it.

The AND of a range keeps only the common binary prefix of left and right. Any differing lower bit will be zeroed somewhere in the range.

Invariant: shifting both numbers right removes bits that must become 0 in the final AND.

Algorithm (step-by-step)

1. Initialize shift = 0.
2. While left != right:
   • left >>= 1, right >>= 1, shift++.
3. Return left << shift.

Correctness sketch

If left and right are equal, the range contains one value. Otherwise, shift both right until they match, counting s shifts. Their common remaining bits are shared by every number between the endpoints because none crosses a boundary above the highest differing bit. At that differing bit, the interval crosses from a zero block to a one block; it includes a boundary value whose lower suffix is all zero, so every removed suffix position has at least one zero somewhere in the range. AND therefore clears all s suffix positions. Shifting the common prefix back left restores exactly the surviving bits.

Trace (hand walkthrough)

Example input:
left = 5 (101), right = 7 (111)
Range AND = 100 (4)

Walk:
- left=101, right=111 -> shift1: 10,11
- shift2: 1,1 -> common prefix 1
- shift back -> 100 (4)

Pitfalls to avoid

• Using left & right directly (incorrect for ranges > 2 numbers).
• Forgetting that left==right means the AND is that value.

Debugging lens

Test equal endpoints, ranges crossing a power of two, and ranges beginning at zero. Endpoint AND alone is insufficient: 5&7 is 5, but AND of 5,6,7 is 4.

Complexity

• Time: O(1) (<= 31 shifts).
• Extra space: O(1).

Implementation notes (Go)

• Use non-negative ints; shifting works reliably for non-negative values.

Reconstruction checkpoint

For range [5,7], write the three values in binary and explain the result without iterating through a large range.

Return to Bit Manipulation · Module quiz