Hamming Distance

Bit Manipulation

10 min

Problem Statement

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

Example 1:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
The arrows point to the positions where the corresponding bits are different.

Solution (XOR + Bit Counting)

The Hamming distance is equivalent to the number of set bits (1s) in the result of XORing the two numbers. The XOR operation x ^ y will produce a number where a bit is 1 only if the corresponding bits in x and y are different.

Algorithm Steps

First, calculate the XOR of x and y. Let's call this xor_result.
Initialize a distance counter to 0.
While xor_result is not 0, repeatedly do the following:
Use the trick xor_result & (xor_result - 1) to clear the least significant set bit.
Increment the distance counter.
The final distance is the Hamming distance.

00000001

00000100

XOR Result

00000101

Counting Set Bits...

00000101

Distance: 0

Calculate XOR: 00000001 ^ 00000100 = 00000101

Hamming Distance Solution


class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor_result = x ^ y
        distance = 0
        while xor_result > 0:
            # Clear the least significant bit
            xor_result &= (xor_result - 1)
            distance += 1
        return distance