向“世界上最快的判断32位整数二进制中1的个数的算法”挑战

connet

const int one_in_char[256]=
{
    0, 1, 1, 2, 1, 2,2,3
......
                              ,8
}
此为 0-255 每个数中 1 的个数。
这个雕虫小技在密码，crc...等地方使用很广泛。
int func2(int v)
{
    int n=v;
    unsigned char *ptr=(unsigned char *)&n;
    return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
对任何数，任何体系结构的cpu， 只要 sizeof(int)-1 次加法。
而且很容易扩展到任何数据类型。
使用 case最慢， 使用条件转移要受流水线预测错误的干扰。

唯吾顾家三少

绝世神帖，楼主给力

InMySin

在stackoverflow找到类似的。。
http://stackoverflow.com/questio ... count-positive-bits

原来还可以改进算法，我去。。。最后是用硬件指令直接做？！

fallening

C++ 的呢？

1. template<size_t n>
   
2. struct count_1
   
3. {
   
4.   enum{value=(n&1)+count_1<(n>>1)>::value;};
   
5. };
   
6. 
   
7. template<>
   
8. struct count_1<0>
   
9. {
   
10.   enum {value=0;};
    
11. };
    
12. 
    
13. 
    
14. template<>
    
15. struct count_1<1>
    
16. {
    
17.   enum {value=1;};
    
18. };
    
19. 
    
20. 
    

复制代码

leizisdu

回复 3# mik
顶！

gamago

都别吵啦。
这个题目在这里很久以前就讨论过，不止一次。

网上有关于这个题目的总结性网页，大家不用闭 ...
assiss 发表于 2006-07-20 15:03

学习喽，呵呵。

ai4life

大家有必要这么高热情嘛！！！楼主的方法很普通啊

mailjzwu_1

学习学习！大家热情高阿！

lenovo

原帖由 assiss 于 2006-7-21 13:06 发表


原来你是yuxh的马甲？难怪。

晕，地球人都知道。

achun.shx

大家用空间换时间确实是个好办法。
其实很多优秀的程序都这样干，
不过大家的热情竟然这么高，是在是让人摸不着头脑。