461. Hamming Distance

Reformulated question¶

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 this question interesting?¶

It tests whether you recognize a bitwise reduction:

difference in bits
becomes XOR
then popcount

Solve the problem with idiomatic python¶

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

Alternative without bit_count():

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # Brian Kernighan's trick:
        # each step removes the lowest set bit.
        n = x ^ y
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("x", "y", "expected"),
    [
        (1, 4, 2),
        (3, 1, 1),
        (0, 0, 0),
        (0, 7, 3),
        (7, 0, 3),
        (15, 15, 0),
        (10, 5, 4),
        (2**31 - 1, 0, 31),
    ],
)
def test_hamming_distance(x, y, expected):
    assert Solution().hammingDistance(x, y) == expected

Comment 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()

Code¶

import pytest


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


class SolutionKernighan:
    def hammingDistance(self, x: int, y: int) -> int:
        # Remove one set bit at a time from x ^ y.
        n = x ^ y
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count


@pytest.mark.parametrize(
    ("x", "y", "expected"),
    [
        (1, 4, 2),
        (3, 1, 1),
        (0, 0, 0),
        (0, 7, 3),
        (7, 0, 3),
        (15, 15, 0),
        (10, 5, 4),
        (2**31 - 1, 0, 31),
    ],
)
def test_hamming_distance(x, y, expected):
    assert Solution().hammingDistance(x, y) == expected


Solution().hammingDistance(1, 4)       # 2
Solution().hammingDistance(3, 1)       # 1
SolutionKernighan().hammingDistance(1, 4)  # 2