剑指offer之二进制中1的个数
1 问题
实现一个函数，输入一个函数，输出该二进制数据中1的个数。例如9表示二进制数据1001，有2位是1，因此输入9，该函数会输出2。
2 分析
我们先了解下计算机里面位运算，有5种
1）& 这个是与操作，规律如下
1 & 1 = 1 1 & 0 = 0 0 & 1= 0 0 & 0 = 0
2）| 这个是或运算，规律如下
1 | 1 = 1 1 | 0 = 1 0 | 1= 1 0 | 0 = 0
3）^ 异或运算，规律如下
1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 1 = 1 0 ^ 0 = 0
4） 左移 m<<n 表示把m左移n位，在左移n位的时候，最左边的n位丢弃，同时右边补上n个0 比如
-
00001010 << 2 = 00101000
-
-
10001010 << 3 = 01010000
5） 右移 左移 m >> n 表示把m右移n位，在右移n位的时候，最右边补上n个0 ，最左边分2种情况，如果数字是一个无符号整形
则用0填补最左边的n位，如果是一个有符号的数据，则最左边用数字的符号填补n个数据。如果是正数，左边补n个0，是负数左边补n个1.
-
00001010 >> 2 = 00000010
-
-
10001010 >> 3 = 11110001
这里我们可以把原数据和1进行&操作，如果二进制数据尾巴进行&操作，如果包含1的话&1操作就是1，返之结果为0，然后我们把数据进行右移一位就行。
如果一个正数要除以2，我们效率最高的是把这个数据进行右移一位。
3 代码实现
C++版本
-
#include <stdio.h>
-
-
/*
-
*二进制数据里面包含数字1的个数
-
*/
-
int containOneNumber(int value)
-
{
-
int count = 0;
-
while (value != 0)
-
{
-
//这里是(value & 1)不是（value & 0）
-
if (value & 1)
-
++count;
-
//这里是value = value >> 1,而不是value >> 1; 我们要用变量接收它
-
//不然不管就只执行了一次也就是value除以了2，所以导致死循环。
-
value = value >> 1;
-
}
-
return count;
-
-
}
-
-
int main(void)
-
{
-
int result = containOneNumber(9);
-
printf("result is %d\n", result);
-
return 0;
-
}
java版本
-
public int containOneNumber(int value)
-
{
-
int count = 0;
-
while (value != 0)
-
{
-
if ((value & 1) != 0)
-
{
-
count++;
-
}
-
value = value >>> 1; //>>>就是java中的无符号右移
-
}
-
return count;
-
}
我们知道java用 >>> 是无符号右移，右移的时候，所以最高位左边都是0，如果这个数是负数的时候，右移的话最高位会补1，
C++版本就会变成死循环。
4 优化
方法1:
n与1做与运算，判断n的最低位是不是为1,接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1….这样反复左移
-
int containOneNumber1(int n)
-
{
-
int flag = 1;
-
int count = 0;
-
while (flag != 0)
-
{
-
if ((flag & n) != 0)
-
{
-
count++;
-
}
-
flag = flag << 1;
-
}
-
return count;
-
}
方法2：
把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0，那么一个整数的二进制表示中有
多少个1，就可以进行多少次这样的操作
-
int containOneNumber1(int n)
-
{
-
int flag = 1;
-
int count = 0;
-
while (n != 0)
-
{
-
++count;
-
n = n & (n - 1);
-
}
-
return count;
-
}
5 总结
1） 把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0，那么一个整数的二进制表示中有多少个1
2）n与1做与运算，判断n的最低位是不是为1,接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1….这样反复左移
3） 如果是正整数的情况下，我们可以把正整数右移动和1进行&操作，然后再去统计。
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/102675036
- 点赞
- 收藏
- 关注作者
评论（0）