求一个整数的bit位中1的个数

noword2k

刘五十三 发表于 2012-07-08 12:53
最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。

没清茶和新闻了，失业了？
C/C++版块，扯数字电路逻辑门，这不瞎JB扯淡吗？

selfrun

A:位操作
    一次移位加法完成多个位的数据累加(对于32位整数，5次分别是16、8、4、2、1),时间复杂度是O(log(8*n))，编译器优化的最好结果是只有1次内存数据访问。
B:查表
    直接从内存取结果累加，不过cpu读内存也是顺序访问，时间复杂度是O(n),32位整数，至少4次内存访问。

曾经在intel 和amd处理器上比较过这两个方法，貌似一种处理器是A方法快，另一种处理器是B方法快。从复杂度分析上看，64位的应该是A方法好些

用循环的一定会变慢，因为分支预测失败，指令队列会被清空

群雄逐鹿中原

刘五十三 发表于 2012-07-08 12:53
最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。

TTL门的响应时间在几个纳秒到几十纳秒，
CMOS门电路的响应时间更长，
算下来处理频率也就几十M到几百M，1G都不到。

你能搭出的很简单的逻辑电路，速度将会快不过当今一些常见的CPU。
而且你还得考虑如何处理输出输出，
你的输入输出能快过CPU cache的效能吗？

或者用FPGA或CPLD这些相对较复杂的编程逻辑器件？

vhghhd

int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}

刘五十三

群雄逐鹿中原 发表于 2012-07-09 15:15
TTL门的响应时间在几个纳秒到几十纳秒，
CMOS门电路的响应时间更长，
算下来处理频率也就几十M到几百M，1G都不到。

你能搭出的很简单的逻辑电路，速度将会快不过当今一些常见的CPU。
而且你还得考虑如何处理输出输出，
你的输入输出能快过CPU cache的效能吗？

或者用FPGA或CPLD这些相对较复杂的编程逻辑器件？

cpu本质就是逻辑门搭出来的。任何cpu的动作都是逻辑门的逻辑运算而已。逻辑门直接处理比cpu运算快几倍几十倍不是啥问题。就是你说的cpu cache，一样是逻辑门组成的。

比如以前的硬盘拷贝数据到内存，用dma比cpu快就是个例子，dma处理的时候，芯片直接接管总线然后挂起cpu,把数据拷贝到内存后再释放总线给cpu。

刘五十三

noword2k 发表于 2012-07-09 09:33
没清茶和新闻了，失业了？
C/C++版块，扯数字电路逻辑门，这不瞎JB扯淡吗？

嗯，好在你又给我发了5毛。日子还过得去。你别老把啥都泛政治化，是不是要把我的方法打成五毛反动编程，然后再踏上一只脚，永世不得翻身啊。

sb_oy

还是4楼的算法比较犀利！

群雄逐鹿中原

刘五十三 发表于 2012-07-17 12:35
cpu本质就是逻辑门搭出来的。任何cpu的动作都是逻辑门的逻辑运算而已。逻辑门直接处理比cpu运算快几倍几 ...

你这个是脱离现实的臆想而已。

这里逻辑门不是问题，我也相信你能搭出来。
问题在于工艺。相同的电路，在不同的工艺下，速度可是差距极大。
你搭出来的，和大规模集成电路工艺实现的，效果完全不一样。

hshopeful

回复 5# 塑料袋
您能把这段代码稍微解释一下吗？那些个掩码是怎么确定的！？谢谢！

   

db1984

定义一个表不就解决了吗

bitTable[256]={0,1,1,2,2,.........0~255的bit为1的数量}

32bit的整数

bitTable[x1] + bitTable[x2] + bitTable[x3] + bitTable[x4]