【剑指offer】11-二进制中1的个数

本文系《剑指offer》的刷题记录，通过牛客网在线平台测试通过。
在线测试平台：牛客网
编程资料获取：CodeLab

1-Description

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

2-Solution

1-右移整数
注意这里强调了负数的存在，如果我们单纯的将整数n逐位进行右移将进入死循环，例如将负数0x80000000右移1位的时候，并不是简单地把最高位1移到次高位变成0x40000000，而是右移之后，最高位要置1，因为要保证数字为负数，可以预见最终这个数字将变成0xFFFFFFF而陷入死循环

所以下面的代码对负数而言是不可行的

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

2-左移flag
既然上面的方法不可行，我们可以考虑反过来思考，也就是说不移动整数i而是对数字1进行左移，这样每次均可以判断i的其中1位是不是1，所以可以将代码修改如下：

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         unsigned int flag = 1;
         while(flag){//对任何整数都需要遍历32次，直到flag置0
             if(n & flag){//该位置为1则count++
                 count ++;
             }
             flag = flag << 1;
         }
         return count;
     }
};

3-最优解
我们发现，如果把一个整数减去1，都是把最右边的1变为0，如果其右边还有0的话，所有的0变为1，1而其左边的所有位保持不变，接下来我们把一个整数与其减去1的结果做位于运算，相当于将其右边的1变为0。例如1100减去1的结果为1011，那么1100&1011 = 1000，也就是说我们通过这一操作可以对最右边的1进行计数，所以一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作，解决代码如下：

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

如果了解C++的标准库的话，还可以使用bitset类的方法进行解决，代码如下：

class Solution {
public:
     int  NumberOf1(int n) {
         bitset<32>  bitn(n);
         return bitn.count();
     }
};