位运算

常用位运算符

1. 按位与

a & b;

2. 按位或

a | b;

3. 按位异或（XOR）运算：对应二进制位上 相同为 0，不同为 1。

位1	位2	结果
0	0	0
0	1	1
1	0	1
1	1	0

a ^ b

基本函数

1. 计算一个正整数用 多少位二进制位 来表示（不包括前导 0），等价于“最小能装下它的位数

bit_width(n);

2. 统计一个整数的二进制表示中有多少个1

int x = 13;                    // 二进制：1101
cout << __builtin_popcount(x); // 输出：3

Brian Kernighan算法：

int bitCount(int n) 
{
    int count = 0;
    while (n) 
   {
        n &= (n - 1); // 每次清除最低位的1
        count++;
    }
    return count;
}