Bitwise AND Range LeetCode 201 Guide

LeetCode 201 — Bitwise AND of Numbers Range — asks you to return the bitwise AND of all integers in the inclusive range [left, right]. For example, given left = 5 and right = 7, the answer is 4 because 5 & 6 & 7 = 4.

The range can span up to 2^31 integers, so iterating from left to right computing AND is completely infeasible. You need an O(log n) insight that collapses the range into a single operation.

Despite its Medium label, this problem is a pure bit-manipulation puzzle. Once you see the key insight — that the AND of a range preserves only the common binary prefix of its endpoints — the solution writes itself.

The AND of any two consecutive integers always clears the lowest differing bit. Think about it: if two numbers differ at bit position k, then every value in the range between them cycles through both 0 and 1 at position k. Once a bit position has both a 0 and a 1 anywhere in the range, its AND contribution is 0.

This means the AND of the entire range [left, right] is exactly the common binary prefix shared by left and right. All bits below the highest differing bit position become 0 after the AND. The bits above that position — where left and right agree — are preserved.

For example, 5 = 101 and 7 = 111. They differ starting at bit 1. The common prefix at bit 2 is 1, giving result 100 = 4. Every bit below the common prefix is zeroed out by the AND of the values in between.

The right-shift approach works by repeatedly shifting both left and right one bit to the right until they become equal. At that point, both numbers share all remaining bits — meaning those bits form the common prefix. You then shift the result back left by the number of shifts performed.

Each shift removes the lowest bit from both numbers. Because differing lower bits are discarded, the two numbers converge toward their common prefix. Once left equals right, you have isolated exactly the bits that survive the AND of the full range.

This approach is elegant in its simplicity: count the shifts, find the equal value, shift it back. The time complexity is O(32) for 32-bit integers — effectively O(1) — and space is O(1).

An alternative uses the Brian Kernighan bit-clearing trick: right = right & (right - 1) clears the lowest set bit of right. By repeatedly clearing the lowest set bit of right while right is greater than left, you progressively strip away bits that differ between right and left.

When right finally drops to or below left, you have removed all the bits that are not part of the common prefix. At that point, right itself is the common prefix — which is exactly the AND of the entire range.

Both approaches run in O(32) time and O(1) space. The Brian Kernighan version tends to converge faster in practice when left and right differ in only a few low bits, since it clears one set bit per iteration rather than always shifting by exactly one.

Let us trace through the right-shift approach with left = 5 (binary: 101) and right = 7 (binary: 111). These differ at bits 0 and 1, so we expect those bits to be zeroed out, leaving 100 = 4.

We start the shift counter at 0. In the first iteration, 5 != 7, so we shift: left becomes 10 (2), right becomes 11 (3), shift count is now 1. Still not equal, so we shift again: left becomes 1, right becomes 1, shift count is 2. Now left == right, so we stop.

The common prefix is 1. We shift it back: 1 << 2 = 4. We can verify: 5 & 6 & 7 = 101 & 110 & 111 = 100 = 4. Correct! The two lower bits were zeroed because both 0 and 1 appear at those positions within the range.

Both the right-shift approach and the Brian Kernighan approach are clean and concise. The Python right-shift version: initialize shifts=0; while left!=right: left>>=1, right>>=1, shifts+=1; return left<<shifts. That is four lines. The Brian Kernighan Python version: while right>left: right&=right-1; return right. Two lines.

In Java the code is identical in structure. The right-shift version: int shifts=0; while(left!=right){left>>=1; right>>=1; shifts++;} return left<<shifts;. The Kernighan version: while(right>left) right&=right-1; return right;. Both run in O(log n) — more precisely O(32) = O(1) for 32-bit integers — and use O(1) space.

Either approach is acceptable in an interview. The right-shift version is perhaps easier to explain from first principles. The Kernighan version is shorter and shows familiarity with classic bit tricks. Mentioning both and explaining why they are equivalent will impress interviewers.

LeetCode 201 belongs to the "bit prefix" family of problems. Single Number II (LeetCode 137) uses bit counting across 32 positions to find a number that appears once among triples — a completely different technique but the same spirit of reasoning about bits column by column. Counting Bits (LeetCode 338) builds a DP table where each entry is the popcount of its index, exploiting the relationship between n and n>>1.

Number of 1 Bits (LeetCode 191) directly applies the Brian Kernighan trick: repeatedly clear the lowest set bit and count how many times you do so. If you understand why right & (right-1) clears the lowest set bit, both problem 191 and the Kernighan solution to 201 become trivial.

The bit prefix family also includes problems where you find the XOR or OR common across a range. Any time a problem involves a binary operation applied to all numbers in a range, your first question should be: what survives? For AND, only the common prefix survives. Understanding that mental model will let you transfer the insight across many similar problems.