Why it works
- Counting from left up to right, a number changes its low bits before its high ones. Below the highest bit where left and right differ, some number in between ends in all zeros (28 = 11100 here), so every such bit is 0 in the AND.
- Above that bit, left and right agree, and every number between them has the same bits there, so the AND keeps them. Shifting both right until they are equal finds exactly that shared start.
- Shifting back by shift puts the start in its place and fills the dropped columns with zeros. The numbers between left and right are never read, so the range may be as long as you like.
Complexity
Time O(log right): one shift per bit, at most 31 on LeetCode. Memory O(1): three numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗