位运算

1.求该数中1的个数

int getsum(int x)
{
    int cnt = 0 ;
    while(x)
    {
        cnt ++ ;
        x &= x-1 ;
    }
    return cnt ;
}

View Code

下面是高效一点的

1 int getsum(int x)
2 {
3     x=(x& 0x55555555)+((x>>1)& 0x55555555);
4     x=(x& 0x33333333)+((x>>2)& 0x33333333);
5     x=(x& 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F);
6     x=(x& 0x00FF00FF)+((x>>8)& 0x00FF00FF);
7     x=(x& 0x0000FFFF)+((x>>16)& 0x0000FFFF);
8     return x;
9 }

View Code

2.判断二进制中的1的个数是偶数个还是奇数个

int have_jo(int x)
{
    x=x^(x>>1);
    x=x^(x>>2);
    x=x^(x>>4);
    x=x^(x>>8);
    x=x^(x>>16);
    return x&1;
}

View Code

3.求二进制的逆序

int dword(int x)
{
    x=(x& 0x55555555)<<1  | (x& 0xAAAAAAAA)>>1;
    x=(x& 0x33333333)<<2  | (x& 0xCCCCCCCC)>>2;
    x=(x& 0x0F0F0F0F)<<4  | (x& 0xF0F0F0F0)>>4;
    x=(x& 0x00FF00FF)<<8  | (x& 0xFF00FF00)>>8;
    x=(x& 0x0000FFFF)<<16 | (x& 0xFFFF0000)>>16;
    return x;
}

View Code

把右边连续的1变为0 ---------> x&(x+1)

把右边连续的0变为1---------->x | (x- 1)

取右边连续的1------------------>(x^(x+1))>>1

去掉右边第一个1的左边------>x&(x^(x-1))