统计一个非负整数的二进制形式中1的个数(Brian Kernighan 算法)

当我们要统计一个非负整数的二进制形式中 1 的个数时，可以使用“位运算”的方法，这种方法的原理是通过一些特殊的位运算操作来快速计算一个数字的二进制形式中 1 的个数。

以下是一种比较常见的位运算方法：

1. 定义一个变量 ret，初始值为 0，用于记录二进制形式中 1 的个数。

2. 对于给定的数字 x，我们不断地把它的最低位上的数字与 1 进行比较，如果是 1，就把 ret 加一。

3. 然后，将 x 右移一位，即将 x 的二进制表示形式向右移动一位，去掉最低位的数字。

4. 重复步骤 2 和步骤 3，直到 x 变成 0 为止。

在第二步中，我们如何判断 x 的最低位上的数字是否为 1 呢？这里我们可以使用按位与运算（&），按位与运算的规则是：只有两个相应的二进制位都为 1 时，结果才为 1，否则为 0。因此，如果我们将 x 和 1 进行按位与运算，得到的结果就是 x 的最低位上的数字。例如，对于数字 5（二进制形式为 101），我们将它和 1 进行按位与运算，得到的结果为 1，说明它的最低位上的数字是 1。

但是，使用上述方法进行循环的次数等于数字二进制形式中 1 的个数，效率并不是很高。因此，我们可以采用另外一种更快的方法，即“Brian Kernighan 算法”，该算法的基本思路是利用按位与运算的性质，每次去掉 x 的二进制形式中最低位上的 1，直到 x 变成 0。

具体实现方法如下：

1. 定义一个变量 ret，初始值为 0，用于记录二进制形式中 1 的个数。

2. 对于给定的数字 x，不断执行以下操作，直到 x 变成 0 为止： a. 将 x 与 x-1 进行按位与运算，并将结果赋值给 x。这个操作会将 x 的二进制形式中最低位上的 1 变成 0。 b. ret 加 1。

3. 返回 ret，即为数字 x 的二进制形式中 1 的个数。

在这个过程中，每次执行操作 a，都会去掉 x 的二进制形式中最低位上的 1。

因此，对于任意一个非负整数 x，循环的次数等于它的二进制形式中 1 的个数，而且由于每次操作都会去掉一个 1，因此时间复杂度为 O(k)，其中 k 是 x 的二进制形式中 1 的个数。

与普通的循环方法相比，Brian Kernighan 算法在计算二进制形式中 1 的个数时具有更高的效率。这是因为在二进制表示中，每个数字都可以表示为若干个 2 的幂次之和，例如 9（二进制表示为 1001）可以表示为 2³ + 2⁰，而 10（二进制表示为 1010）可以表示为 2³ + 2¹。在 Brian Kernighan 算法中，每次操作都会去掉二进制形式中最低位上的 1，因此每个数字只会被处理一次，因此时间复杂度为 O(k)，其中 k 是 x 的二进制形式中 1 的个数。

因此，我们可以将原来的代码修改为以下形式：

int CountBit(int x)
{
    int ret = 0;
    while (x)
    {
        x = x & (x - 1);
        ret++;
    }
    return ret;
}

其中，x & (x - 1) 表示将 x 的二进制形式中最低位上的 1 变成 0，这个操作会去掉 x 的二进制形式中最低位上的 1。

Brian Kernighan 算法

Brian Kernighan 算法是一种用于统计一个二进制数中 1 的个数的算法，它被命名为 Brian Kernighan，是因为这个算法是由 Brian Kernighan 在他的《C Programming Language》一书中首次介绍的。

该算法的思想是利用位运算，通过不断将数字中最低位的 1 变成 0 的方式来统计二进制数中 1 的个数。具体来说，算法的步骤如下：

1. 定义一个计数器 ret，初始值为 0。

2. 循环直到数字 x 变成 0：每次循环中，将 x 与 x - 1 做与运算，然后将结果赋值给 x。也就是说，x = x & (x - 1)。

3. 在每次循环中，将计数器 ret 加 1。

4. 循环结束后，返回计数器 ret 的值，即为二进制数中 1 的个数。

算法的正确性可以通过以下思路来解释：当一个二进制数减去 1 时，它的最低位的 1 变成了 0，而该位之后的所有 0 变成了 1。因此，如果我们将一个二进制数与它减去 1 的结果做与运算，那么该数最低位的 1 就会变成 0。因此，每次将 x 与 x - 1 做与运算，都会将 x 的二进制形式中最低位的 1 变成 0，这样就能够不断去掉 x 的二进制形式中的 1，并在每次操作中将计数器加 1，从而统计出二进制数中 1 的个数。

Brian Kernighan 算法的时间复杂度与二进制数中 1 的个数相关，具体来说，时间复杂度为 O(k)，其中 k 是二进制数中 1 的个数。这比暴力枚举二进制数中的每一位并统计 1 的个数更加高效。

假设我们要统计数字 19（二进制表示为 10011）中的 1 的个数，下面一步一步演示 Brian Kernighan 算法的执行过程：

1. 定义计数器 ret，初始值为 0。

2. 循环直到数字 x 变成 0。

1. 第一次循环中，x = 19，执行 x = x & (x - 1) 的结果为 x = 10011 & 10010 = 10010，即将数字 19 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 1。

2. 第二次循环中，x = 18，执行 x = x & (x - 1) 的结果为 x = 10010 & 10001 = 10000，即将数字 18 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 2。

3. 第三次循环中，x = 16，执行 x = x & (x - 1) 的结果为 x = 10000 & 01111 = 00000，即将数字 16 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 3。

4. 因为此时 x = 0，跳出循环。

3. 返回计数器 ret 的值，即为数字 19 的二进制形式中 1 的个数，也就是 3。

通过上面的步骤，我们可以看到算法是如何利用位运算，每次将数字中最低位的 1 变成 0 的方式，统计二进制数中 1 的个数的。

我们再举一个数据示例：

假设我们要统计数字 15（二进制表示为 1111）中的 1 的个数，下面一步一步演示 Brian Kernighan 算法的执行过程：

1. 定义计数器 ret，初始值为 0。

2. 循环直到数字 x 变成 0。

1. 第一次循环中，x = 15，执行 x = x & (x - 1) 的结果为 x = 1111 & 1110 = 1110，即将数字 15 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 1。

2. 第二次循环中，x = 14，执行 x = x & (x - 1) 的结果为 x = 1110 & 1101 = 1100，即将数字 14 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 2。

3. 第三次循环中，x = 12，执行 x = x & (x - 1) 的结果为 x = 1100 & 1011 = 1000，即将数字 12 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 3。

4. 第四次循环中，x = 8，执行 x = x & (x - 1) 的结果为 x = 1000 & 0111 = 0000，即将数字 8 的二进制形式中最低位的 1 变成了 0。 此时计数器 ret 的值为 4。

5. 因为此时 x = 0，跳出循环。

3. 返回计数器 ret 的值，即为数字 15 的二进制形式中 1 的个数，也就是 4。

通过上面的步骤，我们可以看到算法是如何利用位运算，每次将数字中最低位的 1 变成 0 的方式，统计二进制数中 1 的个数的。

csp-j2018年初赛：

为了统计一个非负整数的二进制形式中 1 的个数，代码如下：

int CountBit(int x)
{
    int ret = 0;
    while(x)
    {
     ret++;
     ___________;
    }
    return ret;
}

则空格内要填入的语句是（ ）。 A. x >>= 1 B. x &= x - 1 C. x |= x >> 1 D. x <<= 1