Hamming distance between two integers

Question

The Hamming distance between two integers is the number of bit positions where they differ.

a = 1  (0001)
b = 4  (0100)
-> 2      # they differ in two positions

Return the Hamming distance of a and b in time proportional to the number of differing bits, not the full word width.

Accepted Answer

Two numbers differ in exactly the positions where their XOR is 1, so a ^ b marks every disagreement and the answer is that value's popcount. Count those bits with Kernighan's loop: x &= x - 1 clears the lowest set bit each pass, so the loop runs once per differing bit, not once per bit position. Tracing a = 1, b = 4: x = 5 = 0b101. First pass 5 & 4 = 4, count 1. Second pass 4 & 3 = 0, count 2. Loop ends, answer 2. Time O(	ext{number of set bits}), at most the word width; space O(1). Takeaway. XOR turns "where do these differ" into a set of 1-bits, and Kernighan's x & (x - 1) counts them in o…

Hamming distance between two integers

Your answer

More Coding questions