Sponsored
Sponsored
This approach involves reducing the problem to finding a common ancestor in the binary tree representation of the numbers. When calculating the bitwise AND for numbers between left and right, we repeatedly right shift both numbers until they become equal, which means they share the same common prefix. The result will be left << the number of shifts.
Time Complexity: O(log N), where N is the range defined by right - left.
Space Complexity: O(1), no additional space required.
1function rangeBitwiseAnd(left, right) {
2 let shift = 0;
3 while (left < right) {
4 left >>= 1;
5 right >>= 1;
6 shift++;
7 }
8 return left << shift;
9}
10
11console.log(rangeBitwiseAnd(5, 7)); // Output: 4JavaScript Explanation:In JavaScript, this function performs bitwise operations similarly to other languages and logs the result using console.
In this approach, we find the common prefix of the binary representations of the numbers in the range. This is achieved by continually shifting the left and right numbers until they become equal. The remaining value after shifting is the common prefix, which gives the result after reversing the shifts.
Time Complexity: O(log N), where N is the range between left and right, depending on how many bits need to be cleared.
Space Complexity: O(1).
class MainClass {
public static int RangeBitwiseAnd(int left, int right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
public static void Main(string[] args) {
Console.WriteLine(RangeBitwiseAnd(5, 7)); // Output: 4
}
}C# Explanation: The C# version also uses a class to encapsulate the logic within a static method.