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.
1def rangeBitwiseAnd(left, right):
2 shift = 0
3 while left < right:
4 left >>= 1
5 right >>= 1
6 shift += 1
7 return left << shift
8
9print(rangeBitwiseAnd(5, 7)) # Output: 4Python Explanation:The Python implementation is concise and leverages Python's ability to handle bit manipulation directly in a while loop.
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).
1
Python Explanation: Python's logical operations make it straightforward to implement this method.