所谓的1位计数就是计算一个非负的整数用二进制表示时有几个1,例如
十进制5=二进制0101,1位计数=2
看起来似乎很简单的算法啊,只要把二进制中每一位遍历一遍判断是否为1就可以了,写出代码大概是这个样子
第一种算法:
typedef unsigned int uint;
int pop(uint x)
{
int num = 0;
for (int i = 0; i < 32; i++)
{
num += (x & (1 << i)) > 0;
}
return num;
}
这个算法足够的清晰,这就是最简单的穷举法了,但是效率却非常的低,要循环32次,这个算法的复杂度是o(n)
第二种算法:
int pop(uint x)
{
int num = 0;
while (x != 0)
{
num++;
x = x & (x - 1);
}
return num;
}
其实这个算法也非常简单,而且也符合我们习惯的思维方式,就是从低位开始找含有1的位,找到后计数并置为0,直到找不到1位结束
其中的num仅仅是简单的计数
x = x & (x - 1);就是把最右边的1置为0的算法,参考我的另一篇文档<<位运算>>
这个算法的复杂程度取决于1的数目,如果1位很少,这个算法非常的快,如果1位很多呢?下面的算法应该更有效一些
int pop(uint x)
{
int num = 0;
x = ~x;
while (x != 0)
{
num++;
x = x & (x - 1);
}
return 32 - num;
}
先对x取反,再找1位的数目,其实这里找的是原来0位的数目,因此最终的结果是32-num
可惜我们根本不能假设1位的数目是多还是少,因此这个算法的复杂度是o(n/2)
第三种算法:
int pop(uint x)
{
int num = x;
while (x != 0)
{
x = x >> 1;
num -= x;
}
return num;
}
这个算法和第二种算法类似,只不过把找1置0的过程变成了右移做减法
这个算法来源于公式:
pop(x)=x-Σ(x>>i)
其实这来自于更直观的公式:
Σ2**i=2**(i+1)-1
也就是
1=2**(i+1)-Σ2**i
翻译白话就是对于二进制a000...来说,a位1的数目就是a000...-0111...
因为对任意位a都成立,因此把所有位叠加起来就是带x的公式了
这个算法循环的数目取决于最左边的1在第几位,因此平均的复杂度是o(n/2),而且加法运算也不如&运算
第四种算法:
int pop(uint 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;
}
如果说算法一是最简单的穷举思想,算法二,算法三可以称为递推或者递归的思想,那么算法四就是大大有名的分治思想了
复习一下,分治算法的一般步骤是:分解,解决,合并
分解:
具体到这个问题就是要算32位的二进制1计数,可以分解为计算16位,8位,4位,2位,1位的二进制1计数
解决:
而1位的二进制1计数是简单的,就是本身嘛
合并:
把两个连续的1位的二进制1计数相加放到一个2位的二进制中
x = (x & 0x55555555) + ((x >> 1) & 0x55555555); //其中的0x55555555应该理解为0x01010101010101010101010101010101
把两个连续的2位的二进制1计数相加放到一个4位的二进制中
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); //其中的0x33333333应该理解为0x00110011001100110011001100110011
把两个连续的4位的二进制1计数相加放到一个8位的二进制中
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); //其中的0x0F0F0F0F应该理解为0x00001111000011110000111100001111
把两个连续的8位的二进制1计数相加放到一个16位的二进制中
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); //其中的0x00FF00FF应该理解为0x00000000111111110000000011111111
把两个连续的16位的二进制1计数相加放到一个32位的二进制中
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF); //其中的0x0000FFFF应该理解为0x00000000000000001111111111111111
最终x就是32位二进制数的1计数
这个算法的复杂度是o(logn),对于32位整数来说,只有5步
当然,这个算法还可以再进一步的优化,为了节省几个CPU指令,但是这已经无关紧要了,因为本质上还是同样的思想
第五种算法:
int pop(uint x)
{
static char table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
return table[x & 0xF] +
table[x >> 4 & 0xF] +
table[x >> 8 & 0xF] +
table[x >> 12 & 0xF] +
table[x >> 16 & 0xF] +
table[x >> 20 & 0xF] +
table[x >> 24 & 0xF] +
table[x >> 28 & 0xF];
}
标准的查表法,以空间换取时间,这确实是一个非常简单而且无趣的算法,如果我们不在乎这点空间,这个算法确实是非常有效的,特别是把table开到256个大小
参考<<高效程序的奥秘>>