Bitwise AND Across a Range
Problem
A network tool needs the widest mask shared by a block of consecutive addresses. Given two integers lo and hi with 0 ≤ lo ≤ hi ≤ 2^31 - 1, return the bitwise AND of every integer from lo to hi, inclusive. The range can hold about two billion numbers, so looping over it is far too slow.
Examples
Input: lo = 5, hi = 7
Output: 4
Why: 101 & 110 & 111 = 100Input: lo = 12, hi = 15
Output: 12
Why: 1100 through 1111 all share the prefix 11, and the low two bits take every valueInput: lo = 1, hi = 2147483647
Output: 0
Why: edge case, the range crosses a power of two, so no bit survivesHints
0 / 3
Look at any bit position below the highest bit where lo and hi differ. Counting up from lo to hi passes through a number where that bit is 0.
So the answer is the common binary prefix of lo and hi, followed by zeros.
Shift both numbers right until they are equal, counting the shifts, then shift the shared value back left by that count.
Solution
Take the highest bit where lo and hi differ: lo has a 0 there and hi has a 1, so the range contains the number with that 1 followed by all zeros, and the number just before it with that 0 followed by all ones. Between those two, every bit at or below that position is 0 in at least one number, so all of them vanish from the AND. Bits above it are the same in lo and hi, and since every number in between lies between them, those bits are shared by the whole range. The answer is therefore the common prefix of lo and hi padded with zeros, found by shifting both right until they match. That takes at most 31 shifts, so time and space are O(1).
def range_and(lo, hi):
shift = 0
while lo != hi: # strip bits until only the shared prefix is left
lo >>= 1
hi >>= 1
shift += 1
return lo << shift # prefix followed by zeros
print(range_and(5, 7)) # -> 4
print(range_and(12, 15)) # -> 12
print(range_and(1, 2147483647)) # -> 0
print(range_and(9, 9)) # -> 9Stuck on the idea rather than the code? Masks and Power of Two covers it.