Hamming Distance

easy bit manipulation

Problem

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.

Inputx = 1, y = 4

Output2

1 = 0001, 4 = 0100. Bits at positions 0 and 2 differ.

def hamming_distance(x, y):
    z = x ^ y
    count = 0
    while z:
        z &= z - 1
        count += 1
    return count

function hammingDistance(x, y) {
  let z = x ^ y;
  let count = 0;
  while (z) {
    z &= z - 1;
    count++;
  }
  return count;
}

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

Explanation

The Hamming distance is just the count of bit positions where x and y disagree. The clean way to spot those positions is to compute z = x ^ y: XOR puts a 1 exactly where the two bits differ and a 0 where they match.

So now the problem reduces to counting the 1 bits in z (its popcount). The Python solution does this with a neat trick: z &= z - 1 clears the lowest set bit each time, and we count how many times we can do that before z becomes 0.

Why does z & (z - 1) remove the lowest 1? Subtracting one flips that lowest set bit to 0 and turns the zeros below it into ones; ANDing with the original wipes out exactly that one bit. Each loop pass removes one set bit, so the loop runs once per differing position.

Example: x = 1 (0001), y = 4 (0100). Then z = 0101, which has two set bits, so the answer is 2.

Because each step deletes a set bit, the work depends only on how many bits differ, not on the full width of the integer.

Time: O(k) where k is the number of set bits in x⊕y Space: O(1)