Hamming Distance
Understanding the Problem
We need to count how many bit positions differ between two integers. Lining up the binary representations of x and y, the Hamming distance is the number of positions where one has a 1 and the other has a 0.
XOR (^) produces exactly this count of disagreements. XOR of two bits is 1 if and only if the bits differ, so x ^ y produces a number whose 1 bits sit at every position where x and y disagree. The problem reduces to counting the 1 bits in x ^ y, also called the popcount or population count.
Key Constraints:
0 <= x, y <= 2^31 - 1→ Both values are non-negative and fit in a 32-bit signed integer. Since the sign bit stays 0,x ^ yis also non-negative, so right shifts and thexor - 1trick below behave predictably and the answer is at most 31.
Approach 1: Bit-by-Bit Comparison
Intuition
Count the differing bits by inspecting x ^ y one bit at a time. Right-shift the XOR result by one position each iteration and test the least significant bit with xor & 1. Adding that bit to a running counter accumulates the total number of set bits. The loop stops once xor becomes 0, so it examines at most 31 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 inspects every bit position, including the zeros. The next approach skips the zero bits and touches only the set bits, so its loop count drops from 31 to the number of differing bits.
Approach 2: Brian Kernighan's Algorithm (Optimal)
Intuition
The expression n & (n - 1) clears the lowest set bit of n. Subtracting 1 flips the lowest set bit from 1 to 0 and turns every bit below it from 0 to 1. ANDing that result with the original n keeps the higher bits unchanged and zeroes out the lowest set bit along with everything beneath it, so exactly one 1 bit disappears.
Instead of inspecting all 31 positions, repeatedly clear the lowest set bit and count how many times before xor reaches zero. If only 2 of the 31 bits are set, the loop runs twice rather than 31 times.
Each iteration removes exactly one set bit and leaves the rest in place, so the loop terminates after as many steps as there are set bits in xor. That count is the number of 1 bits in x ^ y, which equals the number of positions where x and y differ, 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.