2018-01-21 21:32:47

### 零、前言：从门电路说起

CCF的评测机CPU AMD Athlon II x2 240的制程为45nm。作为对比，人类头发单根直径是70μm左右，是这个晶体管大小的1500倍。如果用这样的晶体管来搭建“门”，在人类发断面那么小的面积上，可以搭出数百万个“门”。

### 一、状压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;
}

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

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);