Bitwise Operators

基础的位操作见C++技巧。

更多位操作

除了基础的And, Or, Xor, Not以及移位操作外，以下更多的位操作函数也是有用的：

• __builtin_clz(x) (count trailing zeros): 数字最前面的$0$的数量
• __builtin_ctz(x) (count leading zeros): 数字最后面的$0$的数量
• __builtin_popcount(x): 数字中$1$的位数
• __builtin_parity(x): 数字的奇偶校验（1的位数 % 2）

以上是int的版本，在后面加上ll就是long long的版本，比如__builtin_ctzll(x)。

子集的位表示

用bitmask可以方便地表示子集，例如遍历所有$n$个元素的子集：

for (int b = 0; b < (1<<n); b++) {
    // process subset b
}

遍历所有$k$个元素的子集：

for (int b = 0; b < (1<<n); b++) {
    if (__builtin_popcount(b) == k) {
        // process subset b
    }
}

习题