本文共 1526 字,大约阅读时间需要 5 分钟。
最近在看《Programming Pearls》。里面的好些问题很有意思。做一点小小的总结吧。
这个问题是计算一个unsigned int型二进制数中一个的个数,google中看到了不少很巧妙的算法,在这里做一个简单总结。另外,很喜欢stackoverflow这个论坛,geek很多,打酱油的人很少,感觉国外的程序员遇到有趣的问题兴致更高。关于这个问题,帖子见http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer。
最简单最直观的想法是检测每一位是不是1,如果是的话就计数器加1,最后肯定能得出结果来。虽然"too simple, sometimes naive",但是一般情况下是很好用的,需要的时候不用到处查,很快就能写出来。
下面的程序思路一样,也是每位检测:
下面的这种方法比较巧妙,已经比较难想到了。可以动手试试n-1的二进制表达就明白了。
这里面的方法属于那种“此曲只应天上有”的类型,我都没有尝试去理解,用的时候查一下就好了。
下面的程序只有一句话,调用系统库函数 __builtin_popcount,我在gcc下编译运行是可以的。
转载地址:http://etxli.baihongyu.com/