Count the bit positions where two numbers differ: XOR marks every difference, then clear the lowest set bit until none are left.
▼The problem
LeetCode 461 (Easy). Given two integers x and y, return the Hamming distance between them: the number of bit positions where their binary forms differ.
Examples (LeetCode's): x = 1, y = 4 → 2 (0001 vs 0100) and x = 3, y = 1 → 1 (0011 vs 0001).
The solution
def hamming_distance(x, y):
n = x ^ y
count = 0
while n:
n &= n - 1
count += 1
return countTranscript
Hamming Distance. Given two integers, x and y, count the bit positions where they differ. It's spot the difference, in binary.
Take one and four. One is zero, zero, zero, one. Four is zero, one, zero, zero. They differ in two spots, so the answer is two. Three and one differ in just one spot: the answer is one.
The slow way: turn both numbers into binary strings, pad them to the same length, and compare them character by character. With thirty-two bit integers, that's thirty-two checks, even when only one bit differs.
The key idea is XOR. It gives a one wherever the two bits disagree, and a zero wherever they match. So x XOR y is a map of every difference: here, zero, one, zero, one. Now just count its ones. Brian Kernighan's trick: n AND n minus one clears the lowest one bit, so the loop runs once per difference. It's Single Number's XOR, then Number of One Bits.
In code, XOR the two numbers. While n is not zero, clear its lowest one bit and add one to the count. Then return the count.
Back to one and four. XOR gives five: zero, one, zero, one. Five AND four is four: the lowest difference is gone, count one. Four AND three is zero: count two. Nothing left, so the distance is two.
The loop runs once per differing bit, at most thirty-two times: constant time for a fixed-size integer, and constant space.
XOR finds the differences, Kernighan counts them. That's Hamming Distance.