位运算是计算机底层的操作，通常效率极高，对程序的优化有着不可忽视的作用

求二进制数中 1 的个数

Solution1:

很直接地可以想到，可以枚举每一位，检测是否为 1，将答案累加。

int count1(unsigned int x)
{
    int cnt=0;
    for(int x=0;i<32;i++)if(x&(1<<i))cnt++;
    return cnt;
}

分析发现，这种方法时间复杂度为恒值：
32~64 次自加操作，32 次&，32 次<<

Solution2:

灵感：可以用 lowbit 函数去除最后一位 1。

int lowbit(x){return x&-x;}
int count2(unsigned int x)
{
    int cnt=0;
    while(x)x-=lowbit(x),cnt++;
    return cnt;
}

分析发现，这种方法在 1 较少的情况下比较快速：
0~32 次减法、自加、取反、操作，以及频繁的函数调用。

Solution3:

改进上一个方法：利用 i&(i-1) 简化操作：

int count3(unsigned int v)
{
    int cnt = 0;
    while(v) v &= (v-1),num++;
    return cnt;
}

分析可知，这种方法较上一种方法有微笑的进步。

Solution4:

转换思考方向：利用二叉树….

int count4(unsigned int v) 
{ 
    v = (v & 0x55555555) + ((v >> 1) & 0x55555555) ; 
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333) ; 
    v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f) ; 
    v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff) ; 
    v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff) ; 

    return v ; 
}

什么意思呢？分别求出二进制数相邻两个区块的 1 的个数，合并。
分析可知，这种方法大致做到了之前的算法无法达到的稳定复杂度。仿佛达到了效率的极限。

还能不能更快呢?

当然可以！下面介绍一些常规做法，和非常规做法。

Solution5 常规:

利用预处理求出的 1 个数表，可以高效地取得 x 前 16 位和后 16 位 1 的个数。

int num[1<<16];
int count5(unsigned int x)
{
    return (num[x&65535]+num[(x>>16)&65535]);
}
void init()
{
    for(int i=0;i<(1<<16);i++)num[i]=count4(i);
}

Solution6 常规：

和之后的几个方法都参考了 http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html 的介绍。

int count6(unsigned int x) 
{
    unsigned int tmp = x - ((x >>1) &033333333333) - ((x >>2) &011111111111);
    return ((tmp + (tmp >>3)) &030707070707) %63;
}

由于，有取模运算，速度可能不及以上的某些方法，但是也不失作为最脑洞方法的尊严。
至于为什么，可以参考上面链接提到的博客。

Solution7 非常规：

位标记法

struct _byte 
{ 
    unsigned a:1; 
    unsigned b:1; 
    unsigned c:1; 
    unsigned d:1; 
    unsigned e:1; 
    unsigned f:1; 
    unsigned g:1; 
    unsigned h:1; 
}; 

int count7( unsigned char b ) 
{
    struct _byte *by = (struct _byte*)&b; 
    return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h); 
}

Solution8 非常规：

CPU 指令法，但是首先得确定你的 CPU 支持 SSE4 指令，用 Everest 和 CPU-Z 可以查看是否支持。当然不推荐在信息学竞赛中使用。

#include <nmmintrin.h>
unsigned int n =127 ;
unsigned int bitCount = _mm_popcnt_u32(n) ;

综上，这几种各具特色的算法都有各自的优势，同时也有着不足。综合诸多因素考虑，我个人还是比较喜欢 Solution3 和 5 的。

存在性背包

通常会有这类背包问题：用价值分别为 Pi 的物品各无限个能否构成 Ci 的价格？
如果 Pi 都比较小，这种问题除了在剩余系下利用 SPFA 解决，也可以用位运算获得 1/64 的系数。
虽然应用范围并不广泛，但是实际上这种操作的威力还是比较大的。

class force1
{
    public:
    ll f[LEN],mask[4];
    int get_ok(int pos)
    {
        ll now=pos/L;
        ll mov=pos%L;
        ll a1=0,b1=0,a2=0,b2=0,a3=0,b3=0,a4=0,b4=0;
        if(now>=0)a1=f[now]&(mask[3]>>(L-mov-1));
        if(now>=1)b1=f[now-1]&(mask[3]<<(mov+1)),a2=(f[now-1]<<(L-mov-1))&mask[2];
        if(now>=2)b2=f[now-2]&(mask[2]<<(mov+1)),a3=(f[now-2]<<(L-mov-1))&mask[1];
        if(now>=3)b3=f[now-3]&(mask[1]<<(mov+1)),a4=(f[now-3]<<(L-mov-1))&mask[0];
        if(now>=4)b4=f[now-4]&(mask[0]<<(mov+1));
        if(a1||a2||a3||a4||b1||b2||b3||b4)return 1;
        return 0;
    }
    void set_mask(int pos)
    {
        mask[pos/L]|=((1LL<<ll(pos%L)));
    }
    void dp()
    {
        memset(mask,0,sizeof(mask));
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)set_mask(4*L-P[i]-1);
        f[0]=1;
        for(int i=1;i<=mxs;i++)if(get_ok(i))f[i/L]|=(1LL<<(i%L));
        int ans=0;
        for(int i=1;i<=m;i++)if(f[A[i]/L]&(1LL<<(A[i]%L)))ans++;
        cout<<ans<<endl;
    }
}f1;

快速求汉明距离

求两个 01 字串相同的位的个数
不用多说了，用位运算搞。结合之前的 count(x) 函数。

int dist(int a,int b)
{
    return count5(a&b);
}