LeetCode 461: Hamming Distance

Problem Restatement

We are given two integers x and y.

We need to return the Hamming distance between them.

For two integers, the Hamming distance is the number of bit positions where their binary representations are different. The official problem asks us to return the Hamming distance between two integers x and y.

For example:

x = 1
y = 4

Their binary forms are:

1 = 0001
4 = 0100

They differ in two positions:

0001
0100
 ^ ^

So the answer is:

2

Input and Output

Function shape:

def hammingDistance(x: int, y: int) -> int:
    ...

Examples

Example 1:

x = 1
y = 4

Binary:

1 = 0001
4 = 0100

Different positions:

0001
0100
 ^ ^

Answer:

2

Example 2:

x = 3
y = 1

Binary:

3 = 0011
1 = 0001

Only one bit differs:

0011
0001
  ^

Answer:

1

Example 3:

x = 0
y = 0

Both numbers have the same binary representation.

Answer:

0

First Thought: Compare Bits One by One

A direct approach is to inspect every bit position.

Since the constraints fit inside 31 bits, we can check bits from 0 to 30.

For each bit position, extract the bit from x and y.

If they differ, increment the answer.

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

        for bit in range(31):
            bit_x = (x >> bit) & 1
            bit_y = (y >> bit) & 1

            if bit_x != bit_y:
                distance += 1

        return distance

This works because the Hamming distance is exactly the count of positions where the two bits differ.

Problem With Manual Bit Comparison

The bit-by-bit approach is already efficient because there are only 31 relevant bits.

But the code is more verbose than needed.

There is a bit operation that directly marks all different positions: XOR.

Key Insight

XOR has the exact behavior we need.

For each bit:

So x ^ y has 1 exactly at positions where x and y differ.

Then the answer is the number of 1 bits in x ^ y.

For example:

x = 1      # 0001
y = 4      # 0100
x ^ y = 5  # 0101

The result 0101 has two 1 bits.

So the Hamming distance is:

2

Algorithm

Compute:

diff = x ^ y

Then count the number of set bits in diff.

In Python, this can be done directly:

diff.bit_count()

Return that count.

Correctness

For every bit position, XOR returns 1 exactly when the two input bits are different.

Therefore, after computing:

diff = x ^ y

the number of 1 bits in diff equals the number of bit positions where x and y differ.

The Hamming distance is defined as exactly that count.

So returning the number of set bits in x ^ y gives the correct answer.

Complexity

For arbitrary-size integers, the time depends on the number of machine words used to store the integers.

Implementation

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return (x ^ y).bit_count()

Code Explanation

The expression:

x ^ y

creates a number whose 1 bits mark the positions where x and y are different.

Then:

.bit_count()

counts how many 1 bits that number has.

That count is the Hamming distance.

Alternative Implementation Without bit_count

Some languages or older Python versions may not have bit_count.

We can count set bits manually using Brian Kernighan’s trick.

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

        while diff:
            diff &= diff - 1
            distance += 1

        return distance

The operation:

diff &= diff - 1

removes the lowest set bit from diff.

So the loop runs once per 1 bit.

Testing

def run_tests():
    s = Solution()

    assert s.hammingDistance(1, 4) == 2
    assert s.hammingDistance(3, 1) == 1
    assert s.hammingDistance(0, 0) == 0
    assert s.hammingDistance(0, 7) == 3
    assert s.hammingDistance(15, 0) == 4
    assert s.hammingDistance(8, 8) == 0
    assert s.hammingDistance(2**31 - 1, 0) == 31

    print("all tests passed")

run_tests()

Test meaning: