（剑指Offer）面试题10：二进制中1的个数

题目：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：

很明显，这道题考察的是位运算。

1、依次将整数右移，判断整数最后一位是否为1(&1)；

问题：如果该整数为负数，则会陷入无限循环，为什么？因为负数右移的时候，左边补1，整数右移过程中不可能为0，因此会陷入无限循环。

补码的移位：

左移，无论正数负数都在右边补0；

右移，正数在左边补0，负数在左边补1；

int NumberOf1(int n){int count=0;while(n){if(n&1)count++;n=n>>1;}return count; }

2、依次将1左移i位，然后跟该整数做与&操作，如果结果不为0，则第i位为1；

问题：整数有多少位，就得循环多少次。

3、利用小技巧

x&(x-1)可以将整数最右边的1变成0，通过这个小技巧，我们只要循环判断n=n&(n-1)是否为0，即可统计1的个数。

整数中有多少个1，则循环多少次。

4、位运算相关题目

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

if(n&(n-1)==0) return true;

• 输入两个整数m,n,计算需要改变m的二进制表示中的多少位才能得到n？

int x=m^n; return NumberOf1(x);　　

代码：

#include <iostream>using namespace std;int NumberOf1_shift(int n){int count=0;unsigned int flag=1;while(flag){if(n&flag)count++;flag=flag<<1;}return count; }int NumberOf1_fast(int n){int count=0;while(n){count++;n=n&(n-1);}return count; }int main() {cout <<NumberOf1_shift(-8)<< endl;cout <<NumberOf1_fast(-8)<< endl;return 0; }

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1

AC代码：

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

　　

转载于:https://www.cnblogs.com/AndyJee/p/4630568.html

总结

以上是生活随笔为你收集整理的（剑指Offer）面试题10：二进制中1的个数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。