题目：
Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Note:
- Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer
-3.
Follow up:
If this function is called many times, how would you optimize it?
这道题乍一看有点傻，不就是计算一个二进制数里面的1的个数嘛，直接傻傻地取出这个数中的每一位，和1与一下看看是不是1就行了。嗯这确实是一种方法，并且是我唯一想到的方法了，复杂度是O(k)，k是数字的长度。代码如下，时间4ms，90.17%，空间8.3M，5.01%：
/*
* @lc app=leetcode id=191 lang=cpp
*
* [191] Number of 1 Bits
*/
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
if (n & 1) {
count++;
}
n >>= 1;
}
return count;
}
};
但是这道题主要的知识点在于另外一种位运算的性质：n&(n-1)这个操作会把数字n中的最后一个1变成0！一看到这个性质就觉得很熟悉，总觉得在哪道题见过，却想不起来了。
为什么n&(n-1)有这样的神秘性质呢？因为如果n中有1，分两种情况：如果1在最右边，那好，直接把1变成了0；而如果1不在最右边，且我们取最靠右的1，那么在-1的过程中会把它后面所有0变成1，把这个1变成0。既然这样，那n和(n-1)其实在最右边的1及它右边的所有数字上都没有相同的，也就是把这些全部变成了0，而和原先的数字相比，就只有最右边的1被变成了0。应用在这道题上，就是疯狂进行这样的操作，直到所有的1都被变成0，计数截止，得到答案。
代码如下，时间复杂度为O(k)，k为数字中1的个数，4ms，90.17%，空间8.3M，9.14%：
/*
* @lc app=leetcode id=191 lang=cpp
*
* [191] Number of 1 Bits
*/
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
};