忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
1234下一页
最近访问板块 发新帖
查看: 18953 | 回复: 38

求一个整数的bit位中1的个数 [复制链接]

论坛徽章:
1
狮子座
日期:2014-03-27 12:53:15
发表于 2012-07-04 21:15 |显示全部楼层
给一个整数,求这个整数的bit位的1的个数,要求,最快算法:

int count(int ipNumber)
{
        int counter =0;
        int tmp(ipNumber);
        while( tmp != 0)
        {
                if ( tmp % 2 == 0)
                        tmp /=2;
                else
                {
                        ++counter;
                        tmp /=2;
                }
        }
        return counter;
}

我只想到了用将10进制转为2进制的方式,来求这个int数据中的bit位中1的个数。

可否使用移位运算,又该如何用??还有没有其他方式??

谢谢

论坛徽章:
4
戌狗
日期:2013-08-15 18:22:43技术图书徽章
日期:2013-08-21 13:48:45巨蟹座
日期:2013-09-26 17:06:39处女座
日期:2013-12-25 11:26:10
发表于 2012-07-04 21:46 |显示全部楼层
这个有标准的算法的

32位的int,做4次移位和加法运算,就能算出来。

论坛徽章:
2
CU大牛徽章
日期:2013-04-17 11:46:28CU大牛徽章
日期:2013-04-17 11:46:39
发表于 2012-07-04 21:48 |显示全部楼层
本帖最后由 cdtits 于 2012-07-05 09:48 编辑

这样行不?
  1. int count(unsigned int num)
  2. {
  3.     int n = 0;
  4.     while (num) {
  5.         if (num & 1)
  6.             n++;
  7.         num >>= 1;
  8.     }
  9.     return n;
  10. }
复制代码

论坛徽章:
4
戌狗
日期:2013-08-15 18:22:43技术图书徽章
日期:2013-08-21 13:48:45巨蟹座
日期:2013-09-26 17:06:39处女座
日期:2013-12-25 11:26:10
发表于 2012-07-04 22:20 |显示全部楼层
unsigned int hweight32(unsigned int w)
{
        unsigned int res = w - ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res + (res >> 4)) & 0x0F0F0F0F;
        res = res + (res >> ;
        return (res + (res >> 16)) & 0x000000FF;
}

论坛徽章:
4
戌狗
日期:2013-08-15 18:22:43技术图书徽章
日期:2013-08-21 13:48:45巨蟹座
日期:2013-09-26 17:06:39处女座
日期:2013-12-25 11:26:10
发表于 2012-07-04 22:21 |显示全部楼层
本帖最后由 塑料袋 于 2012-07-04 23:07 编辑

  1. unsigned int hweight32(unsigned int w)
  2. {
  3.         unsigned int res = w - ((w >> 1) & 0x55555555);
  4.         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
  5.         res = (res + (res >> 4)) & 0x0F0F0F0F;
  6.         res = res + (res >> 8);
  7.         return (res + (res >> 16)) & 0x000000FF;
  8. }
复制代码
以前哥们有一次去novell面试,上来就问脑筋急转弯。
第一个疯狗咬人,人不能咬疯狗的,不会。
第二个就是这个,我该装装B,可是当时想也没想,直接说这种题早就有标准算法了。
然后over


@pmerofc,专家,评论下这段代码呗?

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:50:28
发表于 2012-07-05 09:26 |显示全部楼层

论坛徽章:
0
发表于 2012-07-05 11:06 |显示全部楼层
3#不错的。。。

论坛徽章:
4
戌狗
日期:2013-08-15 18:22:43技术图书徽章
日期:2013-08-21 13:48:45巨蟹座
日期:2013-09-26 17:06:39处女座
日期:2013-12-25 11:26:10
发表于 2012-07-05 12:14 |显示全部楼层
lxk899 发表于 2012-07-05 11:06
3#不错的。。。


我贴的那段代码才是王道啊,不信让@pmerofc来评论一下

论坛徽章:
0
发表于 2012-07-05 13:10 |显示全部楼层

上次貌似有谁发过一个链接,专门讨论这个以及各种优化。

论坛徽章:
0
发表于 2012-07-05 14:46 |显示全部楼层
  1. switch(i)
  2. {
  3.    case 0x01:
  4.    case 0x02:
  5.    case 0x04:
  6.    case 0x08:
  7.    case 0x10:
  8.    ...
  9.       count = 1;
  10.    case 0x0003:
  11.    ...
  12.       count = 2;
  13.    ...
  14. }
  15. repeat and sum+=count;
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP