BitWise And of Numbers Range [Bit Prefix with Brian Kernigan’s Algorithm]

201.Bitwise AND of Numbers Range

Bit Manipulation

Math

Problem Statement:

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

Example:

Input:

left = 5, right = 7

→

Output:

4

5 & 6 & 7 = 4

Algorithm:

1. Find common prefix of both numbers
2. Either use shift method or Brian Kernighan
3. All numbers in range share this prefix
4. Rest of bits become 0 in result

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

// Shift approach: Find common prefix
public int rangeBitwiseAndO(int m, int n) {
    int shift = 0;
    
    // Keep shifting right until numbers are equal
    while (m < n) {
        m >>= 1;
        n >>= 1;
        shift++;
    }
    
    // Shift back left to get final answer
    return m << shift;
}

// Brian Kernighan approach
public int rangeBitwiseAnd(int m, int n) {
    // Keep turning off rightmost 1-bit until numbers equal
    while (m < n) {
        n = n & (n - 1);  // Clear rightmost set bit
    }
    return n;
}

Python Solution:

def rangeBitwiseAnd(self, m: int, n: int) -> int:
    # Brian Kernighan approach
    while m < n:
        n &= (n - 1)  # Clear rightmost set bit
    return n

def rangeBitwiseAndShift(self, m: int, n: int) -> int:
    shift = 0
    
    # Find common prefix by shifting right
    while m < n:
        m >>= 1
        n >>= 1
        shift += 1
        
    # Shift back to get result
    return m << shift

C++ Solution:

int rangeBitwiseAnd(int m, int n) {
    // Brian Kernighan approach
    while (m < n) {
        n &= (n - 1);  // Clear rightmost set bit
    }
    return n;
}

int rangeBitwiseAndShift(int m, int n) {
    int shift = 0;
    
    // Find common prefix by shifting right
    while (m < n) {
        m >>= 1;
        n >>= 1;
        shift++;
    }
    
    // Shift back to get result
    return m << shift;
}