框架
用四种方法算算一个整数中位1的个数,关键词:位运算、效率。
首先把整个框架给出来,用上次我写的那个比较算法时间复杂度的模板和例子:
1 | /* |
循环右移
要计算一个整数中位1的个数,最简单的就是循环右移然后取最低位就好啦~
代码:
1 | // 平均循环(INT_BIT)次 |
这个就不多说了,学过C语言的应该都能想到。平均循环(INT_BIT)次。
优化的循环右移
事实上,如果一个数只是低位有几个1,高位都是0,那么每次都循环INT_BIT次显然太浪费了,可以优化一下。
代码:
1 | // 平均循环(INT_BIT - N)次,N=前导零个数分布均值 |
核心就是一个while循环,前面的if主要是处理负数的。因为C语言没有逻辑右移(不管是不是负数都补零)只有算术右移(如果是负数就补一),我试了一下确实没找到逻辑右移,所以只好在前面处理一下负数了,x &= ~(1 << (INT_BIT - 1))
在我的电脑上其实就等价于x &= 0x7fffffff
,这样做可移植性比较好(看起来比较高级而已,估计也没其他人运行这个程序)。
平均循环(INT_BIT - N)次,N=前导零个数分布均值。想不到在这里居然会碰上前导零……话说我还是在STM32的uC/OS-III内核里第一次看到前导零这个东东。理论上来说,N应该可以算出一个确定的数值,具体涉及到有符号整数的二进制补码形式的前导零的概率分布,听起来似乎有点复杂,懒得算了……
x &= x - 1消去最右边的1
原谅我实在是不知道这个方法该取什么名字,索性就这样叫吧……顾名思义,核心就是这个位运算:x &= x - 1
,它可以消去x
最右边的一,举个栗子:
1 | 1010 (x=10) |
我觉得这个栗子很清楚明白了,所以直接上代码:
1 | // 平均循环(INT_BIT/2 - N)次 |
平均循环(INT_BIT/2 - N)次,这里假设整数是均匀分布的,这样每一位是0、1的概率各为50%,如果是其他分布的话就不是/2了。到底要不要减去前导零个数分布均值我没有想明白,应该是要吧,大概,因为循环次数也和前导零有关系……
查表
最后出场的方法通常是最厉害的,这次……也不例外。
顾名思义,查表嘛,你要问我怎么查?请看代码:
1 | // 平均循环(INT_BIT/M - N)次,M=log2(sizeof(table)),N=前导零个数分布均值 |
因为涉及右移,所以还是需要处理一下负数,然后查表。
平均循环(INT_BIT/M - N)次,M=log2(sizeof(table)),N=前导零个数分布均值。
总结
结果:
在算法的精简程度和时间复杂度之间需要有一个平衡,我觉得第三种方法取得了一个不错的平衡,核心代码就一个5行的while循环,因为是直接位运算也不需要考虑负数的情况。
如果需要更高的速度那么整一个M=5甚至M=6的查表法,如果还觉得想要更刺激一些,其实还有一些很变态的位运算方法,我从网上看到的,至今不太明白。那种方法不需要循环也不需要判断,直接几行位运算就得到结果了,估计怕是只有游戏核心引擎里才需要那么快的速度吧。