剑指Offer:二进制中1的个数

题目描述

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

分析

我们可以用二进制的思想来解决这道题,首先判断整数二进制表示中最右边一位是不是1;接着把输入的整数右移一位,再判断是不是1,这样每次移动一位,直到整个整数变成0为止。

但是以上方法存在一个致命的缺陷,如果输入的正数我们这样做非常不错,但是如果输入的是负数,由于移位需要保证移位前后的符号一致,因此移位后的最高为会设为1.如果一直右移就会陷入死循环。GG

为了避免死循环,我们可以不右移输入的整数。首先把n和1相与,判断n的最低位是不是1.接着把1左移一位,再与n做与运算,就能判断次低位是不是1…这样反复左移每次都能判断n的其中一位是不是1 …

1
2
3
4
5
6
7
8
9
10
int NumberOf1(int n){
int count = 0;
int flag = 1;
while(flag){
if (n & flag)
count ++;
flag = flag << 1;
}
return count;
}

接下来我们再来看一种二进制的解法

先上代码

1
2
3
4
5
6
7
8
public int NumberOf1(int n) {
int count = 0;
while (n!=0) {
count ++;
n = n&(n-1);
}
return count;
}

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

接下来假设最后一位不是1而是0。如果该整数的二进制表示中最右边的1位于第m位,那么减去1时第m位由1变为了0,而第m位之后的所有0都变为了1,第m位之前的所有位都不变。

12-1 ——- 1100 –> 1011

由此我们发现,把一个整数减去1,就是把最右边的1变成0,如果它右边还有0就把0变成1,而它左边的所有位保持不变。接下来我们把一个整数和它减去1的结果做位运算,相当于把他最右边的1变为0

1100 & 1011 —> 1000