| 站点地图 | 联系我
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 上善若水 厚德载物
 现在位置 :: 主页 >> 资料中心 >> ROOT / CODE / ARITHMETIC /
 

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

来源(ChinaUnix.net)

From: http://www.chinaunix.net/jh/23/795048.html

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

--------------------------------------------------------------------------------

http://www.chinaunix.net 作者:connet 发表于:2006-07-21 01:09:45
【发表评论】【查看原文】【C/C++讨论区】【关闭】

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最慢, 使用条件转移要受流水线预测错误的干扰。


Link: http://www.asm32.net/article_details.aspx?id=1401


浏览次数 631 发布时间 2006/7/21 2:26:06 从属分类 ARITHMETIC 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 京ICP备09029108号-1