LeetCode 201 · Bits · Math

Bitwise AND of Numbers Range, explained with a picture

Which switches stay on across a whole range?.

Bits · Math
▶ Watch it step by step

The problem

Return the bitwise AND of all numbers from left to right inclusive.

Input:  5 to 7
Output: 4

Picture it

Picture the numbers as switch panels. Any switch that flips somewhere in the range ends up off. Only the common prefix of left and right survives, so shift both right until they are equal, then shift back.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Common binary prefix of left and right. O(log n).

Python solution

def range_bitwise_and(left, right):
    shift = 0
    while left < right:            # strip differing low switches
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.