Vultr DocsLatest Content

Bitwise AND of Numbers Range

Updated on 13 May, 2025
Bitwise AND of Numbers Range header image

Problem Statement

Given two integers left and right which represent the start and end of a numeric range [left, right], the task is to compute the bitwise AND operation for all integers between left and right, inclusive of left and right themselves. Bitwise AND is a binary operation that takes two bits at corresponding positions in the binaries of two numbers and yields 1 if both bits are 1, otherwise 0. For the range [left, right], we must apply this operation sequentially over all the numbers from left to right.

Examples

Example 1

Input:

left = 5, right = 7

Output:

4

Example 2

Input:

left = 0, right = 0

Output:

0

Example 3

Input:

left = 1, right = 2147483647

Output:

0

Constraints

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

Approach and Intuition

  1. Understand how bitwise AND operation works:

    • Given two numbers, bitwise AND operation is performed at the bit-level, aligning the numbers by their least significant bits.
    • For each pair of bits in the aligned positions, if both bits are 1, the result for that bit position is 1; otherwise, it is 0.

  2. Recognize the problem with expansive ranges:

    • If right is significantly larger than left, the number of operations can grow large, making a direct computation inefficient.
    • For wide ranges, particularly when they across power of two boundaries, the result approaches 0 because the higher order bits diverge and do not satisfy the AND condition of being 1 simultaneously.

  3. Implementation insights from examples:

    • Example 1 (left = 5, right = 7): Direct computational approach yields the result efficiently since the range is small. The bitwise AND of 5 (101_2), 6 (110_2), and 7 (111_2) results in 4 (100_2).
    • Example 2 (left = 0, right = 0): With only one number in the range, the result is the number itself, as there is no other number to AND with.
    • Example 3 (left = 1, right = 2147483647): Given the maximum possible range of integers, the result converges quickly towards zero, because it is improbable for all bits across such a vast range to be 1 simultaneously.

  4. Optimal strategy:

    • Observe that the result is mainly dependent on the common leftmost bits of left and right.
    • Shift both left and right rightwards until they are equal. Each shift represents a lose of a differing bit starting from the least significant bit.
    • Once they are equal, shifting the result leftwards by the same number of shifts gives the final result. This left shift sets the lost varying bits to zero, which aligns with the behavior of the AND operation across the specified range.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int bitwiseAndOfRange(int low, int high) {
        while (low < high) {
            high = high & (high - 1);
        }
        return high;
    }
};

The provided solution in C++ addresses the problem of finding the bitwise AND of all numbers between two integers, low and high. The function bitwiseAndOfRange employs an efficient approach to solve the problem by iteratively reducing the value of high using the expression high & (high - 1). This operation effectively strips the least significant bit from high. The loop continues until low is no longer less than high.

The technique used ensures that the process stops as soon as high equals low or when all bits that differ between low and high have been stripped off, leaving only the common prefix of the binary representations of low and high. The remaining number is the bitwise AND of all numbers in the range. The final result is returned by the function. This method greatly reduces the number of operations required compared to a naive approach that might involve iterating over the entire range.

java 
class Solution {
    public int bitwiseAndInRange(int low, int high) {
        while (low < high) {
            // Clear the least significant bit set
            high = high & (high - 1);
        }
        return high;
    }
}

This Java solution addresses the problem of finding the bitwise AND of all numbers between two integers, low and high. The function bitwiseAndInRange continues to modify high by clearing the least significant bit set, accomplished by applying the operation high & (high - 1), until high becomes less than or equal to low. The approach effectively zeroes out the bits that differ between low and high, finding the common bit prefix of all numbers in the range. The function then returns the modified high, which now represents the bitwise AND of the number range.

python 
class Solution:
    def bitwiseANDInRange(self, lower: int, upper: int) -> int:
        while lower < upper:
            upper = upper & (upper - 1)
        return upper

This Python3 solution to the problem of finding the bitwise AND of a range of numbers involves a class named Solution with a method bitwiseANDInRange. This method takes two integers, lower and upper, as input arguments, representing the bounds of the range. The bitwise AND operation is performed progressively from the upper bound downwards by using a loop that continues while the lower bound is less than the upper bound.

Inside the loop, the code repeatedly performs two operations on the upper variable:

  • Subtract 1 from upper.
  • Perform a bitwise AND between the result and the original upper value.

This effectively clears the least significant bit of upper repeatedly until upper is no longer greater than lower. The loop strategically reduces the upper bound to decrease the range and converge the result towards the bitwise AND of all numbers between the original lower and upper bounds. Once the loop completes, the upper variable, now having converged to the result of the bitwise AND operation across the range, is returned.

Comments

No comments yet.