LeetCode 461 · Bits · Math

Hamming Distance, explained with a picture

How many switches differ between two panels?.

Bits · Math
▶ Watch it step by step

The problem

Count the positions where two numbers’ bits differ (Hamming distance).

Input:  x = 1, y = 4
Output: 2

Picture it

Picture two switch panels side by side. XOR lights up exactly the positions that differ; then count the lights.

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

The key idea

popcount(x ^ y). O(1).

Python solution

def hamming_distance(x, y):
    diff = x ^ y                    # on where they differ
    count = 0
    while diff:
        diff &= diff - 1            # switch off the lowest on switch
        count += 1
    return count

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.