文档章节

算法-求二进制数中1的个数

Airship
 Airship
发布于 2016/08/23 20:23
字数 3065
阅读 6
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

算法-求二进制数中1的个数 问题描述

任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如n = 5(0101)时,返回2,n = 15(1111)时,返回4

这也是一道比较经典的题目了,相信不少人面试的时候可能遇到过这道题吧,下面介绍了几种方法来实现这道题,相信很多人可能见过下面的算法,但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法,或者本文没有提到的算法,请不要吝惜您的代码,分享的时候,也是学习和交流的时候。

普通法

我总是习惯叫普通法,因为我实在找不到一个合适的名字来描述它,其实就是最简单的方法,有点程序基础的人都能想得到,那就是移位+计数,很简单,不多说了,直接上代码,这种方法的运算次数与输入n最高位1的位置有关,最多循环32次。

复制代码 int BitCount(unsigned int n) { unsigned int c =0 ; // 计数器 while (n >0) { if((n &1) ==1) // 当前位是1 ++c ; // 计数器加1 n >>=1 ; // 移位 } return c ; } 复制代码 一个更精简的版本如下

复制代码 int BitCount1(unsigned int n) { unsigned int c =0 ; // 计数器 for (c =0; n; n >>=1) // 循环移位 c += n &1 ; // 如果当前位是1,则计数器加1 return c ; } 复制代码 快速法

这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1,同时累加计数器,直至n为0,代码如下

复制代码 int BitCount2(unsigned int n) { unsigned int c =0 ; for (c =0; n; ++c) { n &= (n -1) ; // 清除最低位的1 } return c ; } 复制代码 为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)。

查表法

动态建表

由于表示在程序运行时动态创建的,所以速度上肯定会慢一些,把这个版本放在这里,有两个原因

  1. 介绍填表的方法,因为这个方法的确很巧妙。

  2. 类型转换,这里不能使用传统的强制转换,而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。

复制代码 int BitCount3(unsigned int n) { // 建表 unsigned char BitsSetTable256[256] = {0} ;

// 初始化表 
for (int i =0; i <256; i++) 
{ 
    BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2]; 
} 

unsigned int c =0 ; 

// 查表
unsigned char* p = (unsigned char*) &n ; 

c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]]; 

return c ; 

} 复制代码 先说一下填表的原理,根据奇偶性来分析,对于任意一个正整数n

1.如果它是偶数,那么n的二进制中1的个数与n/2中1的个数是相同的,比如4和2的二进制中都有一个1,6和3的二进制中都有两个1。为啥?因为n是由n/2左移一位而来,而移位并不会增加1的个数。

2.如果n是奇数,那么n的二进制中1的个数是n/2中1的个数+1,比如7的二进制中有三个1,7/2 = 3的二进制中有两个1。为啥?因为当n是奇数时,n相当于n/2左移一位再加1。

再说一下查表的原理

对于任意一个32位无符号整数,将其分割为4部分,每部分8bit,对于这四个部分分别求出1的个数,再累加起来即可。而8bit对应2^8 = 256种01组合方式,这也是为什么表的大小为256的原因。

注意类型转换的时候,先取到n的地址,然后转换为unsigned char*,这样一个unsigned int(4 bytes)对应四个unsigned char(1 bytes),分别取出来计算即可。举个例子吧,以87654321(十六进制)为例,先写成二进制形式-8bit一组,共四组,以不同颜色区分,这四组中1的个数分别为4,4,3,2,所以一共是13个1,如下面所示。

10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13

静态表-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 ;

} 复制代码 静态表-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 BitCount7(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] ;

} 复制代码

当然也可以搞一个16bit的表,或者更极端一点32bit的表,速度将会更快。

平行算法

网上都这么叫,我也这么叫吧,不过话说回来,的确有平行的意味在里面,先看代码,稍后解释

复制代码 int BitCount4(unsigned 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 ; 

} 复制代码 速度不一定最快,但是想法绝对巧妙。 说一下其中奥妙,其实很简单,先将n写成二进制形式,然后相邻位相加,重复这个过程,直到只剩下一位。

以217(11011001)为例,有图有真相,下面的图足以说明一切了。217的二进制表示中有5个1

完美法

int BitCount5(unsigned int n) { unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111); return ((tmp + (tmp >>3)) &030707070707) %63; } 最喜欢这个,代码太简洁啦,只是有个取模运算,可能速度上慢一些。区区两行代码,就能计算出1的个数,到底有何奥妙呢?为了解释的清楚一点,我尽量多说几句。

第一行代码的作用

先说明一点,以0开头的是8进制数,以0x开头的是十六进制数,上面代码中使用了三个8进制数。

将n的二进制表示写出来,然后每3bit分成一组,求出每一组中1的个数,再表示成二进制的形式。比如n = 50,其二进制表示为110010,分组后是110和010,这两组中1的个数本别是2和3。2对应010,3对应011,所以第一行代码结束后,tmp = 010011,具体是怎么实现的呢?由于每组3bit,所以这3bit对应的十进制数都能表示为2^2 * a + 2^1 * b + c的形式,也就是4a + 2b + c的形式,这里a,b,c的值为0或1,如果为0表示对应的二进制位上是0,如果为1表示对应的二进制位上是1,所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子,十进制数6(0110)= 4 * 1 + 2 * 1 + 0,这里a = 1, b = 1, c = 0, a + b + c = 2,所以6的二进制表示中有两个1。现在的问题是,如何得到a + b + c呢?注意位运算中,右移一位相当于除2,就利用这个性质!

4a + 2b + c 右移一位等于2a + b

4a + 2b + c 右移量位等于a

然后做减法

4a + 2b + c –(2a + b) – a = a + b + c,这就是第一行代码所作的事,明白了吧。

第二行代码的作用

在第一行的基础上,将tmp中相邻的两组中1的个数累加,由于累加到过程中有些组被重复加了一次,所以要舍弃这些多加的部分,这就是&030707070707的作用,又由于最终结果可能大于63,所以要取模。

需要注意的是,经过第一行代码后,从右侧起,每相邻的3bit只有四种可能,即000, 001, 010, 011,为啥呢?因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题,因为3 + 3 = 6,不足8,不会产生进位。

tmp + (tmp >> 3)-这句就是是相邻组相加,注意会产生重复相加的部分,比如tmp = 659 = 001 010 010 011时,tmp >> 3 = 000 001 010 010,相加得

001 010 010 011

000 001 010 010


001 011 100 101

011 + 101 = 3 + 5 = 8。(感谢网友Di哈指正。)注意,659只是个中间变量,这个结果不代表659这个数的二进制形式中有8个1。

注意我们想要的只是第二组和最后一组(绿色部分),而第一组和第三组(红色部分)属于重复相加的部分,要消除掉,这就是&030707070707所完成的任务(每隔三位删除三位),最后为什么还要%63呢?因为上面相当于每次计算相连的6bit中1的个数,最多是111111 = 77(八进制)= 63(十进制),所以最后要对63取模。

位标志法

感谢网友 gussing提供

复制代码 struct _byte { unsigned a:1; unsigned b:1; unsigned c:1; unsigned d:1; unsigned e:1; unsigned f:1; unsigned g:1; unsigned h:1; };

long get_bit_count( unsigned char b ) { struct _byte by = (struct _byte)&b; return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h); } 复制代码 指令法

感谢网友 Milo Yip提供

使用微软提供的指令,首先要确保你的CPU支持SSE4指令,用Everest和CPU-Z可以查看是否支持。

unsigned int n =127 ; unsigned int bitCount = _mm_popcnt_u32(n) ; References

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

作者:zdd 出处:http://www.cnblogs.com/graphics/ 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.

本文转载自:http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

Airship
粉丝 50
博文 1099
码字总数 22567
作品 0
南京
高级程序员
私信 提问
面试算法知识梳理(14) - 数字算法

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 面试算法知识梳理(2) - 字符串算法第一部分 面试算法知识梳理(3) - 字符串算法第二部分 面试算法知识梳理(4) - 数组第一部分 面试...

泽毛
2017/12/28
0
0
求二进制中1的个数(编程之美2.1)

行文脉络 解法一——除法 解法二——移位 解法三——高效移位 解法四——查表 扩展问题——异或后转化为该问题 对于一个字节(8bit)的变量,求其二进制“1”的个数。例如6(二进制0000 0110...

技术mix呢
2017/11/09
0
0
JAVA中常用的二进制位操作

一,计算某个正数的二进制表示法中 1 的个数 1 //求解正数的二进制表示法中的 1 的位数2 private static int countBit(int num){3 int count = 0;4 for(; num > 0; count++)5 {6 num &= (nu...

一贱书生
2016/11/19
10
0
输入一个十进制整数,统计其中二进制1的个数

题目:统计给定的十进制数的二进制中1的个数 分析: 1.很多人看到这个需求的时候,第一反应是先把给定的十进制数转换成二进制数,再把二进制数转换为字符数组,再遍历这个字符数组计算1出现的...

kuangsonghan
2017/12/13
0
0
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis面试题详解:哨兵+复制+事务+集群+持久化等

Redis主要有哪些功能? 1.哨兵(Sentinel)和复制(Replication) Redis服务器毫无征兆的罢工是个麻烦事,如何保证备份的机器是原始服务器的完整备份呢?这时候就需要哨兵和复制。 Sentinel...

Java阿七
2分钟前
0
0
响应国家号召 1+X 证书 Web 前端开发考试模拟题

官方QQ群:736413913 1+x证书Web前端开发初级理论考试样题2019 http://blog.zh66.club/index.php/archives/149/ 1+x证书Web前端开发初级实操考试样题2019 http://blog.zh66.club/index.php/...

张帅个人博客
6分钟前
2
0
如何检查一个字符串在Objective-C中是否包含另一个字符串?

如何检查字符串( NSString )是否包含另一个较小的字符串? 我希望有这样的东西: NSString *string = @"hello bla bla";NSLog(@"%d",[string containsSubstring:@"hello"]); 但是我能找到......

javail
23分钟前
2
0
.NET Core开发的iNeuOS工业互联网平台,发布 iNeuDA 数据分析展示组件,快捷开发图形报表和数据大屏

目 录 1. 概述... 2 2. 演示信息... 2 3. 简单介绍... 3 4. 产品特点... 4 5. 价值体现... 5 1. 概述 经过一段时间的努力,iNeuDA产品组件已经开发和测试完成,现在正式上线。现在iNeuOS工业...

wxzz
26分钟前
2
0
在每个GROUP BY组中选择第一行?

顾名思义,我想选择以GROUP BY分组的每组行的第一行。 具体来说,如果我有一个如下的purchases表: SELECT * FROM purchases; 我的输出: id | customer | total---+----------+------ 1...

技术盛宴
39分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部