剑指offer面试题10-二进制中1的个数

问题描述

请实现一个函数,输入一个整数,输出该整数二进制表示中1的个数。
例如把9的二进制是1001,有2位是1。因此,如果输入9,该函数输出2。

解决算法

算法一

根据题目,我们可以想到先判断最低位是否为1,然后将次高位右移一位,然后在判断最低位是否为1,通过不断右移直到最高位右移到最低位时就可判断出每一位的情况,就得到了有多少位是1。那么问题就来了,如和判断最低位是否为1。

根据与运算的性质可知:1&1=1、1&0=0,那么最低位和1进行与操作,若结果为1则表示最低位为1,否则为0。

那么算法可总结为:将整数与1进行与操作,若结果为1,则最低位为1,1的个数加1,然后把整数向右移一位,重复上述操作,直至整数变为0。

与运算时相同位的两个数字都为1,则为1;若有一个不为1,则为0,即:1&1=1、1&0=0、0&1=1、0&0=1

示例

例如,求整数13的二进制中1的个数,过程如下:

整数13对应的二进制表示为:00000000 00000000 00000000 00001101。

java中int为4字节(4byte)共32位(32bit)。

第一步,整数和1进行与运算,结果为1,最低位为1,1的个数为1:
 00000000 00000000 00000000 00001101
& 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000001

第二步,整数右移一位,和1进行与运算,结果为0,最低位不为1:
 00000000 00000000 00000000 00000110
& 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000000

第三步,整数右移一位,和1进行与运算,结果为1,最低位为1,1的个数加1:
 00000000 00000000 00000000 00000011
& 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000001

第四步,整数右移一位,和1进行与运算,结果为1,最低位为1,1的个数加1:
 00000000 00000000 00000000 00000001
& 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000001

第五步,整数右移一位,和1进行与运算,结果为0,最低位不为1:
 00000000 00000000 00000000 00000000
& 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000000

整数右移后为0,结束,最后得到二进制中1的个数为3。

但是上边的算法有个小问题。由于计算机机中数值是以补码的形式存在,对于负数来说,对补码右移过程中最高位需补1而不是补0,当最高位移到最低位时,二进制的每一位上都为1,这就导致二进制表示中会有无限个1,右移过程陷入了死循环中。因此,对于负数,需要进行无操作符的右移,才能避免上述情况的发生。

正数的右移,负数的无符号右移,就是相应的补码移位所得,在高位补0即可
负数的右移,就是补码高位补1,然后按位取反加1即可,可参考另一篇博文《右移运算符总结》

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int NumberOf1(int n) {
int count = 0;

while(n!=0) {
//判断当前位置是否为1
if((n&1)==1) {
count++;
}

//对n进行逻辑右移操作(无符号右移)
n=n>>>1;
}

return count;
}

算法二

算法二的解法和算法一基本一样,不同的是,每次判断完后整数保持不变,对1进行左移一位。

具体算法为:

  1. 首先把整数和1进行与运算,判断最低位是否为1,然后将1左移一位得到2。
  2. 再把整数和2进行与运算,判断次低位是否为1,然后将2左移一位得到4。
  3. 再把整数和4进行与运算,判断第3位是否为1,然后再将4左移一位得到8。
  4. ……

重复上述操作,直到判断到最高位是否为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int Numberof12(int n) {
int count = 0;
int flag = 1;

while(flag != 0) {
//判断当前位置是否为1
if(1 == (n & flag)) {
count++;
}
//对1进行左移操作
flag = flag<<1;
}

return count;
}

算法一和算法而都是对二进制表示中的每一位进行判断,因此循环次数为32次(java中int类型长度为32位),下面介绍一种二进制表示中有几个1就进行几次循环的算法。

算法三

我们考虑下一个非0的整数减去1的情况。假设在整数的二进制表示中第一个1位于m位。当整数减去1后时,由于m的右侧都为0,0减1不够减,需要向高位借位,直到m位才借到1,此时,由于m位被借了1变为了0,m位右侧都变为了1,m位左侧位保持不变。然后我们在拿整数和减去1后得到的整数进行与操作,由于两个数的m位左侧相同,与操作后m位左侧保持不变;m位及m位右侧都变为了0(m位是 1&0=0,m位右侧是0&1=0)。举个栗子:1010减去1得到1001,1010&1001=1000。

把上边的思路整理下可知:把一个整数减去1后,把得到的结果和整数做与运算,会把该整数最右侧的1变为0。那么可以做多少次这个操作,二进制表示中就有多少个1。

示例

以整数182(对应二进制为:1011 0110,前24位都为0,省略不写)为例:

  1. 将 1011 0110 减去1得到 1011 0101,1011 0110 & 1011 0101 = 1011 0100。
  2. 将上一步得到的整数 1011 0100 减去1得到 1011 0011,1011 0100 & 1011 0011 = 1011 0000。
  3. 将上一步得到的整数 1011 0000 减去1得到 1010 1111,1011 0000 & 1010 1111 = 1010 0000。
  4. 将上一步得到的整数 1010 0000 减去1得到 1001 1111,1010 0000 & 1001 1111 = 1000 0000。
  5. 将上一步得到的整数 1000 0000 减去1得到 0111 1111,1000 0000 & 0111 1111 = 0000 0000。

最后整数变为0,结束查找,此时共进行了5次操作,故二进制形式中共有5个1。

代码

1
2
3
4
5
6
7
8
9
10
11
public int Numberof13(int n) {
//n 和 n-1 进行与操作,能进行多少次与操作,就有多少个1
int count = 0;

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

return count;
}

附:

完整代码可参考github,地址为:
https://github.com/zhangyihao/Algorithms/blob/master/com.zhangyihao.algorithms/src/com/zhangyihao/algorithms/offer/Question10.java