零、前言：从门电路说起

在计算机内部，一切数据都是以二进制进行储存，其支持的最基本的元操作应该是布尔逻辑运算，例如逻辑与(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位的值：

int bit_read(int a,int k)
{
    return a>>k&1;
}

2、将第k位清0：

void bit_clear(unsigned int &a)
{
    a&=~(1<<k);
}

3、将第k位置1：

void bit_set(unsigned int &a)
{
    a|=1<<k;
}

4、将第k位取反：

void bit_not(unsinged int &a,int k)
{
    a^=1<<k;
}

5、将第k1~k2位取反：

void bits_not(unsigned int &a,int k1,int k2)
{
    a^=((1<<(k2-k1+1))-1)<<k2;
}

二、打包位统计

1、统计true的个数的奇偶性

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 的数目

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的位元个数。

进一步优化：

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 的数目

当然也可以以空间换时间：

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、反转位的顺序

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、计算绝对值

int abs(int x)
{
    int y=x>>31;
    return (x+y)^y;
}

2、求较大值

int max(int x,int y)
{
    int m=(x-y)>>31;
    return y&m|x&~m;
}

3、交换变量

void swap(int &a,int &b)
{
    a^=b;
    b^=a;
    a^=b;
}

4、求两个整数的平均值，不会溢出

int ave(int x,int y)
{
    return (x&y)+((x^y)>>1);
}

四、用位运算装逼

1、a+b Problem

#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;
}