Hamming Distance: XOR and Bit Counting

LeetCode Hamming Distance (Problem 461) asks you to find the number of positions where the corresponding bits of two integers are different. Given two integers x and y, return the Hamming distance between them.

For example, x = 1 and y = 4. In binary, 1 is 0001 and 4 is 0100. They differ at bit positions 0 and 2, so the Hamming distance is 2.

The problem

You are given two integers x and y. Count how many bit positions differ between their binary representations. That count is the Hamming distance.

Why this problem matters

Hamming distance shows up everywhere in computer science. Error-correcting codes use it to measure how many bits flipped during transmission. Similarity hashing uses it to compare fingerprints. And in interviews, it is a clean test of whether you understand XOR and bit counting.

The problem is small enough that brute-forcing works, but the elegant solution teaches you two bit manipulation primitives that appear in dozens of other problems.

The key insight

XOR (^) compares two numbers bit by bit. It outputs 1 wherever the bits differ and 0 wherever they match. So x ^ y gives you a number whose 1-bits mark exactly the positions where x and y disagree.

Once you have the XOR result, the problem reduces to counting 1-bits. You already know how to do that: Brian Kernighan's trick. Each n & (n - 1) operation clears the lowest set bit, so you loop until n reaches 0 and count how many iterations it took.

Two primitives, one after the other. XOR marks the differences, then Kernighan counts them.

The code

def hammingDistance(x, y):
    return bin(x ^ y).count('1')

That one-liner is perfectly valid in Python. XOR the two numbers, convert to a binary string, and count the '1' characters.

If you want to show the bit-level approach (which interviewers often prefer), here is the Kernighan version:

def hammingDistance(x, y):
    xor = x ^ y
    count = 0
    while xor:
        xor &= xor - 1
        count += 1
    return count

Both solutions produce the same result. The Kernighan version runs in O(k) where k is the number of set bits, not the total number of bits.

Why this works

XOR has a simple truth table: it outputs 1 only when the two input bits are different. When you compute x ^ y, every 1 in the result corresponds to a position where x and y disagree. Every 0 means they agree. So the number of 1-bits in x ^ y is exactly the Hamming distance.

Brian Kernighan's trick works because subtracting 1 from a number flips all the bits from the lowest set bit downward. When you AND the original number with n - 1, the lowest set bit gets cleared and everything above it stays the same. Each iteration removes exactly one 1-bit, so the loop count equals the popcount.

Visual walkthrough

Let's trace through x = 1, y = 4 step by step. Watch how XOR isolates the differing bits, then Kernighan's trick counts them.

Complexity analysis

The XOR operation is O(1). The Kernighan loop runs once per set bit in the XOR result. In the worst case, all 32 bits differ, so k is at most 32 for standard integers. The bin().count('1') version is also O(1) for fixed-width integers since the binary string has at most 32 characters.

No extra data structures are needed. You use a single variable for the XOR result and a counter.

Building blocks

XOR marks differences. x ^ y produces a 1-bit at every position where x and y differ. This property makes XOR the go-to operation for comparing bits. You will see it again in Single Number, Missing Number, and many other problems.

Brian Kernighan's bit clearing trick. n & (n - 1) removes the lowest set bit from n. Instead of checking all 32 bits, you only visit the bits that are actually set. For sparse bit patterns, this is much faster than a full scan.

XOR is its own inverse. a ^ b ^ b = a. This self-canceling property does not come up directly in Hamming Distance, but understanding it deepens your grasp of why XOR is so useful across bit manipulation problems.

Edge cases

Same number (x = y): x ^ y = 0, which has zero set bits. The Hamming distance is 0. Both numbers have identical binary representations, so no bits differ.

One number is 0: If x = 0, then x ^ y = y. The Hamming distance equals the number of 1-bits in y. You are counting how many bits differ from all-zeros.

Large numbers: The algorithm works for any non-negative integer the language supports. For 32-bit integers, the maximum Hamming distance is 32 (every bit differs). The Kernighan loop handles this cleanly since it only iterates over set bits.

Powers of two: If both x and y are powers of two, the XOR has exactly two set bits (unless they are equal). For example, 2 ^ 8 = 0010 ^ 1000 = 1010, giving a Hamming distance of 2.

From understanding to recall

The mental model here is two steps: XOR to mark, then count the marks. Once that clicks, you can write the code from memory in under a minute.

The recall anchor: "XOR finds where they differ, Kernighan counts how many." If you can retrieve that sentence without thinking, the implementation follows directly.

Practice this problem cold a few times over the next week. Each attempt should start from a blank editor with no references. By the third rep, you should be writing the solution in about 30 seconds.

Related posts

• Number of 1 Bits - Counting set bits with Kernighan's trick
• Single Number - XOR cancellation pattern
• Counting Bits - Systematic bit counting