本文共 2024 字,大约阅读时间需要 6 分钟。
第一次写关于算法的问题。今天数据库课老师在讲数据库底层实现的时候提到了位图索引,最后归结为1的个数,以前看到很多次关于1的个数的计算,今天总结一下。
最开始是有《编程之美》里面的问题引出的:如何最快地读取到二进制中1的个数.
最开始我也是感觉一个个地数不就完了,但是人家说了要求最快。一个个的数是O(N)级的。
1. 比如:int count=0;
for(;x;x>>1)
{
count++;
}//当然也有每次用x直接除以2 的。
2.后来就是用x&(x-1)的结果是否为0来判断,如果为零,有一个1,否则没有。
所以有:
for(;x;count++)
x&=x-1;
3.查表大法,就是一一列举这n位二进制所有的可能到数组中,然后直接查表就是了,这里就不赘述了
4.这个新的方法叫shift and add,正如名字一样,该算法用的就是shift 和add(移位和加法):
对于n位二进制数,最多有n个1,而n必定能由n位二进制数来表示,因此我们在求出某k位中1的个数后,可以将结果直接存储在这k位中,不需要额外的空间。
以4位二进制数abcd为例,最终结果是a+b+c+d,循环的话需要4步加法
那么我们让abcd相邻的两个数相加,也就是 a+b+c+d=[a+b]+[c+d]
[0 b 0 d]
[0 a 0 c]
--------
[e f] [ g h]
ef=a+b gh=c+d 而 0b0d=(abcd)&0101,0a0c=(abcd)>>1 &0101
[ef] [gh]再相邻的两组相加
[00 ef]
[gh]
--------
i j k l
ijkl=ef+gh gh=(efgh)&& 0011 ,ef=(efgh)>>2 & 0011
依次入次递推。需要log(N)次
代码如下:
typedef unsigned __int64 uint64; //assume this gives 64-bits
const uint64 m1 = 0x5555555555555555; //binary: 0101...
const uint64 m2 = 0x3333333333333333; //binary: 00110011..
const uint64 m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint64 m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
int popcount_1(uint64 x) {
x = (x & m1 ) + ((x >> 1) & m1 );
x = (x & m2 ) + ((x >> 2) & m2 );
x = (x & m4 ) + ((x >> 4) & m4 );
x = (x & m8 ) + ((x >> 8) & m8 );
x = (x & m16) + ((x >> 16) & m16);
x = (x & m32) + ((x >> 32) & m32);
return x;
}
5.对shift and add的优化:
看到有三种优化,这里只提两种吧
1
int popcount_2(uint64 x)
{
x -= (x >> 1) & m1;
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m4;
x += x >> 8;
x += x >> 16;
x += x >> 32;
return x & 0x7f;
}
2.
int popcount_3(uint64 x) {
x -= (x >> 1) & m1;
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m4;
return (x * h01)>>56;
据说这可是MIT的牛人想出来的高招(当时是求余,现在换成除法了更快)
我也是参见了wikipedia(但是看不懂)和http://blog.ibread.net/375/pop-count-problem/上面的文章。
int popcount_3(uint64 x) {
x -= (x >> 1) & m1;
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m4;
return (x * h01)>>56;
转载地址:https://blog.csdn.net/weixin_33093437/article/details/111973141 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!