Log inSign up
mediumLeetCodeNot Started

Bitwise AND of Numbers Range

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given two integers left and right representing the closed interval [left, right], return the bitwise AND of all numbers in this range, inclusive.

Formally, compute left & (left + 1) & (left + 2) & ... & right.

Example 1 · Example 1: Standard Range:

Input: left = 5, right = 7
Output: 4
Explanation: 5 is 101 in binary, 6 is 110, 7 is 111. 101 & 110 & 111 = 100 (which is 4 in decimal).

Example 2 · Example 2: Zero Range:

Input: left = 0, right = 0
Output: 0
Explanation: Only 0 exists in range [0, 0]. 0 & 0 = 0.

Example 3 · Example 3: Large Disjoint Range:

Input: left = 1, right = 2147483647
Output: 0
Explanation: 1 and 2147483647 share no common non-zero prefix bits. The result is 0.

Constraints:

  • 0 <= left <= right <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why bitwise AND over a contiguous range preserves only the shared binary prefix.
  • Master the bit-shift prefix alignment pattern.
  • Apply Brian Kernighan's bit clearing trick to solve range AND in reverse.
  • Implement verified solutions in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks for bitwise AND across an entire integer range [L, R].
  • Range can be as large as 2 * 109, making linear iteration impossible.
  • Focus on bit flipping frequencies across consecutive integers.

Algorithmic Decision Tree:

  • If left == right, answer is simply left.
  • If left and right have different bit lengths (different MSB), result is 0.
  • Extract common binary prefix by shifting right or clearing rightmost set bits.

Connected Patterns:

Counting BitsReverse BitsBrian Kernighan's Algorithm

1. Iterative Accumulator

Intuition

Initialize res = left. Loop for i from left + 1 to right, computing res &= i. If res becomes 0 at any point, return 0 immediately since AND with 0 stays 0.

When to apply: When right - left is guaranteed to be small (< 105).

Algorithm

  1. Step 1: Initialize res = left.
  2. Step 2: Loop i from left + 1 to right. Compute res &= i.
  3. Step 3: If res == 0, break early and return 0.
  4. Step 4: Return res after loop completes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int rangeBitwiseAndBrute(int left, int right) {
6 long long res = left;
7 for (long long i = (long long)left + 1; i <= right; ++i) {
8 res &= i;
9 if (res == 0) return 0;
10 }
11 return (int)res;
12}
13
14int main() {
15 cout << "Brute (5, 7): " << rangeBitwiseAndBrute(5, 7) << endl; // 4
16 cout << "Brute (0, 0): " << rangeBitwiseAndBrute(0, 0) << endl; // 0
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(R - L)
  • Space complexity: O(1)

2. Brian Kernighan's Bit Clearing

Intuition

In binary representation, right & (right - 1) clears the lowest set bit of right. While right > left, clear the lowest set bit. Any bit cleared this way has flipped to 0 somewhere between left and right. Once right <= left, right holds the common prefix with all lower bits zeroed out.

When to apply: When seeking an intuitive one-line loop without shift-count tracking.

Algorithm

  1. Step 1: Loop while right > left.
  2. Step 2: Clear lowest set bit: right = right & (right - 1).
  3. Step 3: Return right.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int rangeBitwiseAndKernighan(int left, int right) {
6 while (right > left) {
7 right &= (right - 1);
8 }
9 return right;
10}
11
12int main() {
13 cout << "Better (5, 7): " << rangeBitwiseAndKernighan(5, 7) << endl; // 4
14 cout << "Better (12, 15): " << rangeBitwiseAndKernighan(12, 15) << endl; // 12
15 return 0;
16}

Time & Space Complexity

  • Time complexity: O(number of set bits in right) <= 32
  • Space complexity: O(1)

3. Bit-Shift Common Prefix

Intuition

The problem reduces to finding the longest common binary prefix of left and right. We increment a shift counter while left < right, right-shifting both numbers. When left == right, we have isolated their common prefix. Left-shifting left by shift pads the non-common suffix with zeros, giving the exact range AND.

When to apply: Optimal for any 32-bit integer range up to [0, 231 - 1].

Algorithm

  1. Step 1: Initialize shift = 0.
  2. Step 2: While left < right, right-shift both: left >>= 1, right >>= 1, and increment shift.
  3. Step 3: Return left << shift.

Bit-Shift Common Prefix Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initial state: left = 5 (binary 101), right = 7 (binary 111)
Visual state
Values and pointers at this exact step
pointers
S
101
111
0
↑ shift
1
Check / comparison
5 != 7
Decision / next transition
Right shift both left and right by 1.
Why this step matters

Initial state: left = 5 (binary 101), right = 7 (binary 111). shiftCount = 0. left != right.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int rangeBitwiseAnd(int left, int right) {
8 int shift = 0;
9 while (left < right) {
10 left >>= 1;
11 right >>= 1;
12 shift++;
13 }
14 return left << shift;
15 }
16};
17
18int main() {
19 Solution sol;
20 cout << "Optimal (5, 7): " << sol.rangeBitwiseAnd(5, 7) << endl; // 4
21 cout << "Optimal (0, 0): " << sol.rangeBitwiseAnd(0, 0) << endl; // 0
22 cout << "Optimal (1, 2147483647): " << sol.rangeBitwiseAnd(1, 2147483647) << endl; // 0
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(1) (at most 31 shifts)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear ScanO(R - L)O(1)Loop from left to right, accumulating bitwise AND into a running result.Linear iteration over the range.
2.Better — Brian Kernighan's Bit ClearingO(number of set bits in right) <= 32O(1)Repeatedly turn off the lowest set bit of right (right = right & (right - 1)) while right > left.Number of 1s in the binary representation of right.
3.Optimal — Bit Shift Common PrefixOptimalO(1) (at most 32 shifts)O(1)Shift both left and right to the right until left == right, counting shift steps. Then shift left back by the count.Bit-shift count.

Common Pitfalls & Crucial Edge Cases

Iterating through every number in [left, right]

For constraints like left = 1 and right = 231 - 1, an O(right - left) loop triggers Time Limit Exceeded (TLE).

Operator precedence errors

Writing right & right - 1 without parentheses executes - before &, altering the logic. Always use right & (right - 1).

Shift overflow on signed integers

Shifting by 32 bits or into the sign bit in languages like C/C++ invokes undefined behavior.

Crucial Edge Cases to Validate:

  • left == right — The range consists of a single number, so the result is simply left.
  • left == 0 — Any bitwise AND containing 0 will result in 0.
  • Range spans across powers of 2 (e.g. left = 3, right = 4) — The most significant bit changes, so common prefix is 0 and the answer is 0.
  • Maximum 32-bit integer boundaries — Ensure shifts do not cause signed integer overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the key observation immediately: consecutively incrementing numbers will alternate lower bits, so only identical higher-order prefix bits remain.
  2. Mention both solutions: the right-shift alignment approach and the Brian Kernighan clearing approach (right &= right - 1).
  3. Clarify whether the inputs are signed or unsigned 32-bit integers.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the bitwise AND of all numbers in [left, right] reduce to finding their common binary prefix?

2.What is the optimal time complexity to find the bitwise AND of range [left, right]?

3.How can Brian Kernighan's trick (n & (n - 1)) be used to solve this problem?

Back to DSA Sheet