Bitwise AND of Numbers Range
Find the AND of every number in [left, right] by locating the common binary prefix of the two endpoints instead of looping the range.
Open on LeetCode ↗Intuition
The direct approach ANDs every number from left to right one at a time, which times out once the range spans anything large. The insight is that a single bit position can only survive the AND of the whole range if every number in that range agrees on it. But if left and right differ at some bit position, then somewhere between them a number must flip that bit from 1 to 0 (since incrementing eventually clears any bit that isn't part of a shared prefix), and one zero anywhere kills that bit for the whole AND. So the surviving bits are exactly the common prefix that left and right share before they first disagree. Shift both numbers right together until they become equal, counting the shifts, then shift that shared value back left, refilling the low end with zeros -- those bits are guaranteed to have been zeroed by something in the range.
Approach
Shift left and right together until they match
Repeatedly shift both left and right one bit to the right, counting how many shifts it takes, until the two values become equal. While they still differ, that low bit position is not part of the guaranteed-common prefix and cannot survive the AND.
The matching value is the shared prefix
Once left equals right after shifting, that common value represents every high bit both endpoints agree on -- these are the only bits that could possibly be 1 across the entire range.
Shift back left to restore magnitude
Shift the matched prefix left by the same number of positions that were dropped. This puts the surviving bits back where they belong and fills the low positions with zero, since those positions were shown to disagree somewhere in the range and therefore must be zero in the final AND.
Solution & live demo
Edge cases
The while loop never executes (0 shifts), and the answer is simply left (or right), since the range contains only one number.
Any range starting at 0 immediately drives the shared prefix search toward 0 unless right is also 0, since 0 shares no set bits with anything until fully shifted down.
The loop runs at most about 31 times (bounded by the bit width), so this stays O(log(right)) even for the largest possible range.
Shifting continues until both reach 0, giving an answer of 0 -- correct, since some number in a wide range will always zero out any given bit.