求二进制中1的个数

题目

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

解法一

可能引起死循环

“基本的思路:先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1。这样每次移动一位,直到整个整数变成0为止。现在的问题变成怎么判断一个整数的最右边是不是1了。这很简单,只要把整数和1做位与运算看结果是不是0就知道了。1除了最右边的一位之外所有位都是0。如果一个整数与1做与运算的结果是1,表示该整数最右边一位是1,否则是0。”

1
2
3
4
5
6
7
8
9
10
11
//当n是负数时,死循环
int NumberOne(int n) {
int count = 0;
while(n) {
if (n & 1) {
count ++;
}
n = n >> 1;
}
return count;
}

解法二

“为了避免死循环,我们可以不右移输入的数字i。首先把i和1做与运算,判断i的最低位是不是为1。接着把1左移一位得到2,再和i做与运算,就能判断i的次低位是不是1……这样反复左移,每次都能判断i的其中一位是不是1。基于这种思路,我们可以把代码修改如下:”

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

解法三

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

我们把上面的分析总结起来就是:把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。”

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

扩展延伸

延伸一

“用一条语句判断一个整数是不是2的整数次方。”

思路:

“一个整数如果是2的整数次方,那么它的二进制表示中有且只有一位是1,而其他所有位都是0。”

延伸二

“输入两个整数m和n,计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010,13的二进制表示为1101,需要改变1010中的3位才能得到1101。”

思路:

“我们可以分为两步解决这个问题:第一步求这两个数的异或,第二步统计异或结果中1的位数。”

延伸三

C++中^运算表示的是二进制的异或运算

1
2
2^4=6
010^100=110

应用:使用该运算可以实现无中间变量两数字的交换

下面的例子实现a和b的置换

1
2
3
4
5
6
7
8
9
a=2;

b=4;

a=a^b;

b=a^b;

a=a^b;

参考:C++中的异或运算符^
剑指offer