「剑指 Offer」面试题 10:二进制中 1 的个数

Posted by Ink Bai on 2019-01-07     & views

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

这道题目考察二进制和位运算,一个数字转换成二进制以后有五种位运算,分别是与、或、异或、左移和右移。

其中与、或和异或运算规律如下表:

运算规则
与(&) 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1
或(|) 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
异或(^) 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

左移运算符 m << n 表示把 m 左移 n 位。左移 n 位的时候,最左边的 n 位将被丢弃,同时在最右边补上 n 个 0。比如:

00001010 << 2 = 00101000
10001010 << 3 = 01010000

右移运算符 m >> n 表示把 m 右移 n 位。如果数字原先是一个正数,则右移之后在最左边补 n 个 0;如果数字是负数,则右移之后在最左边补 n 个 1。下面就是对两个 8 位有符号数右移的例子:

00001010 >> 2 = 00000010
10001010 >> 3 = 11110001

上面就是关于二进制位运算的一些基础知识,我们来看一下怎么应用这些知识解决这个题目。

这里我们可以用到与的知识,1 & 1 的结果是 0,我们可以将这个数的个位与 1 相与,根据结果是否为 0 来确定这一位是不是 1,然后将这个数右移一位,再重复进行这样的判断。但是这样有一个问题,根据上面我们讲的右移的知识,如果一个数是负数,右移之后高位会补 1,结果就是多了很多位的 1,所以这种方法只能处理非负数,我们还需要考虑其他的办法。

上面的想法是右移这个数,可能会产生副作用(负数的情况下),左移是不会产生副作用的,那么我们还可以考虑左移上面用来与这个整数的每一位做与操作的 1。具体做法就是用 1 和这个数相与,根据结果是否为 0 确定最低位是不是 1,然后对 1 做左移运算,这样就变成了 10,可以判断出次低位是不是 1,依此类推不停地左移,总共需要左移整数位即 32 位,需要循环 32 次,代码如下:

public class Solution {
public int NumberOf1(int n) {
int count = 0;
int flag = 1;
while(flag != 0) {
if((flag & n) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
}

上面这种解法循环的次数等于整数二进制的位数,我们再来看一种更加巧妙的方法,整数中有几个 1 就只需要循环几次。

在分析这种算法之前,我们先来分析把一个数减去 1 的情况。如果一个整数不等于 0,那么该整数的二进制表示中至少有一位是 1。先假设这个数的最右边一位是 1,那么减去 1 时,最后一位变成 0 而其他所有位都保持不变。也就是最后一位相当于做了取反操作,由 1 变成了0。

接下来假设最后一位不是 1 而是 0 的情况。如果该整数的二进制表示中最右边一位位于第 m 位,那么减去 1 时,第 m 位由 1 变成 0,而第 m 位之后的所有 0 都变成 1,整数中的第 m 位之前的所有位都保持不变。举个例子:一个二进制数 1100,它的第二位是从最右边数起的一个 1。减去 1 后,第二位变成 0,它后面的两位 0 变成 1,而前面的 1 保持不变,因此得到的结果是 1011。

在前面两种情况中,我们发现把一个整数减去 1,都是把最右边的 1 变成 0。如果它的右边还有 0 的话,所有的 0 都变成 1,而它左边所有位都保持不变。接下来我们把一个整数和它减去 1 的结果做位与运算,相当于把它最右边的 1 变成 0。还是以前面的 1100 为例,它减去 1 的结果是 1011。我们再把 1100 和 1011 做位与运算,得到的结果是 1000。我们把 1100 最右边的 1 变成了 0,结果刚好就是 1000。

把上面的分析总结起来就是:把一个整数减去 1,再和原整数做与运算,会把该整数最右边一个 1 变成 0。那么一个整数的二进制表示中有多少个 1,就可以进行多少次这样的操作。基于这种思路,我们可以写出新的代码:

public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
count++;
n = (n - 1) & n;
}
return count;
}
}

把一个整数减去 1 之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个 1 变成 0。很多二进制的问题都可以用这个思路解决。