461. Hamming Distance

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.

Example 1:

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.

Example 2:

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

Constraints:

• 0 <= x, y <= 231 - 1

To corresponding bits at a position in both of the number in binary forms are different , we use xor operation for these corresponding bits in the number.

Approach 1:

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

Time: O(log(max(x,y)))

Space: O(1)

Approach 2:

Brian Kernighan’s Algorithm:
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit. Therefore, Anding this with the number gives a value in which all the bits after this first set bit from right side , including this bit changes to zero .Doing this successively will count the number of set bits in the number. Our aim here is to count the number of 1’s in x^y.

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

Time: O(number of 1’s in x^y)

Space: O(1)