当前位置：首页 > article >正文

Brian Kernighan 算法

article 2025/2/23 5:16:24

在C++中，位与运算符 & 用于对两个整数的二进制表示进行逐位与操作。对于每个二进制位，只有当两个操作数的对应位都是 1 时，结果的该位才是 1，否则是 0。

表达式 a &= (a - 1) 的作用是将整数 a 的二进制表示中最低位的 1 变为 0。这个操作的原理如下：

减法操作：a - 1 会将 a 的二进制表示中最低位的 1 变为 0，并将其右边的所有 0 变为 1。
与运算：将 a 与 a - 1 进行与运算，结果会将 a 中最低位的 1 变为 0，因为 a - 1 在这个位置是 0，而其他位置保持不变，因为 a 和 a - 1 在其他位置的位都是相同的。

例子：

假设 a 的二进制表示为 101100（十进制为 44）。

减法操作：a - 1 的二进制表示为 101011（十进制为 43）。
与运算：a & (a - 1) 的结果为 101000（十进制为 40）。

可以看到，a & (a - 1) 的结果是将 a 的二进制表示中最低位的 1 变为 0。

作用：

这个操作在统计二进制表示中 1 的个数时非常有用。每次执行 a &= (a - 1)，都会去掉 a 中的一个 1。因此，执行这个操作的次数就是 a 的二进制表示中 1 的个数。

代码示例：

cpp复制

#include <iostream>
using namespace std;

int main() {
    unsigned int a;
    cin >> a;
    int num = 0;

    // Brian Kernighan 算法
    while (a > 0) {
        a &= (a - 1); // 去掉最低位的1
        num++;
    }

    cout << num << endl;
    return 0;
}