Bitwise AND of Numbers Range

🎯

Bitwise AND of Numbers Range

mediumBIT_MANIPULATIONAmazonGoogle

Imagine you want to find the common bits set to 1 in all numbers between two given integers, like finding the shared traits in a family tree of numbers.

💡 This problem asks for the bitwise AND of all numbers in a range. Beginners often struggle because iterating through the entire range is inefficient, and understanding how bits behave over ranges requires insight into binary representation and bit manipulation.

📋

Problem Statement

Given two integers left and right, return the bitwise AND of all numbers in the inclusive range [left, right]. Input: Two integers left and right. Output: An integer representing the bitwise AND of all numbers from left to right inclusive.

0 <= left <= right <= 2^31 - 1The range size can be large, up to 2^31

💡

Example

Input"left = 5, right = 7"

Output4

5 (0101) & 6 (0110) & 7 (0111) = 4 (0100)

Input"left = 0, right = 1"

Output0

0 & 1 = 0

• left == right → output is left (single number)
• left = 0, right = 0 → output is 0
• left = 0, right = large number → output is 0
• left and right differ by 1 → output is bitwise AND of two numbers

⚠️

Common Mistakes

Trying to iterate through the entire range for large inputs

Time limit exceeded or very slow performance

✅ Use the shift-until-equal or bit-clearing approach to avoid iteration

Not handling the case when left == right

Incorrect output or unnecessary computation

✅ Add a check or rely on loop conditions that handle this naturally

Incorrectly shifting only one number instead of both

Wrong result because common prefix is not found correctly

✅ Shift both left and right simultaneously until they are equal

Using bit-clearing approach without understanding it

Confusion or incorrect implementation

✅ Understand that right & (right - 1) clears the rightmost set bit and use it in a loop

🧠

Brute Force (Iterate and AND)

💡 This approach exists to build intuition about the problem by directly applying the definition, even though it is inefficient for large ranges.

Intuition

We compute the bitwise AND of every number from left to right by iterating through the range and accumulating the result.

Algorithm

1. Initialize result as left.
2. Iterate from left+1 to right inclusive.
3. At each step, update result by ANDing it with the current number.
4. Return the final result.

💡 The algorithm is straightforward but slow because it checks every number, which is easy to understand but not scalable.

</>

Code

def rangeBitwiseAnd(left: int, right: int) -> int:
    result = left
    for num in range(left + 1, right + 1):
        result &= num
    return result

# Driver code
if __name__ == '__main__':
    print(rangeBitwiseAnd(5, 7))  # Output: 4

Line Notes

result = leftStart with the first number as the initial AND result

for num in range(left + 1, right + 1)Iterate through every number in the range to combine bits

result &= numUpdate result by keeping only bits set in both result and current number

return resultReturn the final AND after processing all numbers

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int result = left;
        for (int num = left + 1; num <= right; num++) {
            result &= num;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rangeBitwiseAnd(5, 7)); // Output: 4
    }
}

Line Notes

int result = left;Initialize result with the first number in the range

for (int num = left + 1; num <= right; num++)Loop through all numbers from left+1 to right

result &= num;Bitwise AND accumulates common bits across all numbers

return result;Return the final AND value after loop

#include <iostream>
using namespace std;

int rangeBitwiseAnd(int left, int right) {
    int result = left;
    for (int num = left + 1; num <= right; num++) {
        result &= num;
    }
    return result;
}

int main() {
    cout << rangeBitwiseAnd(5, 7) << endl; // Output: 4
    return 0;
}

Line Notes

int result = left;Initialize result with the starting number

for (int num = left + 1; num <= right; num++)Iterate through the range to combine bits

result &= num;Keep only bits set in both result and current number

return result;Return the final AND after processing all numbers

function rangeBitwiseAnd(left, right) {
    let result = left;
    for (let num = left + 1; num <= right; num++) {
        result &= num;
    }
    return result;
}

// Test
console.log(rangeBitwiseAnd(5, 7)); // Output: 4

Line Notes

let result = left;Initialize result with the first number in the range

for (let num = left + 1; num <= right; num++)Loop through all numbers from left+1 to right

result &= num;Update result by ANDing with current number to keep common bits

return result;Return the final AND after processing all numbers

⏱

Complexity

TimeO(right - left)

SpaceO(1)

We iterate through every number in the range, so time depends linearly on the size of the range. Space is constant as we only store one result variable.

💡 For example, if left=1 and right=1,000,000, this means 1 million operations, which is too slow for large inputs.

Interview Verdict: TLE for large ranges

This approach is too slow for large inputs, but it helps understand the problem and verify correctness on small inputs.

🧠

Better Approach (Shift Until Equal)

💡 This approach improves efficiency by focusing on the common prefix of left and right in binary form, avoiding iteration over the entire range.

Intuition

The bitwise AND of a range zeros out any bit that changes within the range. By right-shifting both numbers until they are equal, we isolate the common prefix bits that remain set.

Algorithm

1. Initialize a shift counter to 0.
2. While left != right, right-shift both left and right by 1 and increment shift.
3. When equal, left contains the common prefix bits.
4. Left-shift left by shift to restore the bits and return.

💡 This algorithm cleverly finds the stable bits by removing differing bits from the right until the numbers match.

</>

Code

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

# Driver code
if __name__ == '__main__':
    print(rangeBitwiseAnd(5, 7))  # Output: 4

Line Notes

shift = 0Initialize counter for how many bits we shift

while left != right:Loop until both numbers have the same prefix

left >>= 1Right shift left to remove the least significant bit

return left << shiftRestore the common prefix bits by left shifting back

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rangeBitwiseAnd(5, 7)); // Output: 4
    }
}

Line Notes

int shift = 0;Initialize shift counter to track bit removals

while (left != right)Loop until left and right share the same prefix

left >>= 1;Remove the least significant bit from left

return left << shift;Restore the common bits by shifting left back

#include <iostream>
using namespace std;

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

int main() {
    cout << rangeBitwiseAnd(5, 7) << endl; // Output: 4
    return 0;
}

Line Notes

int shift = 0;Initialize counter for number of shifts

while (left != right)Loop until both numbers have the same prefix bits

left >>= 1;Right shift left to discard differing bits

return left << shift;Shift back to restore the common prefix bits

function rangeBitwiseAnd(left, right) {
    let shift = 0;
    while (left !== right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
}

// Test
console.log(rangeBitwiseAnd(5, 7)); // Output: 4

Line Notes

let shift = 0;Initialize shift counter to zero

while (left !== right)Loop until left and right share the same bits

left >>= 1;Remove the least significant bit from left

return left << shift;Restore the common bits by shifting left

⏱

Complexity

TimeO(log(right))

SpaceO(1)

Each iteration shifts the numbers right, reducing their size by half, so the loop runs at most the number of bits in right.

💡 For 32-bit integers, this means at most 32 iterations, which is very efficient.

Interview Verdict: Accepted

This approach is efficient and passes all tests, making it suitable for interviews.

🧠

Optimal Approach (Brian Kernighan’s Algorithm Inspired)

💡 This approach uses a bit manipulation trick to clear the rightmost set bit of right until it is less than or equal to left, efficiently converging to the common prefix.

Intuition

By repeatedly clearing the rightmost set bit of right, we remove bits that differ from left, eventually isolating the common prefix bits.

Algorithm

1. While right > left, clear the rightmost set bit of right using right = right & (right - 1).
2. When right <= left, return right as the bitwise AND of the range.

💡 This algorithm efficiently removes bits that cause differences, converging quickly to the answer.

</>

Code

def rangeBitwiseAnd(left: int, right: int) -> int:
    while right > left:
        right = right & (right - 1)
    return right

# Driver code
if __name__ == '__main__':
    print(rangeBitwiseAnd(5, 7))  # Output: 4

Line Notes

while right > left:Loop until right is less than or equal to left

right = right & (right - 1)Clear the rightmost set bit of right to remove differing bits

return rightReturn the stable bits common to the entire range

print(rangeBitwiseAnd(5, 7))Test the function with example input

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right = right & (right - 1);
        }
        return right;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rangeBitwiseAnd(5, 7)); // Output: 4
    }
}

Line Notes

while (right > left)Continue until right is less or equal to left

right = right & (right - 1);Remove the rightmost set bit from right

return right;Return the final AND value after clearing differing bits

System.out.println(...)Test output for correctness

#include <iostream>
using namespace std;

int rangeBitwiseAnd(int left, int right) {
    while (right > left) {
        right = right & (right - 1);
    }
    return right;
}

int main() {
    cout << rangeBitwiseAnd(5, 7) << endl; // Output: 4
    return 0;
}

Line Notes

while (right > left)Loop until right is less than or equal to left

right = right & (right - 1);Clear the rightmost set bit to remove differing bits

return right;Return the stable bits common to the range

cout << rangeBitwiseAnd(5, 7)Print test result

function rangeBitwiseAnd(left, right) {
    while (right > left) {
        right = right & (right - 1);
    }
    return right;
}

// Test
console.log(rangeBitwiseAnd(5, 7)); // Output: 4

Line Notes

while (right > left)Loop until right is less or equal to left

right = right & (right - 1);Remove the rightmost set bit from right

return right;Return the final AND value after clearing bits

console.log(...)Output test result for verification

⏱

Complexity

TimeO(k), where k is number of differing bits

SpaceO(1)

Each iteration clears one set bit from right, so the loop runs at most the number of set bits in right.

💡 For example, if right has 5 set bits, the loop runs at most 5 times, which is very efficient.

Interview Verdict: Accepted

This approach is optimal and concise, making it ideal for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the shift-until-equal approach is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(right - left)	O(1)	No	N/A	Mention only - never code for large inputs
2. Shift Until Equal	O(log(right))	O(1)	No	N/A	Preferred approach to code in interviews
3. Bit-Clearing Trick	O(k), k = number of set bits in right	O(1)	No	N/A	Good alternative, mention if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Explain why brute force is inefficient for large inputs.Step 4: Introduce the shift-until-equal approach as an optimization.Step 5: Optionally mention the bit-clearing trick as an elegant alternative.Step 6: Code the chosen approach carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test & Discuss: 7min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, ability to optimize naive solutions, and clarity in explaining your approach.

Common Follow-ups

• What if the range is very large? → Use the optimal approach to handle large ranges efficiently.
• Can you explain why the common prefix matters? → Because bits that differ in the range will be zeroed out in the AND.

💡 These follow-ups test your deeper understanding of bitwise operations and efficiency considerations.

🔍

Pattern Recognition

When to Use

1) Asked for bitwise AND over a range; 2) Range can be large; 3) Need efficient bit manipulation; 4) Recognize common prefix or stable bits

Signature Phrases

bitwise AND of all numbers in rangecommon prefix bitsright shift until equal

NOT This Pattern When

Problems asking for sum or product over ranges, or unrelated bitwise operations like counting set bits

Similar Problems

Bitwise AND of Numbers Range II - similar but with multiple queriesRange Bitwise OR - similar pattern but for OR operationBitwise XOR of Numbers Range - related but different bitwise operation

Practice

1. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

2. You are given an array where exactly two elements appear only once and all the other elements appear exactly twice. Which approach guarantees finding these two unique elements in linear time and constant space?

easy

A. Use XOR of all elements, then partition the array by a set bit of the XOR result and XOR partitions separately.

B. Sort the array and scan linearly to find the two unique elements.

C. Use a hash map to count occurrences and then collect elements with count one.

D. Use a greedy approach to pick elements that appear once by checking neighbors.

Solution

1. Step 1: Understand the problem constraints

   Two unique elements appear once, others appear twice. We want O(n) time and O(1) space.

2. Step 2: Identify the approach that uses XOR partitioning

   XOR all elements to get xor = num1 ^ num2. Find a set bit in xor to partition elements into two groups, each containing one unique number. XOR each group separately to find the unique numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting is O(n log n), hash map uses extra space, greedy fails on duplicates [OK]

Hint: XOR partitioning splits unique numbers by differing bit [OK]

Common Mistakes:

• Assuming sorting is linear time
• Using hash map violates O(1) space
• Greedy fails on duplicates

3. The following code attempts to find two missing numbers using XOR partitioning but sometimes returns incorrect results. Identify the bug.

medium

A. Final return statement returning [x, y]

B. Line calculating xor_all with XOR of all numbers

C. Loop partitioning numbers based on set_bit

D. Line calculating set_bit using bitwise OR instead of AND

Solution

1. Step 1: Understand set_bit calculation

   Correct approach finds rightmost set bit using xor_all & (-xor_all). Using OR instead breaks partitioning.

2. Step 2: Consequence of bug

   Incorrect set_bit causes wrong grouping of numbers, leading to incorrect missing numbers returned.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Replacing OR with AND fixes partitioning and output [OK]

Hint: Rightmost set bit must be found with AND, not OR [OK]

Common Mistakes:

• Using OR instead of AND for set bit
• Misplacing XOR operations
• Returning wrong variables

4. What is the time complexity of the brute force bit counting approach that checks each bit of a 32-bit integer one by one?

medium

A. O(log n) where n is the integer's value

B. O(n) where n is the integer's value

C. O(1) because the number of bits is fixed (32 bits)

D. O(32 * log n) due to bit shifts and counting

Solution

1. Step 1: Identify input size

   The input is an integer n, and the brute force method checks each bit by shifting until n becomes zero.

2. Step 2: Analyze loop iterations

   The number of iterations depends on the number of bits in n, which is proportional to log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Loop runs approximately log n times, so complexity is O(log n) [OK]

Hint: Number of bits in n is proportional to log n [OK]

Common Mistakes:

• Assuming fixed bit width means O(1)
• Confusing value magnitude with fixed bit size

5. What is the time complexity of the brute force iterative division approach to check if a number n is a power of four?

medium

A. O(1) because division is constant time

B. O(n) because it checks every number up to n

C. O(log log n) because division by 4 reduces n faster than by 2

D. O(log n) because the number is divided by 4 each iteration

Solution

1. Step 1: Analyze the loop iterations

   Each iteration divides n by 4, so the number of iterations is proportional to log base 4 of n.

2. Step 2: Express complexity in Big-O notation

   Since log base 4 of n is O(log n), the time complexity is O(log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop runs ~log4(n) times, which is O(log n) [OK]

Hint: Dividing by 4 reduces n logarithmically -> O(log n)

Common Mistakes:

• Confusing division steps as O(1)
• Mistaking log log n complexity