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).
Java Explanation: This snippet implements the same approach in a Java static method.