酱坛子

专注C++技术 在这里写下自己的学习心得 感悟 和大家讨论 共同进步(欢迎批评!!!)

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  65 Posts :: 16 Stories :: 236 Comments :: 0 Trackbacks

公告

王一伟 湖南商学院毕业 电子信息工程专业

常用链接

留言簿(19)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 356740
  • 排名 - 55

最新随笔

最新评论

阅读排行榜

评论排行榜

方法1:
//main.cpp
#include <iostream>

using namespace std;
 
int count_ones(int n)

{

       n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);

       n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);

       n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);

       n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);

       n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

 

       return n;

}

 

int main(int argc,char* argv[])

{
       cout<<count_ones(255)<<endl;

       return 0;
}

方法2:
const int one_in_char[256]=
{
    0, 1, 1, 2, 1, 2,2,3
......
                              ,8
}
此为 0-255 每个数中 1 的个数。  

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]];
}


本人觉得方法1更快速:)

posted on 2006-10-16 08:35 @王一伟 阅读(939) 评论(4)  编辑 收藏 引用 所属分类: 4. C++

Feedback

# re: 统计一个32位int中“1”位的个数 2007-01-05 15:34 pengkuny
请问,count_ones的原理是什么?
我对位操作不是很清楚  回复  更多评论
  

# re: 统计一个32位int中“1”位的个数 2007-01-08 12:26 王一伟
好的 我晚上前给你回复 写个详细的过程和原理给你 其实这个只需要自己自己动手算算就知道了 :)  回复  更多评论
  

# re: 统计一个32位int中“1”位的个数 2007-01-08 17:39 王一伟
n = 9

//第一次计算 此时 n = 0000 0000 0000 0000 0000 0000 0000 1010

0000 0000 0000 0000 0000 0000 0000 1010
0101 0101 0101 0101 0101 0101 0101 0101 //0x55555555
&--------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0000


0000 0000 0000 0000 0000 0000 0000 1010
1010 1010 1010 1010 1010 1010 1010 1010 //0xaaaaaaaa
&--------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1010

0000 0000 0000 0000 0000 0000 0000 1010
>>1---------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101

0000 0000 0000 0000 0000 0000 0000 0000
+ 0000 0000 0000 0000 0000 0000 0000 0101
----------------------------------------------------------------
= 0000 0000 0000 0000 0000 0000 0000 0101

//第二次计算 此时 n = 0000 0000 0000 0000 0000 0000 0000 0101

0000 0000 0000 0000 0000 0000 0000 0101
0011 0011 0011 0011 0011 0011 0011 0011 //0x33333333
&------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001

0000 0000 0000 0000 0000 0000 0000 0101
1100 1100 1100 1100 1100 1100 1100 1100
&------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0100

....... >>2

0000 0000 0000 0000 0000 0000 0000 0001
+ 0000 0000 0000 0000 0000 0000 0000 0001
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010

//第三次计算 此时 n = 0000 0000 0000 0000 0000 0000 0000 0010

0000 0000 0000 0000 0000 0000 0000 0010
0000 1111 0000 1111 0000 1111 0000 1111 //0x0f0f0f0f
&-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010

0000 0000 0000 0000 0000 0000 0000 0010
1111 0000 1111 0000 1111 0000 1111 0000
&-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0000
......>>4
相加 还是得 0000 0000 0000 0000 0000 0000 0000 0010
后面的就不写了






  回复  更多评论
  

# re: 统计一个32位int中“1”位的个数 2008-11-16 09:41 belo
其实这种方法比起传统方法更慢
这是我的一个实现版本:
#include <iostream>
using namespace std;

int count_bits1(int n)
{
n = (n & 0x55555555) + ((n & 0xAAAAAAAA) >> 1); //计算相邻两位的bit和
n = (n & 0x33333333) + ((n & 0xCCCCCCCC) >> 2); //计算相邻四位的bit和
n = (n & 0x0F0F0F0F) + ((n & 0xF0F0F0F0) >> 4); //计算相邻八位的bit和
n = (n & 0x00FF00FF) + ((n & 0xFF00FF00) >> 8); //计算相邻16位的bit和
n = (n & 0x0000FFFF) + ((n & 0xFFFF0000) >> 16); //计算相邻32位的bit和

return n;
}

int count_bits2(int n)
{
int count = 0;
while(n)
{
count++;
n = n & (n-1);
}

return count;
}

int main(void)
{
cout << count_bits1(0xFF) << endl;
cout << count_bits2(0xFF) << endl;

return 0;
}

你可以反汇编一下,然后就知道了  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理