LeetCode/solutions/191. Number of 1 Bits.md

# [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/description/)
# 思路
## 思路一
不断循环，每次循环得到最低位的值，最后可得到所有位1的个数。怎样得到最低位的值，两种方法:
* 1、若num为奇数，则num的最低位肯定为1; 
* 2、用一个只有低位是1的mask与num进行与操作即可得到最低位（或者保持输入不变而不断左移mask）；

**需要注意的是如果输入不是无符号型而是有符号型，那么如果输入的是负数，即符号位为1，那么右移高位会填1，最终会变成0xFFFFFFFF而陷入死循环。解决办法是保持输入不变而不断左移无符号的mask来判断输入的每一位是否为1.**


## 思路二*
依然是循环，但是每次循环不是得到最低位的值，而是每次循环去掉最低位的1，用一个count计数即可得到答案。**我们把原数减1，将结果和原数做与运算即可去掉最低位的1，即`n &= (n - 1)`。**

**此方法同样适用于输入为有符号型的情况。**


# C++
## 思路一
``` C++
// 方法1
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n != 0){
            res += (n % 2);
            n >>= 1; // 除法效率比移位低很多
        }
        return res;
    }
};

// 方法2
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        uint32_t mask = 1;
        for(int i = 0; i < 32; i++){
            res += (n & mask);
            n = n >> 1;
        }
        return res;
    }
};
```
## 思路二*
``` C++
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            n &= (n - 1); // 去掉最后的1
            count++;
        }
        return count;
    }
};
```