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

求二进制数中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);
}
分类: 文章

1 条评论

【算法】 简单的常数优化和编程技巧 —B_Z_B_Y – K-XZY · 2018年10月10日 7:19 下午

[…] 位运算那些令人咋舌的技巧 -boshi […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *