leetcode-461

461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

方法二与方法三是官方题解。

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

解法

方法一：内置位计数功能

使用异或运算

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

方法二：移位实现计数

将异或后的结果与1进行与操作，然后与计数器累加，再右移。

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

方法三：Brian Kernighan 算法

对于一个正整数m来说,m&m-1的结果会将m的二进制最右边的1变成0

在方法二中，对于 $s=(10001100)_2$的情况，我们需要循环右移 $8$ 次才能得到答案。而实际上如果我们可以跳过两个$1$之间的 $0$，直接对 $1$ 进行计数，那么就只需要循环 $3$ 次即可。

我们可以使用 $\text{Brian Kernighan}$ 算法进行优化，具体地，该算法可以被描述为这样一个结论：记$f(x)$表示$x$和$x-1$进行与预算得到的结果既（$f(x)=x&(x-1)$），那么$f(x)$恰为$x$删去其二进制表示中最右侧的 $1$ 的结果。

基于该算法，当我们计算出$s = \boldsymbol { x } \oplus \boldsymbol { y } $，只需不断让$s=f(s)$，直到$s=0$即可。这样没循环一次，$s$都会删去其二进制表示中最右侧的 1，最终循环的次数即为 s 的二进制表示中 1 的数量。

位运算

下表中变量 a 为 60，b 为 13，二进制格式如下：

a = 0011 1100

b = 0000 1101

运算符	描述	实例
&	按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0	(a & b) 输出结果 12 ，二进制解释： 0000 1100
|	按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。	(a |b) 输出结果 61 ，二进制解释： 0011 1101
^	按位异或运算符：当两对应的二进位相异时，结果为1	(a ^ b) 输出结果 49 ，二进制解释： 0011 0001
~	按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。**~x** 类似于 -x-1	(~a ) 输出结果 -61 ，二进制解释： 1100 0011，在一个有符号二进制数的补码形式。
<<	左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。	a << 2 输出结果 240 ，二进制解释： 1111 0000
>>	右移动运算符：把”>>”左边的运算数的各二进位全部右移若干位，**>>** 右边的数字指定了移动的位数	a >> 2 输出结果 15 ，二进制解释： 0000 1111

python二进制、整数转化

整数转二进制：
1、采用%2的方式计算
2、采用python自带了方法 bin.
比如bin(10) 回返回字符串'0b1010' ，只留下‘0’，‘1’序列需要把‘0b’去掉.
bin(number).replace('0b','') 或bin(number)[2:]
>>> bin(10)  // 为了下边表示方便 放入t中
'0b1010'
 
二进制转整数：
>>> int(t[2:],2)
10