• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

【转】C语言 统计整数二进制表示中1的个数

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

主要是为了记录最后一种神奇的方法。

原文地址:http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152408.html

 

这是一个很有意思的问题,也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight,而且wikipedia上也提供了很好的位运算解决的方法,这个下面也会提到。

解决这个问题的第一想法是一位一位的观察,判断是否为1,是则计数器加一,否则跳到下一位,于是很容易有这样的程序。

int test(int n)
{
    int count=0;
    while(n != 0){
        if(n%2 ==1)
            count++;
        n /= 2;
    }
    return count;
}

或者和其等价的位运算版本:

int test(int n)
{
    int count=0;
    while(n != 0){
        count += n&1;
        n >>= 1;
    }
    return count;
}

这样的方法复杂度为二进制的位数,即,于是可是想一下,有没有只与二进制中1的位数相关的算法呢。

可以考虑每次找到从最低位开始遇到的第一个1,计数,再把它清零,清零的位运算操作是与一个零,但是在有1的这一位与零的操作要同时不影响未统计过 的位数和已经统计过的位数,于是可以有这样一个操作 n&(n-1) ,这个操作对比当前操作位高的位没有影响,对低位则完全清零。拿6(110)来做例子,第一次 110&101=100,这次操作成功的把从低位起第一个1消掉了,同时计数器加1,第二次100&011=000,同理又统计了高位的 一个1,此时n已变为0,不需要再继续了,于是110中有2个1。

代码如下:

int test(int n)
{
    int count=0;
    while(n != 0){
        n &= n-1;
        count ++;
    }
    return count;
}

这几个方法虽然也用到了位运算,但是并没有体现其神奇之处,下面这个版本则彰显位运算的强大能力,若不告诉这个函数的功能,一般一眼看上去是想不到这是做什么的,这也是wikipedia上给出的计算hamming_weight方法。

int test(int n)
{
    n = (n&0x55555555) + ((n>>1)&0x55555555);
    n = (n&0x33333333) + ((n>>2)&0x33333333);
    n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
    n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
    n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
  
    return n;
}

没有循环,5个位运算语句,一次搞定。

比如这个例子,143的二进制表示是10001111,这里只有8位,高位的0怎么进行与的位运算也是0,所以只考虑低位的运算,按照这个算法走一次

+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143
+---+---+---+---+---+---+---+---+
|  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次运算后
+-------+-------+-------+-------+
|    0 0 0 1    |    0 1 0 0    |   <---第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <---第三次运算后,得数为5
+-------------------------------+

这里运用了分治的思想,先计算每对相邻的2位中有几个1,再计算每相邻的4位中有几个1,下来8位,16位,32位,因为2^5=32,所以对于32位的机器,5条位运算语句就够了。

像这里第二行第一个格子中,01就表示前两位有1个1,00表示下来的两位中没有1,其实同理。再下来01+00=0001表示前四位中有1个1,同样的10+10=0100表示低四位中有4个1,最后一步0001+0100=00000101表示整个8位中有5个1。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
《learning hard C#学习笔记》读书笔记(19)多线程发布时间:2022-07-13
下一篇:
c语言学习_part01_c_primer_plus_chapter03_数据与c发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap