布赖恩·克尼根算法

Leetcode461 官方题解

布赖恩·克尼根算法
思路

方法二是逐位移动，逐位比较边缘位置是否为 1。寻找一种更快的方法找出等于 1 的位数。

是否可以像人类直观的计数比特为 1 的位数，跳过两个 1 之间的 0。例如：10001000。

上面例子中，遇到最右边的 1 后，如果可以跳过中间的 0，直接跳到下一个 1，效率会高很多。

这是布赖恩·克尼根位计数算法的基本思想。该算法使用特定比特位和算术运算移除等于 1 的最右比特位。

当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。

基于以上思路，通过 2 次迭代就可以知道 10001000 中 1 的位数，而不需要 8 次。

PythonJava

class Solution {
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while (xor != 0) {
distance += 1;
// remove the rightmost bit of ‘1‘
xor = xor & (xor - 1);
}
return distance;
}
}
注意：该算法发布在 1988 年 《C 语言编程第二版》的练习中（由 Brian W. Kernighan 和 Dennis M. Ritchie 编写），但是 Donald Knuth 在 2006 年 4 月 19 日指出，该方法第一次是由 Peter Wegner 在 1960 年的 CACM3 上出版。顺便说一句，可以在上述书籍中找到更多位操作的技巧。

复杂度分析

时间复杂度：\mathcal{O}(1)O(1)。

与移位方法相似，由于整数的位数恒定，因此具有恒定的时间复杂度。

但是该方法需要的迭代操作更少。

空间复杂度：\mathcal{O}(1)O(1)，与输入无关，使用恒定大小的空间。

作者：LeetCode
链接：https://leetcode-cn.com/problems/hamming-distance/solution/yi-ming-ju-chi-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。