一道很简单的题目,计算某个32位无符号数中每个比特位1出现的次数,一开始直接遍历每个位,当然不可能遍历32个位,这样效率太低,4个位一起遍历,然后根据该4bit的值来直接switch出1出现的比特数,这样算法的时间复杂度是O(1),只需要循环32/4=8次,当然结果是无误的,这样也打败了 100% 的cpp提交 :) 当然这个实现的代码实在太长,太难看,于是搜下有没有什么好的解决方法,于是就搜到了这个 n&(n-1)

貌似《编程之美》上提过这个,看来有空可以补补,自身某些方面知识有所欠缺是从工作的时候就知道的,当然欠缺的部分,对于工作是没有多大影响的,但是会限制高度,有空余时间还是得好好的查漏补缺,只是为了自己。

不谈别的了,先来看看这个小技巧,简单分析下。

比如当前有个数n=57,它的二进制表示为 11 1001,我们再来看下-1的结果 11 1000 ,我们将它们进行位与 11 1000,我们看到了最终的结果相比n,最右边的某bit位的1被抹除了。

再来看看借位的例子:

n=1101 1000 n-1=1101 0111 n&(n-1)=1101 0000

可以看到相比n,结果还是把最后一个1的比特位给抹除了,那么我们只要对n不断的进行这种操作,直到n为0,那么1的个数也就被计算出来了。

共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day