Hamming Distance

Share

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, return the Hamming distance between them.

Example 1
Input: x = 1, y = 4
Output: 2
Explanation: 1 (0001) XOR 4 (0100) = 0101. Two bits differ.
Example 2
Input: x = 3, y = 1
Output: 1
Explanation: 3 (011) XOR 1 (001) = 010. One bit differs.

Solution Approach

XOR of x and y produces a number where each 1-bit represents a position where x and y differ. Count the number of 1-bits in the XOR result using the n & (n-1) trick or Java's built-in Integer.bitCount.

  • Compute xor = x ^ y. Each set bit in xor indicates a differing position.
  • Count the 1-bits in xor using Integer.bitCount or a manual loop.
  • Return the count.
Java
class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor != 0) {
            xor &= (xor - 1); // clear lowest set bit
            count++;
        }
        return count;
    }
}
Complexity Analysis:

Time complexity: O(1). Bounded by the number of set bits (at most 32).
Space complexity: O(1). Constant extra space.