Hamming Distance
Last Updated: March 29, 2026
Understanding the Problem
We need to count how many bit positions differ between two integers. If you line up the binary representations of x and y, the Hamming distance is simply the number of spots where one has a 1 and the other has a 0.
The key observation is that XOR (^) gives us exactly what we need. When you XOR two bits, the result is 1 if and only if the bits are different. So x ^ y produces a number where each 1 bit represents a position where x and y disagree. The problem reduces to counting the number of 1 bits in x ^ y, which is also known as the "popcount" or "population count."
Key Constraints:
0 <= x, y <= 2^31 - 1→ Both values fit in a 32-bit signed integer. The maximum number of differing bits is 31 (since the sign bit is always 0 for non-negative values up to 2^31 - 1).- Only two integer inputs → No array iteration needed. The problem is purely about bit manipulation.
Approach 1: Bit-by-Bit Comparison
Intuition
The most straightforward way to count differing bits is to compare x and y one bit at a time. We XOR them together, then walk through every bit of the result, counting the ones.
How do we check each bit? We can right-shift the XOR result by one position in each iteration and check whether the least significant bit is 1. Alternatively, we can use a bitmask that shifts left. Either way, we examine all 31 possible bit positions.
Algorithm
- Compute
xor = x ^ y. This marks every position where the two inputs differ. - Initialize a counter
count = 0. - While
xoris not zero: - If the last bit of
xoris 1 (check withxor & 1), incrementcount. - Right-shift
xorby 1 to move to the next bit. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(k) where k is the number of bits (at most 31). We shift through every bit until the value becomes zero. Since k is bounded by 31, this is effectively O(1).
- Space Complexity: O(1). Only a couple of integer variables are used.
This approach checks every bit position, even the zeros. What if we could skip the zero bits entirely and jump directly from one set bit to the next?
Approach 2: Brian Kernighan's Algorithm (Optimal)
Intuition
Here's a beautiful trick: n & (n - 1) clears the lowest set bit of n. When you subtract 1 from a number, all the bits below the lowest set bit flip from 0 to 1, and the lowest set bit itself flips from 1 to 0. ANDing with the original number zeroes out everything at and below the lowest set bit.
So instead of checking every bit one by one, we can repeatedly clear the lowest set bit and count how many times we do it before the number reaches zero. Each iteration removes exactly one 1 bit, so we loop exactly as many times as there are set bits. If only 2 out of 31 bits are set, we loop just twice.
The trick exploits how binary subtraction works. Subtracting 1 from any number flips the lowest set bit to 0 and all the bits below it to 1. ANDing with the original number zeroes out everything at and below the lowest set bit, effectively "peeling off" one 1 bit per iteration. Since we loop exactly once per set bit, the total iterations equal the Hamming weight of x ^ y, which is the Hamming distance.
Algorithm
- Compute
xor = x ^ y. - Initialize
count = 0. - While
xoris not zero: - Apply
xor = xor & (xor - 1)to clear the lowest set bit. - Increment
count. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(k) where k is the number of set bits in
x ^ y(at most 31). We loop exactly as many times as there are1bits. In the best case (identical inputs), we loop zero times. - Space Complexity: O(1). Only a couple of integer variables.