medium Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Problem. Given two integers left and right with 0 ≤ left ≤ right, return the bitwise AND of every integer in the inclusive range [left, right]: left & (left+1) & … & right.

Naive baseline. Loop i from left to right, AND them all. Correct, but the range can be enormous — with right up to 2⁷¹ - 1 the loop can run billions of times and time out. We need a way to get the answer without visiting every number. The bit structure hands it to us.

The insight — the answer is the common binary prefix

Claim: AND(left..right) equals the longest common leading bit prefix of left and right, with every lower bit set to 0.

Proof of why differing bits vanish. AND turns a bit off if any number in the range has a 0 there. Let i be the highest bit position where left and right differ (if none, left == right and the answer is just left). Every bit above i is identical in left and right — the common prefix — so it is identical for every number in between too, and AND preserves it. For bit i and everything below it: since left < right and they agree above i, left has a 0 at bit i and right has a 1. Consider the number P1 = the common prefix, a 1 at bit i, and 0s below. Then left < P1 ≤ right, so P1 is in the range, and its predecessor P1 - 1 = prefix, 0 at bit i, and all 1s below — is also in the range (it is ≥ left). Now take any bit j ≤ i: exactly one of P1 and P1 - 1 has a 0 there. So every bit from i down is zeroed by the AND. What survives is precisely the common prefix followed by zeros. □

Approach 1 — strip differing suffix by shifting both together

To find the common prefix, shift left and right right in lockstep until they are equal — that throws away exactly the differing low bits. Count the shifts, then shift the common value back left the same amount to put the zeros back where the low bits were.

shift = 0
while (left != right) { left >>= 1; right >>= 1; shift++; }
return left << shift;   // common prefix, low bits restored as 0

Traced example — AND of [5, 7]

5 = 101, 6 = 110, 7 = 111. The true answer is 101 & 110 & 111 = 100 = 4. Watch Approach 1 recover it without touching 6:

Common prefix is 1, shifted back by 2: 1 << 2 = 100 = 4. Correct, and we never enumerated the range. The differing low 2 bits were shifted out and returned as zeros — exactly what the proof predicted.

Approach 2 — Kernighan: strip right's lowest set bit until it drops below left

right & (right - 1) clears the lowest set bit of right (subtracting 1 flips the lowest 1 to 0 and the bits below it to 1; ANDing with the original keeps only the higher bits). Repeatedly clearing right's low set bits while right > left walks right down to the common prefix. When right ≤ left, the low differing bits are gone and right holds the answer.

while (left < right) { right &= right - 1; }
return right;

On [5, 7]: right = 7 & 6 = 6 (still > 5) → right = 6 & 5 = 4 (now < 5, stop) → return 4. Same answer, verified by execution.

Java: common-prefix by shifting

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left != right) {   // inputs are non-negative, so >> is safe
            left  >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }

    // Alternative: Kernighan shrink
    public int rangeBitwiseAndK(int left, int right) {
        while (left < right) right &= right - 1;
        return right;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rangeBitwiseAnd(5, 7));    // 4
        System.out.println(s.rangeBitwiseAnd(0, 0));    // 0
        System.out.println(s.rangeBitwiseAndK(12, 15)); // 12
    }
}

Go: common-prefix by shifting

package main

import "fmt"

func rangeBitwiseAnd(left, right int) int {
    shift := 0
    for left != right {
        left >>= 1
        right >>= 1
        shift++
    }
    return left << shift
}

func rangeBitwiseAndK(left, right int) int { // Kernighan shrink
    for left < right {
        right &= right - 1
    }
    return right
}

func main() {
    fmt.Println(rangeBitwiseAnd(5, 7))    // 4
    fmt.Println(rangeBitwiseAnd(0, 0))    // 0
    fmt.Println(rangeBitwiseAndK(12, 15)) // 12
}

Complexity

• Shifting approach: each iteration drops one bit, so it runs at most w = 32 times → O(log(max value)) = O(1) for 32-bit ints. O(1) space.
• Kernighan approach: each iteration removes one set bit of right, so it runs at most (number of set bits) ≤ 32 times → also O(1) / O(1) space. In practice it often does fewer iterations than the shift version.
• Naive loop: O(right - left) time — up to ~2⁷¹ iterations. That is the whole reason the bit approach exists.

Judgment layer — when the bit trick is essential, and when the naive loop is fine

• Reach for the prefix/Kernighan trick whenever the range can be large — which, given the 2⁷¹ constraint, is the intended case. The naive AND loop is not just slower, it will time out; here the bit insight is not a micro-optimization, it is the difference between a passing and a failing solution.
• The naive loop is acceptable only when you can prove right - left is tiny and bounded, and clarity is paramount. But even then the prefix version is barely longer and removes the risk entirely — there is little reason to prefer the loop.
• Shift vs. Kernighan: both are O(1) and correct; pick the one you can explain cleanly. The shift version is the more intuitive "find the common prefix" story; Kernighan is tighter but leans on the x & (x-1) identity, so only use it if you can state why that clears the lowest set bit.
• vs. a math/formula shortcut: there is no simpler closed form — the answer genuinely depends on the bit-prefix structure, so this is one of the rare problems where the bit manipulation is the natural solution, not a clever detour.

Traps & edge cases

• left == right: both loops return left immediately — the range is a single number, so the AND is that number.
• left == 0: the range includes 0, and 0 & anything = 0, so the answer is 0. Both methods produce it (the prefix collapses to 0). Verified [0,0] = 0.
• Inputs are non-negative (per constraints), so arithmetic >> is safe in Java — no sign-extension concern here, unlike Reverse Bits. If you generalized to signed inputs you would need to revisit this.
• Kernighan guard is left < right, not !=: you want to stop as soon as right has been reduced to at most left, and right &= right-1 can jump right to a value below left without ever hitting equality.
• Don't forget to shift back in Approach 1 — returning left instead of left << shift drops the trailing zeros and gives a wrong, too-small answer.

Authored for this guide from first principles (LeetCode 201). The common-prefix proof is derived above; [5,7]→4, [12,15]→12, [0,0]→0, and [10,10]→10 — along with the raw checks 5&6&7=4 and 12&13&14&15=12 — were confirmed by running both the shift and Kernighan variants in Java 8 and Go 1.25.