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.

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)

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

• Invariant: shifting both numbers right removes bits that must become 0 in the final AND.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

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.

Complexity

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

Implementation notes (Go)

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