461. Hamming Distance

Problem¶

Given two non-negative integers x and y, count how many bit positions differ between them.

Example:

x=1 (0001), y=4 (0100) -> 2

Key trick¶

XOR marks exactly the differing bits.

• x ^ y has 1 where bits differ
• so the answer is the number of set bits in x ^ y

Trap¶

• Comparing decimal digits instead of binary bits
• Forgetting that XOR already isolates differences
• Reimplementing bit counting poorly when bit_count() exists in Python

Why is it interesting?¶

It tests whether you recognize a bitwise reduction:

• difference in bits
• becomes XOR
• then popcount

Python solution¶

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # XOR keeps 1 only where x and y differ.
        return (x ^ y).bit_count()

    def hammingDistance_2(self, x: int, y: int) -> int:
        n = x ^ y
        cnt = 0
        while n:
            n &= n - 1
            cnt += 1
        return cnt

Comment on my solution¶

Your solution is already ideal.

• Correct
• Idiomatic
• Optimal for Python
• Minimal and readable

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