剑指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