Hamming Distance

Difficulty: Easy | Acceptance: 76.80% | Paid: No Topics: Bit Manipulation

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.

• Examples
• Constraints
• Bit Shifting
• Brian Kernighan’s Algorithm
• Built-in Functions

Examples

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Input: x = 3, y = 1
Output: 1

Constraints

0 <= x, y <= 2³¹ - 1

Bit Shifting

Intuition The XOR operation (^) between two numbers results in a number where the bits are set to 1 only where the corresponding bits of the operands are different. We can iterate through the bits of the XOR result to count the number of 1s.

Steps

• Calculate xor = x ^ y.
• Initialize a counter to 0.
• Loop while xor is greater than 0:
  • Add the result of xor & 1 to the counter (checks if the least significant bit is 1).
  • Right shift xor by 1 bit (xor >>= 1).
• Return the counter.

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        distance = 0
        while xor:
            distance += xor & 1
            xor >>= 1
        return distance

Complexity

• Time: O(1) - We iterate at most 32 times (for 32-bit integers).
• Space: O(1) - We use a constant amount of extra space.
• Notes: This is a straightforward approach but always iterates 32 times in the worst case.

Brian Kernighan’s Algorithm

Intuition This is an optimized bit manipulation trick. The expression n & (n - 1) drops the lowest set bit (turns the rightmost 1 to 0). We can use this to count the number of 1s by repeatedly clearing the lowest set bit until the number becomes 0.

Steps

• Calculate xor = x ^ y.
• Initialize a counter to 0.
• Loop while xor is greater than 0:
  • Update xor to xor & (xor - 1).
  • Increment the counter.
• Return the counter.

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        distance = 0
        while xor:
            xor &= xor - 1
            distance += 1
        return distance

Complexity

• Time: O(k) - Where k is the number of set bits in xor. In the worst case, it is O(32) = O(1).
• Space: O(1) - Constant space usage.
• Notes: This is generally faster than the standard bit shifting approach when the number of differing bits is small.

Built-in Functions

Intuition Most programming languages provide built-in functions or library methods to count the number of set bits (population count) in an integer. We can leverage these to solve the problem concisely.

Steps

• Calculate xor = x ^ y.
• Return the result of the built-in popcount function applied to xor.

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')

Complexity

• Time: O(1) - The operation is generally optimized to hardware instructions or runs in constant time relative to integer size.
• Space: O(1) - Constant space.
• Notes: This is the most readable and concise solution, though it relies on language-specific features.