Hamming Distance
The Hamming distance between two integers is the number of positions at which their corresponding bits differ . Given two integers x and y, return the Hamming distance between them. XOR x and y first — the result has a 1 exactly where the bits differ — then count that XOR's set bits.
Constraints
- 0 ≤ x, y ≤ 231 - 1
Example
Input
x = 1, y = 4Output
2Explanation 1 = 0001 and 4 = 0100 differ in two bit positions.
In plain terms
- Hamming distance
- How many bit positions differ between two numbers of the same width.
XOR the two numbers, then count the set bits
80
40
20
11
Statusinit
x = 0001, y = 0100. Compute diff = x ^ y.
What happens in this step
x = 1, y = 4 x = 00000001 y = 00000100 Set up to XOR x and y — every bit position where they differ will come out as 1 in diff.
Step 1 of 4
Steps to visualize
- Compute diff = x ^ y — a 1 wherever the two numbers differ.
- Count the set bits in diff using n & (n - 1) to clear the lowest one each round.
- The final count is the Hamming distance.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
80
40
20
11
Statusinit
x = 0001, y = 0100. Compute diff = x ^ y.
What happens in this step
x = 1, y = 4 x = 00000001 y = 00000100 Set up to XOR x and y — every bit position where they differ will come out as 1 in diff.
Step 1 of 4
Solution
function hammingDistance(x, y) {
let diff = x ^ y;
let count = 0;
while (diff !== 0) {
diff &= diff - 1;
count++;
}
return count;
}- Time
- O(k), k = number of differing bits
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
x = 1, y = 4 | 2 | example from the docstring |
x = 5, y = 5 | 0 | identical values have no differing bits |
x = 0, y = 2147483647 | 31 | every set bit in a large value counts against zero |
x = 8, y = 0 | 1 | a single differing bit |
x = 0, y = 0 | 0 | smallest valid input, both values zero |
x = 15, y = 240 | 8 | two values whose bits are complete opposites within a byte |