听attack学长讲完课，整理一波

基本运算

按位或

\(1|1 = 1，1 | 0 = 1，0|0 = 0\)

按位与

\(1\&1=1 ,1 \& 0 = 0,0 \& 0 = 0\)

异或

\(1 \bigoplus 1 = 0,1\bigoplus 0 = 1,0 \bigoplus 0 = 0\)
异或性质
1.\(a \bigoplus a = 0\)
2.\(a \bigoplus 0 = a\)
3.\(a \bigoplus b = b \bigoplus a\)
4.\(a \bigoplus b \bigoplus c = a \bigoplus (b \bigoplus c)\)

按位取反

\(\sim x\)就是将x在二进制下的\(0\)变为\(1\)，\(1\)变为\(0\)

移位运算

逻辑移位

一般采用的移位方式。
右移时左边补零，右边溢出(舍弃)
左移时右边补零，左边溢出。

算术移位

右移时左边由符号决定。右边溢出。
左移时左边溢出(符号位不变)，右边补零。

循环移位

将溢出的位填补到另一边。

基础操作

查看pos位

\(x>>pos \& 1\)

更改pos位

\(x |= (1 << pos),x ^{\wedge}=(1<<pos),x\&=(1<<pos)\)

不基础操作

lowbit

\(lowbit(x) = x \& -x\)
可以快速找到x中最后一个1出现的位置。

快速查询二进制中1的个数

正常做法

cin>>x;
   cout<<__builtin_popcount(x)<<endl;

***丝做法
预处理，\(count[i] = count[i >> 1] + (i \& 1)\)

cin>>x;
   for(unint i = 1;i <= 1000000;++i)
      Count[i] = Count[i>>1] + (i & 1);
   cout<<Count[x];

那如果查询的数字到了\(10^9\)或者更大怎么办。很简单只要上这个数字前\(16\)的\(count\)+后\(16\)位的\(count\)就行了。

翻转二进制位

和上面方法类似，先预处理出翻转\(16\)位后的数字，\(32\)位的将前后分别翻转即可。

cin>>x;
   for(unint i = 1;i <= (1 << 16);++i)
      rev[i] = rev[i>>1] | ((i & 1) << 15);
   cout<<rev[x >> 16] | (rev[x & ((1 << 16) - 1)] << 16);

求后缀0的个数

可以用lowbit快速找到最后一个1的位置就就行了。
也可以\(\_\_builtin\_ctz(x)\)

求前缀0的个数

\(\_\_builtin\_clz(x)\)

提取末尾连续的1

\(x\&(x ^{\wedge} (x + 1))\)

枚举子集

for(int i = x;i;i = (i - 1) & x) {
    i是x的一个子集
}

找到所有二进制下含有k个1的数

设最右边连续的\(1\)是第\(𝑖\)位到第\(𝑗\)位，我们可以\(𝑖\)位\(+1\)，同时原来\(𝑖\)到\(𝑗 – 1\)位上的\(1\)移到最后
比如\(101110\)，\(𝑘 = 4\)
此时\(𝑖=1, 𝑗=3,\) 我们给\(1\)位置\(+1\)，变为\(110000\)，再把\(1\)到\(2\)位置的\(1\)移到最后，变为\(110011\)

unint nxt(unint x) {
   unint l = x & -x,y = x + l;
   return y | (((x ^ y) / l) >> 2);
}
int main() {
   int x;
   cin>>x;
   unint z = (1 << x) - 1;
   while(z) {
      cout<<z<<endl;
      z=nxt(z);
   }
   return 0;
}