algorithm notes: leetcode#461 hamming distance

Problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2³¹.

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.

Solution

Basic idea

Use XOR to solve this problem. 1 ^ 0 = 1, 1 ^ 1 = 0 ^ 0 = 0. If two bits are different, it will return 1 otherwise 0. So we can calculate x ^ y, transform to binary form, and then count the number of 1 as result. For example, x = 1, y = 4, then x ^ y = 5, which is ‘0101’ in binary form. There are two ‘1’ in ‘0101’.

Python implementation

1
2
3
4
5
6
7
8

class (object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count('1')

Java implementation

1
2
3
4
5

class  {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

Time complexity

O(1)

Space complexity

O(1)

Link

461. Hamming Distance
461. 汉明距离
(中文版) 算法笔记: 力扣#461 汉明距离