Community Problem
Hamming Distance
Difficulty: Easy
Count the bit positions where two non-negative integers differ using XOR plus a population-count loop.
Hamming Distance
Count the bit positions where two non-negative integers differ using XOR plus a population-count loop.
By @freyadiallo
May 17, 2026
·
Updated May 18, 2026
870 views
25
4.2 (12)
I had this on a Cisco networking team interview, where they cared about the answer because the same trick shows up in error-correcting codes. Two operations only: XOR the inputs to mark differing bits, then popcount the result. The interviewer was specifically NOT looking for a 32-iteration loop checking each bit; they wanted Brian Kernighan's trick that runs in time proportional to the number of set bits.
Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.
Examples
Example 1:
- Input:
x = 1, y = 4 - Output:
2 - Explanation:
1 = 0001,4 = 0100. Two bits differ.
Example 2:
- Input:
x = 3, y = 1 - Output:
1 - Explanation:
3 = 011,1 = 001. One bit differs.
Example 3:
- Input:
x = 0, y = 0 - Output:
0 - Explanation: Identical inputs differ in zero bits.
Example 4:
- Input:
x = 0, y = 2147483647 - Output:
31 - Explanation:
0vs0x7FFFFFFFdiffers in 31 bits.
Constraints
0 <= x, y <= 2^31 - 1.
Follow-up
Why XOR? (x ^ y) has a 1 in every position where x and y differ, so the Hamming distance equals the number of set bits in the XOR. Brian Kernighan's n &= n - 1 clears the lowest set bit per iteration, giving O(popcount) instead of O(32).
Solution
Hints
Solution Walkthrough
Approach: XOR + Brian Kernighan Popcount (O(k) time, O(1) space)
Split the problem into two well-known primitives. First, x ^ y produces a bitmask z whose 1 bits mark every position where x and y differ. Second, count the set bits of z using Brian Kernighan's trick: z &= z - 1 clears the lowest set bit per iteration. The loop runs exactly k = popcount(z) times, where k is the answer; on uniform random 32-bit inputs that's about 16, never more than 32.
Key Insight
XOR marks differing bits
x = 0001
y = 0100
z = 0101 two ones, hamming distance is 2
Brian Kernighan iteration on z = 0101
step 1: z & (z - 1) = 0101 & 0100 = 0100 count = 1
step 2: z & (z - 1) = 0100 & 0011 = 0000 count = 2
loop exitsAlgorithm
- Compute
z = x ^ y. - While
z != 0: setz = z & (z - 1)and increment the counter. - Return the counter.
Why It Works
z & (z - 1) clears exactly the lowest set bit of z, leaving all higher bits untouched. The loop terminates when z reaches zero, which happens after exactly popcount(z) iterations. The XOR step is a clean reduction from "compare two integers" to "count set bits in one integer".
Complexity
Metric Value
Time O(k) k = number of differing bits, at most 32
Space O(1)Most runtimes expose a built-in popcount: JavaScript can use (z >>> 0).toString(2).match(/1/g)?.length || 0 (slower but obvious), and Python has bin(z).count('1') or z.bit_count() on 3.10+. The hand-written Brian Kernighan loop is the standard interview answer because it works in any language and demonstrates the bit-manipulation idea.
Pitfalls
- Looping 32 times unconditionally. Works but signals you don't know the popcount trick. Brian Kernighan is strictly better.
- Forgetting that the inputs are non-negative. No sign-extension worries here, but if the constraint changed to allow negatives, you'd want unsigned right shift in JS (
>>> 0). - Using
Math.abs(x - y)or differences. Hamming distance is a BIT count, not a numeric difference.1 vs 4has Hamming distance 2, not 3. - Reaching for a string conversion.
bin(x ^ y).count('1')is fine in Python but slower; in JS the regex approach allocates. The bit loop is cheaper.
Solution Code