Medium · Common Binary Prefix
Understand → Visualise → Practice.
Return the bitwise AND of every integer in the inclusive range `[left,right]`.
Somewhere between left and right every lower bit takes the value 0, so the AND of the range is the common binary prefix of left and right, followed by zeros.
While left < right, shift both right by one and count the shifts.
Shift the common value back left by the same count.
That value is the AND of every integer in the range.
O(log right) time and O(1) space.
Looping over every integer from left to right is far too slow for ranges near 2³¹.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.