位运算

约 339 个字 9 行代码 预计阅读时间 1 分钟

$a+b=(a\oplus b)+((a\&b)<<1)$ ，把异或看成不进位的加法，与看成计算进位，左移一下加上去，刚好是和

位运算题目通常按照每一位拆开来，分别计算贡献，再加起来

int lowbit(int x){return x&(-x);} 返回最低位的1，的2的幂

__lg $O(1)$ 求 $\log_2x$ ，比 log2 快

内建函数

1. int __builtin_ffs(int x) ：返回 x 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 x 为 0 时返回 0 。

2. int __builtin_clz(unsigned int x) ：返回 x 的二进制的前导 0 的个数。当 x 为 0 时，结果未定义。

3. int __builtin_ctz(unsigned int x) ：返回 x 的二进制末尾连续 0 的个数。当 x 为 0 时，结果未定义。

4. int __builtin_clrsb(int x) ：当 x 的符号位为 0 时返回 x 的二进制的前导 0 的个数减一，否则返回 x 的二进制的前导 1 的个数减一。

5. int __builtin_popcount(unsigned int x) ：返回 x 的二进制中 1 的个数。

6. int __builtin_parity(unsigned int x) ：判断 x 的二进制中 1 的个数的奇偶性。

这些函数都可以在函数名末尾添加 ll （如 __builtin_popcountll ）来使参数类型变为 ( unsigned ) long long （返回值仍然是 int 类型）。

各种枚举集合

for(int i=mask;i;i=(i-1)&mask)//枚举子集,O(2^{popcount}),没有考虑0，如果需要则特判
for(int i=0;i<(1<<n);++i)for(int j=i;j;j=(j-1)&i)//枚举每个子集的子集，O(3^n)
for(int i=mask;i<MAX;i=(i+1)|mask)//枚举超集,O(2^{TotalDigit-popcount})
for(int i=(1<<k)-1;i<(1<<n);){//枚举所有大小为k的子集,k=0需特判
    //具体操作
    int x=i&-i;
    int y=i+x;
    i=((i&~y)/x>>1)|y;
}

---

讲课链接