[剑指Offer]12.二进制中1的个数

题目

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

思路

把一个整数减去1，再和原整数做与运算，会把整数最右边一个1变成0.那么一个整数的二进制表示中有多少个1，就可以进行多次这样的操作。

代码

/*--------------------------------------- * 日期：2015-07-20 * 作者：SJF0115 * 题目: 12.二进制中1的个数 * 结果：AC * 网址：http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1 * 来源：剑指Offer * 博客： -----------------------------------------*/ #include <iostream> #include <vector> #include <string> #include <stack> #include <algorithm> using namespace std;class Solution { public:int NumberOf1(int n){int count = 0;while(n){n &= (n-1);++count;}//whilereturn count;} };int main(){Solution s;int n;while(cin>>n){int result = s.NumberOf1(n);// 输出cout<<result<<endl;}//whilereturn 0; }

思路二

我们可能很快就有一个思路：先判断整数二进制表示中最右边一位是不是1.接着把输入的整数右移一位，此时原来处于从右边数起第二位被移到最右边了，再判断是不是1。这样每次移动一位，直到整个整数变成0为止。基于这个思路我们写完下面的程序。但是当我们输入一个负数时，这个方法就会出现问题。比如0x80000000，把负数0x80000000右移一位时并不是简单的把最高位的1移到第二位变成0x40000000，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后最高位仍然是1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。

代码二

class Solution { public:int NumberOf1(int n){int count = 0;while(n){if(n & 1){++count;}//ifn = n >> 1;}//whilereturn count;} };

思路三

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

代码三

/*--------------------------------------- * 日期：2015-07-20 * 作者：SJF0115 * 题目: 12.二进制中1的个数 * 结果：AC * 网址：http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1 * 来源：剑指Offer * 博客： -----------------------------------------*/ #include <iostream> #include <vector> #include <string> #include <stack> #include <algorithm> using namespace std;class Solution { public:int NumberOf1(int n){int count = 0;int base = 1;while(base){if(n & base){++count;}//ifbase = base << 1;}//whilereturn count;} };int main(){Solution s;int n;while(cin>>n){int result = s.NumberOf1(n);// 输出cout<<result<<endl;}//whilereturn 0; }

总结

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

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