#461
Hamming Distance
Easy XOR + popcount
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the bit positions where two integers differ.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: in how many positions do the two numbers' bits differ?
Why this works: XOR leaves a 1 exactly where they differ; count those.
Example: x = 1 (0001), y = 4 (0100)
0001 ^ 0100 = 0101 → two 1s → 2✦Hints open one at a time
XOR has a 1 exactly where the bits differ.
Then count the 1-bits of the XOR.
↗Approach
Compute x ^ y and count its set bits with the n & (n - 1) trick (or Integer.bitCount).
</>Solution (Java)
class Solution {
public int hammingDistance(int x, int y) {
int diff = x ^ y, count = 0;
while (diff != 0) {
diff &= diff - 1;
count++;
}
return count;
}
}!Common mistake
Comparing decimal digits instead of bits.
Complexity
- Time: O(1).
- Space: O(1).
