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

题目链接：二进制中1的个数

 

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

 

题解：

1、很容易想到每次做&运算，然后判断结果是否为0来判断是否有1。

2、去讨论区看了下第一个方法效率太低。

第二个方法就是让每次让n & n-1。我刚开始没懂举了个例子。

n = 1100

1100 - 1 = 1011　　1100&1011 = 1000

1000 - 1 = 0111　　1000 & 0111 = 0000 

从上可得，每次-1操作是使'1'位被借走，再和原来的&会使被借位的1变成0。

也就是我们每次做这个操作的时候都会使数字里的1变成0，那么只要全为0，这个1的个数就找出来了。

 

代码：

class Solution {
public:
     int  NumberOf1(int n) {
        int cnt = 0;
        int flag = 1;
        while(flag >= 1 || flag <= -1){
            if(( n & flag) != 0){
                cnt++;
            }
            flag <<= 1;
        }
        return cnt;
     }
};



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