
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
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 is1
; otherwise, it is0
.
Recognize the problem with expansive ranges:
- If
right
is significantly larger thanleft
, 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 being1
simultaneously.
- If
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 of5 (101_2)
,6 (110_2)
, and7 (111_2)
results in4 (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 be1
simultaneously.
- Example 1 (
Optimal strategy:
- Observe that the result is mainly dependent on the common leftmost bits of
left
andright
. - Shift both
left
andright
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.
- Observe that the result is mainly dependent on the common leftmost bits of
Solutions
- C++
- Java
- Python
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.
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.
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
fromupper
. - 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.
No comments yet.