Hamming Distance
Maintained by Vikas D, software engineer
You are given two non-negative integers, x and y. Write their values in binary and line them up by position. The Hamming distance is the count of positions where one number has a 1 and the other has a 0.
Positions where both bits agree (both 0 or both 1) do not contribute. Only the disagreements are counted, so the answer is always between 0 and the number of bits in the larger value.
Return that count as an integer. The order of the two arguments does not matter, since a position either differs or it does not.
Examples
1 is 001 and 4 is 100. The lowest bit and the highest bit disagree, while the middle bit agrees, so two positions differ.
3 is 011 and 1 is 001. Only the middle bit disagrees, so the distance is 1.
15 is 1111 and 0 is 0000. All four of the lowest bits disagree, so the distance is 4.
Constraints
- 0 <= x, y <= 2^31 - 1
- Both inputs are non-negative integers, so no sign bits are involved.
Visible test cases
- hammingDistance(1, 4) == 2
- hammingDistance(3, 1) == 1
- hammingDistance(0, 0) == 0
- hammingDistance(15, 0) == 4
- hammingDistance(93, 73) == 2
Hints
Hint 1
Two bits differ exactly when they are not equal. Think about an operation that turns equal bits into 0 and unequal bits into 1.
Hint 2
XOR (x ^ y) produces a number whose set bits mark precisely the positions where x and y disagree. The problem now reduces to counting the set bits of one number.
Hint 3
To count set bits quickly, repeatedly clear the lowest set bit with n & (n - 1) and tally how many times you can do it before reaching 0.
Approaches
XOR then check every bit
Time O(b) where b is the bit width (32 here) · Space O(1)XOR the two numbers so the differing positions become 1s, then walk all bit positions and count how many 1s appear.
- Compute diff = x ^ y.
- Loop a fixed number of times (32 for a 31-bit range), shifting diff right by one each pass.
- Add the lowest bit (diff & 1) to a running count on every pass.
- Return the count after the loop finishes.
XOR then clear lowest set bit (Brian Kernighan)
Time O(k) where k is the number of differing bits · Space O(1)After XOR, only the differing bits are set, so counting set bits gives the answer. Clearing the lowest set bit each step runs once per set bit instead of once per position.
- Compute diff = x ^ y.
- While diff is not zero, run diff = diff & (diff - 1), which removes the lowest set bit.
- Increment a counter on each removal.
- Return the counter once diff reaches 0.
Common mistakes
- Comparing the numbers directly (x - y or x == y) instead of comparing them bit by bit. The answer depends on positions, not magnitude.
- Forgetting that the loop variable for the position-scan version must cover the full bit width; stopping early misses high bits of large inputs.
- Counting agreeing bits rather than disagreeing ones, which inverts the result.
- Assuming the inputs have the same number of binary digits. Pad the shorter value conceptually with leading zeros; XOR handles this automatically.
Follow-up variations
- Compute the total Hamming distance summed over every pair in an array of integers, ideally without checking all pairs explicitly.
- Extend the idea to the Hamming distance between two equal-length strings instead of integers.
- Handle very large numbers that exceed a machine word, where you cannot rely on fixed-width bit operations.
- Given a target distance d, count how many integers in a range sit exactly d bits away from a fixed value.