The O(n) Club: Bitwise AND of Numbers Range — or, Why Naive Loops Cry

The O(n) Club: Bitwise AND of Numbers Range — or, Why Naive Loops Cry

⚡ TL;DR

Bitwise AND from left to right: all differing bits will be mercilessly zeroed out. Don’t even try to brute-force this with a loop—unless you like stress-testing CPUs and breaking hearts.

// Fast & clever: match only the high shared bits
public int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
}

🧠 How Devs Usually Mess This Up

Let’s face it: many developers instinctively reach for the old reliable for-loop and try to AND everything in sight (ans = left; for (int i = left + 1; i <= right; i++) ans &= i;). This works beautifully for ranges smaller than your lunch order. On any real input? You just summoned the runtime demons. Others try left & right (cute, but flat wrong when more than one number is in play—any bit that changes between the endpoints gets wiped out, like your optimism during an outage).

🔍 What’s Actually Going On

Visualize binary numbers as stubborn old electrical switches. If a switch ever flickers (flips) somewhere in the range, that line fuses off forever—any position that isn’t the same in both left and right is lost to history, replaced by zero. So your goal? Keep only the parts that never changed—the leftmost (high) bits they share. Everything below the first differing bit? Kablooey. This is why we right-shift until they’re identical, then rebuild the result by slapping the zeroes back on.

🛠️ PseudoCode

• Set up a shift counter. (That’s your demolition crew, tracking how much you’ve cleared.)
• Keep shifting left and right right until they match.
• Each shift, increment your counter.
• When they finally agree, you’ve found the shared prefix.
• Move it back where it belongs: shift left the same amount you shifted right. Voilà—done.

// Java logic in friendly pseudocode
int shifts = 0;
while (left != right) {
    left >>= 1;
    right >>= 1;
    shifts++;
}
return left << shifts;

💻 The Code

public int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    // Nudge both numbers right until they're soulmates
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    // Put the zeroes back where we stole them
    return left << shift;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Large Ranges: Never, ever, ever loop from left to right—unless you want a free space heater.
• Zero In the Range: If your range includes a number where all bits vanish (i.e., crosses a power of two), the result is zero. Pay attention.
• Negative Numbers: Problem is typically non-negative, but don’t go sign-extending by accident. Java’s binary is unforgiving.
• Complexity: O(log n)—yes, really. That’s just counting the bits, not the regret.

🧠 Interviewer Brain-Tattoo

“If you try to brute-force a range AND, the only bit you’ll keep is sticking in their memory for the wrong reason.”