Brain Kernighan 比特位计数算法

Brain Kernighan 算法用来计算数据的 Hamming Weight，即一串 bit 中为 1 的位数，用以提升计算效率。

我们先来通过普通的办法尝试来计算对一个 32 位整形数的比特位计数，python 的代码如下：

def hammingWeight(self, n: int) -> int:
    ret = 0
    while n:
        ret += n % 2
        n = n >> 1
    return ret

我们通过一个循环，不断的考察 n 的最后一位，如果是 1， 则说明最右边 bit 为 1，将结果+1，这个算法的时间复杂度为 O(32), 不错是常数，但我们还有提升空间，比如这样一个数字 1000000001 我们的算法在中间 0 的时候会做多次无用的计算，使用 Brain Kernighan 算法则可以帮我们跳过中间 0 位的循环，可以进一步提高计算的数度，实现代码如下：

def hammingWeight(self, n: int) -> int:
    ret = 0
    while n:
        n &= n - 1
        ret += 1
    return ret

这里的原理是，n = n & (n-1) 会去掉 n 中最右边的 1，我们只要不断重复这一操作，当 n 降为 0 时，我们的操作次数就是 n 中 1bit 的数量。考虑以下这个例子：

// first iteration
n           = 1001
n - 1       = 1000
n & (n - 1) = 1000
op_times    = 1

// second iteration
n           = 1000
n - 1.      = 0111
n & (n - 1) = 0000
op_times    = 2

// n = 0 now stop iteration and return op_times as result