Description
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
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: 0Solution in Python
To solve the problem of finding the bitwise AND of all numbers in the given range [left, right], we need to understand how the bitwise AND operation works across multiple numbers.
Key Insight:
When we perform a bitwise AND operation across multiple consecutive numbers, the result will only retain the common bits that are the same in all those numbers. If any bit position differs among the numbers in the range, that bit will be set to 0 in the result.
Approach:
- Shift the Range: The idea is to keep shifting both
leftandrightto the right until they are equal. Every time we shift, we essentially remove the bits that differ betweenleftandright. - Track the Shifts: We need to keep track of how many shifts we perform because we will need to shift the result back to the left by the same amount to get the final answer.
- Return the Result: Once
leftequalsrightafter shifting, the bits that remain inleft(orright, since they are now equal) represent the common bits in the original range. Shift these bits back to their original position to obtain the result.
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
# Initialize a counter for the number of shifts
shift_count = 0
# Shift left and right to the right until they are equal
while left < right:
left >>= 1 # Shift left to the right by 1 bit
right >>= 1 # Shift right to the right by 1 bit
shift_count += 1 # Increment the shift counter
# Once left equals right, shift back to the left by shift_count to get the result
return left << shift_countExample Walkthrough:
For left = 5 and right = 7:
- Binary of
5is101 - Binary of
6is110 - Binary of
7is111
- After 1st shift:
leftbecomes2(from5->101to10)rightbecomes3(from7->111to11)
- After 2nd shift:
leftbecomes1(from2->10to1)rightbecomes1(from3->11to1)
Now left equals right, and the remaining bits in left (which is 1) represent the common prefix. After shifting it back by 2 (the number of shifts), the result is 4 (which is 100 in binary).
This approach efficiently computes the bitwise AND for large ranges without iterating through all the numbers.
Solution in Javascript
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
var rangeBitwiseAnd = function(left, right) {
// Initialize a counter for the number of shifts
let shiftCount = 0;
// Shift left and right to the right until they are equal
while (left < right) {
left >>= 1; // Shift left to the right by 1 bit
right >>= 1; // Shift right to the right by 1 bit
shiftCount++; // Increment the shift counter
}
// Once left equals right, shift back to the left by shiftCount to get the result
return left << shiftCount;
};Solution in Java
class Solution {
public int rangeBitwiseAnd(int left, int right) {
// Initialize a counter for the number of shifts
int shiftCount = 0;
// Shift left and right to the right until they are equal
while (left < right) {
left >>= 1; // Shift left to the right by 1 bit
right >>= 1; // Shift right to the right by 1 bit
shiftCount++; // Increment the shift counter
}
// Once left equals right, shift back to the left by shiftCount to get the result
return left << shiftCount;
}
}Solution in C#
public class Solution {
public int RangeBitwiseAnd(int left, int right) {
// Initialize a counter for the number of right shifts
int shiftCount = 0;
// Keep shifting left and right to the right until they are equal
while (left < right) {
left >>= 1; // Right shift the left boundary by 1 bit
right >>= 1; // Right shift the right boundary by 1 bit
shiftCount++; // Increment the shift counter
}
// Shift left back to the left by shiftCount to get the result
return left << shiftCount;
}
}