位运算常数优化的骚操作
SuperJvRuo
2018-01-21 21:32:47
### 零、前言：从门电路说起
在计算机内部，一切数据都是以二进制进行储存，其支持的最基本的元操作应该是布尔逻辑运算，例如逻辑与(and)、逻辑或(or)、逻辑非(not)、逻辑亦或(xor)等等。
这些运算的实现，几乎可以说是直接与电路的基本元件逻辑门相对应起来，是计算机天生所最擅长的操作，其执行速度无疑也是最快的。
比如，左上面那个门，叫“与门”，对应“逻辑与”运算。它左边的两只脚是输入，右边头上的一根毛是输出。计算机中用1表示true，0表示false，所以，当“与门”两只脚的输入都是1的时候，它头顶的毛才会输出1，否则，头顶上的毛就输出0。
类似的，右上边尖脑袋的家伙对应的是“逻辑或”运算。当且仅当两个输入都是0的时候，头顶上输出0，否则输出1。
另外左下边单脚的三角形家伙，叫“非门”：它头顶的毛总是输出跟脚底下的输入相反的结果。脚底输入0，头顶就输出1；脚底输入1，头顶就输出0。
这三个家伙是最基本的“门”。其他的什么与非门，或非门，同或门，异或门，都可以通过这哥仨组合得到。
当然了，上面这些都是画图的时候用的符号，就跟电路图里的电阻一样，画出来是这样：
可是在现实生活中，它长这样：
那么，这些计算机中的“门”，在现实生活中长什么样呢？
组成门电路的基本单元，叫“晶体管”，一个逻辑门由两个或多个晶体管组合而成。单个晶体管长这样：
这是一个早期的晶体管在电子显微镜下的照片。可以看到图中的比例尺是180nm。估算一下，这个晶体管的大小在350nm左右。
CCF的评测机CPU AMD Athlon II x2 240的制程为45nm。作为对比，人类头发单根直径是70μm左右，是这个晶体管大小的1500倍。如果用这样的晶体管来搭建“门”，在人类发断面那么小的面积上，可以搭出数百万个“门”。
整数的四则运算等操作，就是用众多逻辑门所搭建起来的。加减法电路的逻辑门数量比较少，同样可以在较短的时间内进行运算，但如果像除法一般逻辑复杂，电路也相应庞大，速度就很难以接受了。再到更复杂的浮点运算，速度也就更慢。简而言之，在众多的CPU 指令中，凡是在bit级别进行操作的，基本上都能够在一个clock cycle中完成，例如位移(bit shift)、位扫描(bit scan)、逻辑运算等等，再加上加减法、取补码等等简单的整数运算，组成了一个非常高速的指令集合。
巧妙地组合这些运算，往往能取代一些原本缓慢的操作，获得速度上的极大提升。
### 一、状压DP中的位运算
#### 1、读取第k位的值：
```cpp
int bit_read(int a,int k)
{
return a>>k&1;
}
```
#### 2、将第k位清0：
```cpp
void bit_clear(unsigned int &a)
{
a&=~(1<<k);
}
```
#### 3、将第k位置1：
```cpp
void bit_set(unsigned int &a)
{
a|=1<<k;
}
```
#### 4、将第k位取反：
```cpp
void bit_not(unsinged int &a,int k)
{
a^=1<<k;
}
```
#### 5、将第k1~k2位取反：
```cpp
void bits_not(unsigned int &a,int k1,int k2)
{
a^=((1<<(k2-k1+1))-1)<<k2;
}
```
### 二、打包位统计
#### 1、统计true的个数的奇偶性
```cpp
int bits_parity(unsigned int a)
{
x^=x>>1;
x^=x>>2;
x^=x>>4;
x^=x>>8;
x^=x>>16;
}
```
运算结果的第i 位表示在原始数据中从第i 位到最高位true 数目的奇偶性，有了这个结果，我们就可以很方便地得到任意一段的奇偶性。
如果想要得到k1~k2 位中true 个数的奇偶性，直接计算
(x>>k1^x>>(k2+1))&1
即可。
#### 2、统计true 的数目
```cpp
int popcount(unsigned int x)
{
x=(x&0x55555555)+(x>>1&0x55555555);
x=(x&0x33333333)+(x>>2&0x33333333);
x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
return x;
}
```
原理：
用分治法实现，将原始问题化为两个小问题——统计16个位元中值为1的位元个数，分别将其解决，然后再将结果合并。统计16位中值为1的位元个数时，又进一步化为求两个8个位元中值为1的位元个数...递归使用这个策略，直到分解 到统计1个位元中值为1的位元个数，把相邻两个位元的值相加，即得2个位元中中值为1的位元个数。
进一步优化：
```cpp
int popcount(unsigned int i)
{
i=i-((i>>1)&0x55555555);
i=(i&0x33333333)+((i>>2)&0x33333333);
i=(i+(i>>4))&0x0f0f0f0f;
i=i+(i>>8);
i=i+(i>>16);
return i&0x3f;
}
```
[【知乎】面试经典问题——统计 32 位有符号整型二进制表示中 1 的数目](https://zhuanlan.zhihu.com/p/32899882)
当然也可以以空间换时间：
```cpp
const unsigned char popcount_tab[]=
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
};
int popcount (register int x)
{
return popcount_tab[(x>>0)&0xff]+popcount_tab[(x>>8)&0xff]+popcount_tab[(x>>16)&0xff]+popcount_tab[(x>>24)&0xff];
}
```
#### 3、反转位的顺序
```cpp
unsigned int rev(unsigned int x)
{
x=(x&0x55555555)<<1|(x>>1&0x55555555);
x=(x&0x33333333)<<2|(x>>2&0x33333333);
x=(x&0x0F0F0F0F)<<4|(x>>4&0x0F0F0F0F);
x=(x&0x00FF00FF)<<8|(x>>8&0x00FF00FF);
x=(x&0x0000FFFF)<<16|(x>>16&0x0000FFFF);
return x;
}
```
### 三、常用操作的位运算优化
#### 1、计算绝对值
```cpp
int abs(int x)
{
int y=x>>31;
return (x+y)^y;
}
```
#### 2、求较大值
```cpp
int max(int x,int y)
{
int m=(x-y)>>31;
return y&m|x&~m;
}
```
#### 3、交换变量
```cpp
void swap(int &a,int &b)
{
a^=b;
b^=a;
a^=b;
}
```
#### 4、求两个整数的平均值，不会溢出
```cpp
int ave(int x,int y)
{
return (x&y)+((x^y)>>1);
}
```
### 四、用位运算装逼
#### 1、a+b Problem
```cpp
#include<cstdio>
int add(int a, int b) {
while (b)
{
int sw = a;
a ^= b;
b = (b & sw) << 1;
}
return a;
}
int main()
{
int a, b, ans;
scanf("%d%d", &a, &b);
printf("%d", add(a, b));
return 0;
}
```