位运算总结（一）

常见问题：计算一个数字中的最低位为1的位置、或者统计数字中1的个数

常见的问题为计算一个数字的二进制中最低比特位为1的位置、以及比特位为1的数量，解法有使用GCC库函数:__bulitin_popcount(uint)、lowbit以及暴力法(循环判断每一位是否为1)。

思路1：利用库函数__bulitin_popcount(uint)。

思路2：利用n&(-n)的结果恰好为n的为最低位置为0的结果，例如6(110)&5(101)=4(100)。

1
2
3
4
5
6
7
8
9
10
int getCount(int x)
{
    int ans=0;
    while(x)
    {
        ++ans;
       x&=(x-1); 
    }
    return ans;
}

思路3：利用lowbit()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lowbit(uint x)
{
	return x&(-x);
}
int getCount(int x)
{
    int ans=0;
    while(x)
    {
        ++ans;
        x-=lowbit(x); // 采用lowbit减去最低位的1的数值继续计算
    }
    return ans;
}

lowbit算法

主要功能：计算一个数字中最低位1所代表的的数字，例如lowbit(6)=2（110中的最低位1位置为2）。

主要原理：利用x&-x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lowbit(uint x)
{
	return x&(-x);
}
int getCount(int x)
{
    int ans=0;
    while(x)
    {
        ++ans;
        x-=lowbit(x); // 采用lowbit减去最低位的1的数值继续计算
    }
    return ans;
}