统计无符号整数二进制中1的个数(Hamming weight)

1.问题来源

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙的解法。查找网上资料,才知道这个问题的正式的名字叫Hamming weight(汉明重量)。

2.问题描述

对于一个无符号整型数,求其二进制表示中1的个数。比如12的以32位无符号整型来表示,其二进制为:00000000 00000000 00000000 00001100,那么12的二进制中1的个数是两个。

3.具体解法

方法一: 移位法

网上的对这种方法的称谓五花八门,个人权且称之为移位法,因为比较形象贴切地描述了这个方法具体实现。

#include <stdint.h>

int count1(uint32_t x){
    int count=0;
    while(x){
        if(x&0x1)
            ++count;
        x=(x>>1);
    }
    return count;
}

方法二:去1法 因为网上没有对之权威的称谓,个人还是权且称之为”去1法”,因为这种方法中,x&(x-1)将会减少x二进制中最右边的1,直至x变为0。

int count1(uint32_t x){
    int count = 0;
    while(x){
        x = x & (x-1);
        count++;
    }
    return count;
}

与之相似的变形是可以先统计出二进制数中0的个数,统计方法是x=x|(x+1)的作用是每次循环把x的二进制中从右往左数的第一个0变成1,直道变成全1的时候x+1就溢出为全0,循环结束。

int count1(int x){  
  int n=0;  
  while((x+1)){  
    n++;  
    x|=(x+1);
  }
  return 32-n;  
} 

方法三:分治法 这个方法是Hamming weight Wikipedia上面提出来的,很高效,比上面的两种方法都要高效。采用了分治法的思想,具体实现如下:

int Hamming_weight(uint32_t 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;  
}

代码解析: 乍一看,立马懵逼,很难看懂为何那么写。先将代码中用到的几个常数对比一下其特点,再联想到分治的思想,你可能就懂了。

0x5555……这个换成二进制之后就是01 01 01 01 01 01 01 01…… 
0x3333……这个换成二进制之后就是0011 0011 0011 0011…… 
0x0f0f………这个换成二进制之后就是00001111 00001111……

看出来点什么了吗? 如果把这些二进制序列看作一个循环的周期序列的话,那么第一个序列的周期是2,每个周期是01,第二个序列的周期是4,每个周期是0011,第三个的周期是8,每个是00001111,第四个和第五个以此类推。看出了这些数的特点,再回头看代码你会轻松的发现代码的意义。算法的实现原理是将32位无符号整数分成32个段,每个段即1bit,段的取值可表示当前段中1的个数,所以将32个段的数值累加在一起就是二进制中1的个数,如何累加呢?这就是代码做的事情。 (n&0x55555555)+((n>>1)&0x55555555) 将32位数中的32个段从左往右把相邻的两个段的值相加后放在2bits中,就变成了16个段,每段2位。同理(n&0x33333333)+((n>>2)&0x33333333)将16个段中相邻的两个段两两相加,存放在4bits中,就变成了8个段,每段4位。以此类推,最终求得数中1的个数就存放在一个段中,这个段32bits,就是最后的n。

看懂了上面几行的代码,你会情不自禁的想说:妙,太妙了!算法的世界总是那么奇妙。你也许可能会问,有没有更优的方法了,还真有,Hamming weight Wikipedia还有对该方法的优化,有心者继续探究吧,我就此打住,不和大家一同前行啦。

方法四:位标记法 巧妙的使用位域结构体来标记32位无符号整数每个位,最后将32个位相加得到1的个数。可见这里的累加方法明显与上面不同,代码也是略显膨胀。

struct BitStruct{
        uint8_t a:1;uint8_t b:1;uint8_t c:1;uint8_t d:1;uint8_t e:1;uint8_t f:1;uint8_t g:1;uint8_t h:1;
        uint8_t a1:1;uint8_t b1:1;uint8_t c1:1;uint8_t d1:1;uint8_t e1:1;uint8_t f1:1;uint8_t g1:1;uint8_t h1:1;
        uint8_t a2:1;uint8_t b2:1;uint8_t c2:1;uint8_t d2:1;uint8_t e2:1;uint8_t f2:1;uint8_t g2:1;uint8_t h2:1;
        uint8_t a3:1;uint8_t b3:1;uint8_t c3:1;uint8_t d3:1;uint8_t e3:1;uint8_t f3:1;uint8_t g3:1;uint8_t h3:1;
};

//get number of 1 
int count1(uint32_t x){
    BitStruct* stBit=(BitStruct*)&x; 
    return (stBit->a+stBit->b+stBit->c+stBit->d+stBit->e+stBit->f+stBit->g+stBit->h+
            stBit->a1+stBit->b1+stBit->c1+stBit->d1+stBit->e1+stBit->f1+stBit->g1+stBit->h1+
            stBit->a2+stBit->b2+stBit->c2+stBit->d2+stBit->e2+stBit->f2+stBit->g2+stBit->h2+
            stBit->a3+stBit->b3+stBit->c3+stBit->d3+stBit->e3+stBit->f3+stBit->g3+stBit->h3); 
}

方法五:指令法 popcnt assembly 超简洁,感谢网友Milo Yip提供。使用微软提供的指令,首先要确保你的CPU支持SSE4指令,用Everest和CPU-Z可以查看是否支持。

cout<<_mm_popcnt_u32(0xffffffff)<<endl;

方法六:MIT HAKMEM 169算法 MIT HAKMEM是1972由MIT AI Lab(Massachusetts Institute of Technology Artificial Intelligence Laboratory,麻省理工学院人工智能实验室)发表的一篇技术报告,里面描述了一些技巧性很强,很有用的算法,用来更快更有效地进行数学运算。其中第169个算法,就跟popcount有关,用来统计整数二进制中1的个数。HAKMEM是“hacks memo”的简写,意为技巧备忘录。

原始的代码是用汇编写的,翻译成C代码如下:

int HAKMEM(uint32_t n){  
    uint32_t tmp;
    tmp=n-((n>>1)&033333333333)-((n>>2)&011111111111);
    tmp=(tmp+(tmp>>3))&030707070707;
    return tmp%63;
}

乍一看,绝对懵逼,上面的代码究竟是什么意思,下面给大家作简要的分析。

总共需要3次shift,3次and,2次sub,1次add, 1次mod共10次算数运算。这是32位整数的版本,改成适用于64位整数的版本也很简单。主要思想也是分治以及并行加法,其中文字常量如033333333333都是8进制的数。

第一步: n-((n>>1)&033333333333)-((n>>2)&011111111111);表示的意思是将n中的二进制1的个数分段存储在从右至左的每一个3个bits的段中。比如一个3位二进制数是4a+2b+c,我们要求的是a+b+c,n>>1的结果是2a+b,n>>2的结果是a,所以: (4a+2b+c) - (2a+b) - (a) = a + b + c。

第二步: (tmp+(tmp>>3))&030707070707;将各个3bits段中表示的1的个数累加起来放在一个6bits的段中,之所以使用0001112000111_2与每一个6bits的段相与,是因为使用3bits就可以表示6bits段中二进制1的个数而不会产生溢出,因为3bits最大可以表示7,6bits段中二进制1的个数最多是6。

第三步: 第二步做完之后,对于变量tmp,除了最左边是2bits为单独的一段,其它的从右至左每6位组成一段。以上面无符号32bits整数为例,x=a*64^5+b*64^4+c*64^3+d*64^2+e*64+f,因为a,b,c,d,e,f中保留着各个6bits段中的二进制1的个数,所以我们要求的是a+b+c+d+e+f,很明显, (a+b+c+d+e+f)=(a+b+c+d+e+f)mod 63=x mod 63。也就是说x与a+b+c+d+e+f关于模63同余。证明如下:

(x mod 63)=(a*64^5)%63+(b*64^4)%63+(c*64^3)%63+(d*64^2)%63+(e*64)%63+f%63
因为64的n次幂(n>=0)取模63的余数始终等于1,所以
(x mod 63)=a%63+b%63+c%63+d%63+e%63+f%63
因为(a+b+c+d+e+f)<=32,所以
(x mod 63)=(a+b+c+d+e+f)%63=a+b+c+d+e+f

同理,对于64位整数我们也可以这么处理。

上面解释了每一步的意义作用,但是该算法是如何一步一步优化推理而来的,这里不做赘述,具体可参考:MIT HAKMEM算法分析

方法七:查表法 (1)静态表-8bit 首先构造一个包含256个元素的表table,table[i]即i中1的个数,这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n,我们将其拆分成四个8bit,然后分别求出每个8bit中1的个数,再累加求和即可,这里用移位的方法,每次右移8位,并与0xff相与,取得最低位的8bit,累加后继续移位,如此往复,直到n为0。所以对于任意一个32位整数,需要查表4次。以十进制数2882400018为例,其对应的二进制数为10101011110011011110111100010010,对应的四次查表过程如下:红色表示当前8bit,绿色表示右移后高位补零。

第一次(n & 0xff) 10101011110011011110111100010010

第二次((n >> 8) & 0xff) 00000000101010111100110111101111

第三次((n >> 16) & 0xff)00000000000000001010101111001101

第四次((n >> 24) & 0xff)00000000000000000000000010101011

具体实现如下:

int bitCountSearchTable(unsigned int n){ 
    unsigned int table[256] = 
    { 
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 
    }; 

    return table[n &0xff]+table[(n>>8)&0xff]=+table[(n >>16)&0xff]+table[(n >>24)&0xff];
}

(2)静态表-4bit 原理和8-bit表相同,详见8-bit表的解释

int BitCount4(unsigned int n){
    unsigned int table[16]={
        0, 1, 1, 2, 
        1, 2, 2, 3, 
        1, 2, 2, 3, 
        2, 3, 3, 4
    } ;

    unsigned int count =0 ;
    while (n){
        count += table[n &0xf] ;
        n >>=4 ;
    }
    return count ;
}

4.小结

网上应该还有很多不同的而又令人叹为观止的实现方法,这里我就不探究了,有兴趣的读者可继续挖掘。


参考文献

[1]求二进制数中1的个数 [2]计算一个无符号整数的二进制中0和1的个数 [3]c语言:统计整数二进制表示中1的个数(汉明重量) [4]HAKMEM.维基百科 [5]求二进制数中1的个数 (下)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HUST 1588 辗转数对

1588 - 辗转数对 时间限制:1秒 内存限制:128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b),我们可以通过一步将这个数对...

3459
来自专栏企鹅号快讯

30分钟学会用Python编写简单程序

参与文末每日话题讨论,赠送异步新书 异步图书君 学习目标 知道有序的软件开发过程的步骤。 了解遵循输入、处理、输出(IPO)模式的程序,并能够以简单的方式修改它...

56710
来自专栏编程理解

动态规划(一):爬楼梯

时,处于原地,因为步长为 1 ~ 2 阶,不能有前进之后再后退的情况,所以只能有当前一种方式,所以

1262
来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

2956
来自专栏Spark学习技巧

Flink DataStream编程指南

Flink程序是执行分布式集合转换(例如,filtering, mapping, updating state, joining, grouping, defi...

1.7K7
来自专栏take time, save time

你所能用到的BMP格式介绍(二)

一、可能你忽视的基础         在正式开始之前,我不得不从最基本的地方开始,因为这些地方大多数人会忽视的一干二净,如果不在开始进行说明,那么在后面一定会有...

2947
来自专栏java一日一条

成为优秀Swift开发者的10条建议

在这里给大家分享一些帮助大家成为更优秀的Swift开发者的建议,让你的代码,写的更少,性能更优 。

1112
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十九)

但它的特点就是下次使用next(a)时,接着上次的断点继续运行,直到下一个yield

1083
来自专栏java达人

哈希表

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接...

1827
来自专栏小樱的经验随笔

51Nod 1182 完美字符串(字符串处理 贪心 Facebook Hacker Cup选拔)

1182 完美字符串 ?             题目来源:                         Facebook Hacker Cup选拔    ...

2917

扫码关注云+社区

领取腾讯云代金券