LeetCode 461 - Hamming Distance

The problem asks us to compute the Hamming distance between two integers. The Hamming distance is defined as the number of bit positions where the two numbers differ in their binary representation. For example, consider x = 1 and y = 4.

leetcodeeasybit-manipulation

LeetCode Problem 461

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the Hamming distance between two integers. The Hamming distance is defined as the number of bit positions where the two numbers differ in their binary representation.

For example, consider x = 1 and y = 4.

Their binary representations are:

  • 1 = 0001
  • 4 = 0100

If we compare the bits position by position:

Position x y Different?
1 1 0 Yes
2 0 0 No
3 0 1 Yes
4 0 0 No

There are exactly two positions where the bits differ, so the Hamming distance is 2.

The input consists of two non-negative integers, x and y. The output is a single integer representing how many bit positions are different.

The constraints tell us that:

  • 0 <= x, y <= 2^31 - 1

This means both integers fit within a standard 32-bit signed integer range. Since the numbers are relatively small in terms of bit length, any solution that processes all bits individually is already efficient enough.

An important observation is that we are not comparing decimal digits or string representations. The comparison must happen at the binary bit level.

Several edge cases are important to consider:

  • When x == y, the answer should be 0 because all bits match.
  • When one number is 0, the answer becomes the number of set bits in the other number.
  • Large values near 2^31 - 1 must still work correctly.
  • Leading zeros do not matter because binary comparison naturally aligns bits by position.

Approaches

Brute Force Approach

A straightforward solution is to compare every bit position one by one.

We can repeatedly examine the least significant bit of both numbers using bitwise AND:

x & 1
y & 1

If these bits differ, we increment the answer.

After checking the current bit, we shift both numbers right by one position and continue until all bits have been processed.

Since integers are at most 31 bits long under the constraints, this approach works efficiently enough.

The brute-force method is correct because every bit position is explicitly checked exactly once. If two corresponding bits differ, that contributes exactly one to the Hamming distance.

Optimal Approach

The key insight comes from the XOR operation.

Recall the behavior of XOR:

Bit A Bit B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

Notice that XOR produces 1 exactly when the bits are different.

Therefore:

x ^ y

creates a number where every set bit represents a differing bit position.

After computing the XOR, the problem reduces to counting how many set bits are present.

We can count set bits efficiently using Brian Kernighan’s algorithm:

n = n & (n - 1)

This operation removes the lowest set bit from the number. Repeating this process counts all set bits efficiently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(32) O(1) Checks every bit position individually
Optimal O(k) O(1) Uses XOR and removes one set bit per iteration

Here, k represents the number of set bits in x ^ y.

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the XOR of x and y.
difference = x ^ y

XOR produces 1 wherever the bits differ and 0 wherever they match. 2. Initialize a counter variable.

distance = 0

This variable will track how many differing bit positions exist. 3. While the XOR result is not zero, repeatedly remove the lowest set bit.

difference = difference & (difference - 1)

This operation removes exactly one set bit from the number. 4. Increment the counter after each removal.

Since each iteration removes one set bit, the number of iterations equals the number of differing bits. 5. Continue until the XOR result becomes zero.

At that point, all differing bits have been counted. 6. Return the counter as the final Hamming distance.

Why it works

The correctness comes from two properties:

  1. x ^ y produces 1 exactly at positions where the bits differ.
  2. n & (n - 1) removes exactly one set bit from n.

Therefore, repeatedly applying the second operation counts exactly how many differing bit positions exist between x and y.

Python Solution

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

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

        return distance

The implementation begins by computing the XOR of x and y. This isolates all differing bit positions into a single integer called difference.

The variable distance stores the number of differing bits found so far.

The while loop continues as long as there is at least one set bit remaining in difference.

Inside the loop, the statement:

difference &= difference - 1

removes the lowest set bit. Since each iteration removes exactly one set bit, incrementing distance counts one differing position.

Once all set bits are removed, difference becomes zero and the loop stops. The final value of distance is returned.

Go Solution

func hammingDistance(x int, y int) int {
    difference := x ^ y
    distance := 0

    for difference != 0 {
        difference &= difference - 1
        distance++
    }

    return distance
}

The Go implementation follows the exact same logic as the Python version.

The primary difference is syntax. Go uses := for variable declaration and a for loop instead of Python’s while loop.

No special overflow handling is required because the constraints guarantee that the values fit within standard integer ranges.

Worked Examples

Example 1

Input:

x = 1
y = 4

Binary representations:

1 = 0001
4 = 0100

Compute XOR:

0001
0100
----
0101

So:

difference = 5

Now count set bits.

Iteration difference (binary) Operation New difference distance
Start 0101 Initial value 0101 0
1 0101 0101 & 0100 0100 1
2 0100 0100 & 0011 0000 2

The loop ends because difference becomes 0.

Final answer:

2

Example 2

Input:

x = 3
y = 1

Binary representations:

3 = 0011
1 = 0001

Compute XOR:

0011
0001
----
0010

So:

difference = 2

Now count set bits.

Iteration difference (binary) Operation New difference distance
Start 0010 Initial value 0010 0
1 0010 0010 & 0001 0000 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(k) Each iteration removes one set bit
Space O(1) Only a few integer variables are used

The runtime depends on the number of set bits in x ^ y, not the total number of bits in the integers. In the worst case, there can be at most 31 set bits due to the constraints, so the algorithm is extremely efficient.

The space complexity is constant because no additional data structures are allocated.

Test Cases

solution = Solution()

assert solution.hammingDistance(1, 4) == 2  # Example 1
assert solution.hammingDistance(3, 1) == 1  # Example 2

assert solution.hammingDistance(0, 0) == 0  # Both numbers identical
assert solution.hammingDistance(0, 7) == 3  # Count set bits in one number
assert solution.hammingDistance(7, 0) == 3  # Reverse order of previous test

assert solution.hammingDistance(15, 15) == 0  # All bits match
assert solution.hammingDistance(8, 0) == 1  # Single set bit

assert solution.hammingDistance(255, 0) == 8  # Multiple consecutive set bits
assert solution.hammingDistance(1023, 511) == 1  # Only highest bit differs

assert solution.hammingDistance(2147483647, 0) == 31  # Maximum constraint value
assert solution.hammingDistance(2147483647, 2147483647) == 0  # Maximum equal values
Test Why
(1, 4) Validates the first provided example
(3, 1) Validates the second provided example
(0, 0) Tests identical zero values
(0, 7) Tests counting set bits directly
(7, 0) Ensures symmetry of the operation
(15, 15) Tests identical non-zero values
(8, 0) Tests a single differing bit
(255, 0) Tests many consecutive set bits
(1023, 511) Tests a high-bit difference
(2147483647, 0) Tests maximum constraint size
(2147483647, 2147483647) Tests maximum equal values

Edge Cases

One important edge case occurs when both numbers are identical. In that situation, every bit matches, so the XOR result becomes zero immediately. The loop never executes, and the algorithm correctly returns 0.

Another important case occurs when one number is zero. In this scenario, the Hamming distance equals the number of set bits in the other number. The XOR operation naturally handles this because 0 ^ n = n. The implementation correctly counts all set bits using Brian Kernighan’s algorithm.

A third edge case involves very large numbers near the upper constraint limit. For example, 2147483647 contains 31 set bits. Some implementations might incorrectly assume a fixed smaller bit width or mishandle integer operations. This solution works correctly because it relies entirely on standard bitwise operations and processes all set bits regardless of their position.

Another subtle edge case is when only one bit differs between the numbers. In that case, the XOR result contains exactly one set bit, and the loop executes exactly once. The implementation naturally handles this efficiently.