Tricks

二进制/位运算相关

内建函数

• __builtin_ctzll(x) 求 $x$ 左侧连续 $0$ 的个数

• __builtin_popcount(x) 求 $x$ 二进制表示中 $1$ 的个数

Lowbit

• x&-x 求左侧一个 $1$，如 $(10100)_2\to(100)_2$

• 使用 Lowbit 预处理状压中二进制数对应数组元素的和值

  for(int s=1;s<(1<<n);s++){
   sum[s]=sum[s^(s&-s)]+a[__builtin_ctzll(s&-s)+1];
  }

• 使用 Lowbit 枚举二进制数中每一个 $1$

  for(int t=x;t;t-=t&-t){
      //此时用t&-t从左到右取出所有1
  }