Medium Bit Shift Bit Manipulation
In plain English: AND all integers from m to n together. Find the result without looping through every number.
Any bit that flips between m and n will become 0 in the AND. Shift both right until they match — the common prefix is the answer, shifted back.
Prompt
Given a range [m, n] where 0 <= m <= n, return the bitwise AND of all numbers in this range.
Try to write it from scratch before scrolling down.
Solution
def range_bitwise_and(m, n):
shift = 0
while m != n:
m >>= 1
n >>= 1
shift += 1 # count how many bits differ
return m << shift # common prefix, shifted back
# Test: range_bitwise_and(5, 7) == 4 (101 & 110 & 111 = 100)
# Test: range_bitwise_and(0, 0) == 0
# Test: range_bitwise_and(1, 2147483647) == 0