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

简介1.问题来源 之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙的解法。查找网上资料,才知道这个问题的正式的名字叫Hamming weight(汉明重量)。 2.问题描述 对于一个无符号整型数,求其二进制表示中1的个数。比如12的以32位无符号整型来表示,其二进制为:00000000 00000000 00000000 00001100,那么12的二进制

1.问题来源

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

2.问题描述

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

3.具体解法

方法一: 移位法

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

  1. #include
  2. intcount1(uint32_tx){
  3. intcount=0;
  4. while(x){
  5. if(x&0x1)
  6. ++count;
  7. x=(x>>1);
  8. }
  9. returncount;
  10. }

方法二:去1法

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

  1. intcount1(uint32_tx){
  2. intcount=0;
  3. while(x){
  4. x=x&(x-1);
  5. count++;
  6. }
  7. returncount;
  8. }

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

  1. intcount1(intx){
  2. intn=0;
  3. while((x+1)){
  4. n++;
  5. x|=(x+1);
  6. }
  7. return32-n;
  8. }

方法三:分治法

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

  1. intHamming_weight(uint32_tn){
  2. n=(n&0x55555555)+((n>>1)&0x55555555);
  3. n=(n&0x33333333)+((n>>2)&0x33333333);
  4. n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
  5. n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff);
  6. n=(n&0x0000ffff)+((n>>16)&0x0000ffff);
  7. returnn;
  8. }

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

  1. 0x5555……这个换成二进制之后就是0101010101010101……
  2. 0x3333……这个换成二进制之后就是0011001100110011……
  3. 0x0f0f………这个换成二进制之后就是0000111100001111……

看出来点什么了吗? 如果把这些二进制序列看作一个循环的周期序列的话,那么第一个序列的周期是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的个数。可见这里的累加方法明显与上面不同,代码也是略显膨胀。

  1. structBitStruct{
  2. uint8_ta:1;uint8_tb:1;uint8_tc:1;uint8_td:1;uint8_te:1;uint8_tf:1;uint8_tg:1;uint8_th:1;
  3. uint8_ta1:1;uint8_tb1:1;uint8_tc1:1;uint8_td1:1;uint8_te1:1;uint8_tf1:1;uint8_tg1:1;uint8_th1:1;
  4. uint8_ta2:1;uint8_tb2:1;uint8_tc2:1;uint8_td2:1;uint8_te2:1;uint8_tf2:1;uint8_tg2:1;uint8_th2:1;