« 前一篇:网站首页head 区代码规范
后一篇:研究生 »

经典算法:数一 @ 3/9/2006

学习类
下面的函数得到数t的二进制表示中1的个数:
template <typename T> size_t foo(T t) {
    size_t ret = 0;
    while (t) {
        t &= t - 1;
        ++ret;
    }
    return ret;
}
发布于 3/9/2006 14:16:31 | 评论:3
吴雨 @ 3/9/2006 14:25:12
The hacker's delights里头的hard code的做法,会快一点。

假设x是32位的数,统计x中1的个数。共log(32)五步:
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);
3dot14 @ 3/11/2006 1:14:19
第一个看过,不过第二个实在觉得凭空想不太好想出来,我觉得肯定是根据什么公式推算出来的吧!
gmcat @ 7/12/2006 8:51:29
分治法

看帖要回帖...

categories
archives
links
statistics
  • 网志数:1170
  • 评论数:2013