Brian Kernighan 求解 set bit 个数

基础知识

二进制位由 0 与 1 组成, 把不同的位分别定义如下：

如下图所示，上面的部分为 set bit，下面的为 unset bit

按位与操作：bitwise AND operator

两边的 bit 都是 1 返回 1，否则返回 0

按位右移操作：bitwise Right-shift operator

往右边移动一个比特位，也等同于直接除以 2.操作的结果就是，最右边的比特位被删了。

要理解 Brain 算法，首先要理解 n-1 会发生什么？

假设把一个二进制数的最右边的 set bit 称为 p 点。n-1 会将 p 点及后面所有的位置的比特进行反转，0 变成 1，1 变成 0。

以一个 set bit 不在最后一位为例，40 的二进制表示为 101000。在进行 n-1 操作后，比特位变成了 100111. 上面的例子中，p 点及后面的比特位从 1000 变成了 0111。

有了这个基础后，再执行 n & (n-1) 会发生什么？

n -1 只会改变 p 点及后面的位置，对于 p 点之前的位置是保持不变的。那么在 p 点之前的比特位执行 n & (n-1)，前面的比特位不发生改变。 n 与 n-1 ,在 p 及 p 后面的比特位中是完全相反的，所以这部分的比特位在进行 & 操作后，会全部变成 0。

这也就解释了 n & (n-1) 的作用就是，将 p 点及后面的位置全部清零。那么，被清理的部分有多少个 1 呢？

根据上面 p 点的定义，p 点就是最右边的 1 个 set bit，所以只有 1 位 1.

那么每次减 1 后，计数器加 1，直到 n 变为 0，是不是就把所有的 1 给数出来了呢！

1
2
3
4
5
6
7
8
func brianKernihan(x int) int {
    count := 0
    for x > 0 {
        x = x & (x-1)
        count++
    }
    return count
}