Hamming Distance

How it works

At each position, XOR the two low bits to determine whether they differ. Add that contribution and shift both values right. Continue until neither value has remaining set bits.

Steps

1. Initialize the distance to zero.
2. Add (x & 1) XOR (y & 1).
3. Shift both values until both are zero.

Complexity

• Time: O(log(max(x, y) + 1)), at most the fixed input bit width.
• Space: O(1).

Things to watch for

• Use XOR to detect different bits.
• Equal inputs have distance zero.
• The problem supplies nonnegative integers.

class Solution:
  def hammingDistance(self, x: int, y: int) -> int:
    ans = 0

    while x > 0 or y > 0:
      ans += (x & 1) ^ (y & 1)
      x >>= 1
      y >>= 1

    return ans

class Solution {
 public:
  int hammingDistance(int x, int y) {
    int ans = 0;

    while (x > 0 || y > 0) {
      ans += (x & 1) ^ (y & 1);
      x >>= 1;
      y >>= 1;
    }

    return ans;
  }
};