[容易]汉明距离

[容易]汉明距离

[题]

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

Note: \(0\leq x,y < 2^{31}\)

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

Input: x = 1, y = 4
Output = 2
Explanation:
1 (0 0 0 1)
2 (0 1 0 0)

[解]

Method 1:
分别列出两个数字的二进制形式,并放在两个list中,逐个的比较元素值,从而得出结果

Method 2:
对两个数进行异或操作,得出新的数字,将这个数学转换为二进制形式,每个1代表有一对元素不同。

4 xor 6
0100 xor 0110
0010
2

Method 3
利用异或的特性,先将两数 x 和 y 做异或运算。得到的结果中,为 1 的位表示 x 和 y 中不相同的位置。先右移再左移,此时若xor还等于原来的xor,则表示最低位为0,否则为1。记录xor中1的个数,即 x 和 y 不同位的个数。

10010 >> 1 = 00100

求该整数的二进制表示中有多少个1