Problem of The Day: Hamming Distance

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        res = 0
        mask = 1
        while x > 0 or y > 0:
            a = x & mask
            b = y & mask
            if a != b:
                res += 1
            x >>= 1
            y >>= 1
        return res

Editorial

Approach 1: Built-in BitCounting Functions

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

Approach 2: Bit Shift

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        xor = x ^ y
        distance = 0
        while xor:
            # mask out the rest bits
            if xor & 1:
                distance += 1
            xor = xor >> 1
        return distance

Approach 3: Brian Kernighan’s Algorithm

class Solution:
    def hammingDistance(self, x, y):
        xor = x ^ y
        distance = 0
        while xor:
            distance += 1
            # remove the rightmost bit of '1'
            xor = xor & (xor - 1)
        return distance