Bitwise AND of Numbers Range

MEDIUM✓ CHIP-TIMEDLC #201 — FULL STATEMENT ↗

The drill: AND together every integer in the inclusive range from left to right — one differing bit anywhere in that range zeroes it out for good, so the answer is usually shorter than you'd guess.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two integers arrive marking the two ends of an inclusive range, with left never larger than right, and the task is to AND together every integer from left through right.

Because a bitwise AND only keeps a bit that every single operand agrees on, the moment any two numbers inside that range disagree on some bit position, that bit is gone from the final result for good.

The range can span a huge count of integers, but the answer only ever depends on the small handful of leading bits where left and right themselves still agree.

EX 01

left = 5 · right = 7

→ 4

THE BOARD'S EXAMPLE

EX 02

left = 0 · right = 0

→ 0

SINGLE VALUE, ZERO

EX 03

left = 1 · right = 1

→ 1

SINGLE VALUE, NONZERO

left and right are non-negative integers with left ≤ right
the range being ANDed is inclusive on both ends
values can run up into the billions, so the range itself may be enormous
the result depends only on the shared leading bits of left and right

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

ANDing every number in a huge range one by one is correct, but the range itself can be enormous — most of that work produces zero long before the loop ends.

HINT 2 THE STRUCTURE

The moment two numbers in the range disagree on a bit, that bit is gone from the final answer forever. What's the earliest bit where left and right themselves could possibly disagree?

HINT 3 ONE STEP FROM THE ANSWER

Right-shift left and right together until they're equal — that surviving common prefix is the only part of the answer that could ever have stayed 1. Shift it back into place.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE COMMON PREFIXPATTERN · COMMON PREFIX SHIFTleft = 5 · right = 7

LEFT / RIGHT (BINARY)

left → 5 (101)

right → 7 (111)

STEP 1

5 and 7 disagree on their lowest bit. Shift both right together until they match — the surviving prefix is the answer.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/bitwise-and-of-numbers-range.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        while left != right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift

TIME O(LOG RIGHT)SPACE O(1)PYTHON · RACE PACE · 8 LN

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        result = left
        for v in range(left, right + 1):
            result &= v
            if result == 0:
                break
        return result

TIME O(RIGHT − LEFT)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

TIME O(LOG RIGHT)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int result = left;
        for (int v = left; v <= right; v++) {
            result &= v;
            if (result == 0) {
                break;
            }
        }
        return result;
    }
}

TIME O(RIGHT − LEFT)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED