Hamming Distance Solutions & Complexity

1. Define the problem

Hamming Distance

The Hamming distance between two integers is the number of positions at which their corresponding bits differ . Given two integers x and y, return the Hamming distance between them. XOR x and y first — the result has a 1 exactly where the bits differ — then count that XOR's set bits.

Constraints

0 ≤ x, y ≤ 2³¹ - 1

Example

Inputx = 1, y = 4

Output2

Explanation 1 = 0001 and 4 = 0100 differ in two bit positions.

2. Know the words first

In plain terms

Hamming distance: How many bit positions differ between two numbers of the same width.

3. Visualize the solution

XOR the two numbers, then count the set bits

Statusinit

x = 0001, y = 0100. Compute diff = x ^ y.

What happens in this step

x = 1, y = 4
  x = 00000001
  y = 00000100

Set up to XOR x and y — every bit position where they differ will come out as 1 in diff.

Step 1 of 4

Steps to visualize

Compute diff = x ^ y — a 1 wherever the two numbers differ.
Count the set bits in diff using n & (n - 1) to clear the lowest one each round.
The final count is the Hamming distance.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

XOR the two numbers, then count the set bits

Statusinit

x = 0001, y = 0100. Compute diff = x ^ y.

What happens in this step

x = 1, y = 4
  x = 00000001
  y = 00000100

Set up to XOR x and y — every bit position where they differ will come out as 1 in diff.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function hammingDistance(x, y) {
  let diff = x ^ y;
  let count = 0;

  while (diff !== 0) {
    diff &= diff - 1;
    count++;
  }

  return count;
}

Time: O(k), k = number of differing bits
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`x = 1, y = 4`	`2`	example from the docstring
`x = 5, y = 5`	`0`	identical values have no differing bits
`x = 0, y = 2147483647`	`31`	every set bit in a large value counts against zero
`x = 8, y = 0`	`1`	a single differing bit
`x = 0, y = 0`	`0`	smallest valid input, both values zero
`x = 15, y = 240`	`8`	two values whose bits are complete opposites within a byte

Hamming Distance