一、题目描述

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

二、算法1（暴力）

解题思路

1. 依次检查二进制每一位，若当前位与(&)1为1，则计数器加1
2. 检查二进制的第k位 : n & (1 << k)

代码实现（C++11）

class Solution {
public:
     int  NumberOf1(int n) {
         int cnt = 0;
         for(int i = 0; i < 32; i++) {
             if(n & (1 << i)){    // 检查二进制的第i位
                 cnt++;
             }
         }
         return cnt;
     }
};

时间复杂度：, k为n的位数, 这里为32
空间复杂度：, 常数空间

三、算法2（lowbit运算）

解题思路

1. lowbit运算是一种经典的算法，它可以求得整数二进制表示下最后一位1，即若，则
2. 通过lowbit运算，我们可以快速的取出整数二进制表示下的最后一位1，因此每取一次我们就计数一次，然后再去掉最后一位1，知道n = 0
3. 那么如何实现lowbit呢，我们可以先对n取反，然后再加1，这样就使得取反后的结果最后一位1与n对应，最后相与(&)就取出了最后一位1

代码实现（C++11）

class Solution {
public:
    // lowbit运算
    int lowbit(int n) {
        return n & (~n + 1);
    }

     int  NumberOf1(int n) {
         int cnt = 0;
         // 从低位到高位依次取出1
         for(int i = n; i; i -= lowbit(i)) {
             cnt++;
         }
         return cnt;
     }
};

时间复杂度：, m为n二进制表示中1的个数
空间复杂度：, 常数空间