461.Hamming Distance

Tags: [bit-operation]

Link: https://leetcode.com/problems/hamming-distance/?tab=Description

TheHamming distancebetween two integers is the number of positions at which the corresponding bits are different.

Given two integersxandy, calculate the Hamming distance.

Note:
0 ≤x,y< 231.

Example:

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.

Better Solution:

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        z = x^y
        counter = 0
        for i in xrange(32):
            counter += (z >> i) & 1
        return counter

Better Solution:

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        counter = 0
        for i in xrange(32):
            counter += ((x >> i) & 1) ^ ((y >> i) & 1)
        return counter

Solution:

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        if x < 0 or y < 0:
            raise ValueError('the input is invalid')

        hamming_distance = 0
        for i in xrange(32):
            hamming_distance += (x & 1) ^ (y & 1)
            x >>= 1
            y >>= 1

        return hamming_distance

Revelation:

• For most of bit-operation problem, we can assume one integer has only 32 bits.

Note:

• In Python, XOR operator is ' ^ '
• In Java, XOR operator is ' ^ '
• 0 ^ 0 == 0
• 0 ^ 1 == 1
• 1 ^ 0 == 1
• 1 ^ 1 == 0