来源：剑指 Offer 15. 二进制中1的个数

问题描述：

---

解题分析：

1.自己的方法报错了

我自己想的就是先将其转化为字符串，然后数一数1的个数，结果不对，但是我调试的时候，发现结果是对的呀！！！
无法理解，太玄幻了，先放在这里吧！

class Solution {
public:
    int hammingWeight(uint32_t n) {
        string new_n=to_string(n);
        int count=0;
        for(auto a:new_n)
        {
            if(a=='1')
            {
                count++;
            }
        }
        return count;
    }
};

2.移位运算

这里首先介绍一下移位运算：

• 4<<2: <<表示的是左移，高位移出，低位补0，相当于乘以 2 n 2^n 2n,n表示移动n次
• 4>>2:>>表示的是右移，低位移出，高位补0，相当于除以 2 n 2^n 2n,n表示移动n次

这里还得再多说几句：

• > > > >>> >>> :表示无符号右移，无论正负数，前面补0
• > > >> >>:右移：正数前面补0，负数补1
• < < << <<:左移：无论正负数，后面补0

题目中输入的是n,是一个32位的无符号二进制数，n 和 2 i 2^i 2i进行与运算，若n的第i位是1，则结果为1；若n的第i位是0，则结果为0.
这样就可以判断n中有几个1了。
但是结果我很疑惑，时间复杂度是 O ( n ) O(n) O(n),空间复杂度是 O ( 1 ) O(1) O(1).
最后的结果并不好，内存消耗只击退了5.98%的用户。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        //移位运算
        int count=0;
        for(int i=0;i<32;i++)
        {
            if(n& (1<<i))
            {
                count++;
            }
        }
        return count;
    }
};

3.还有一种移位运算

就是把n的最后一位和1 做与运算，若为结果为1，则就是最后一位为1；若结果为0，最后一位为0.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        //移位运算
        int count=0;
        while(n)
        {
            if(n&1==1)
            {
                count++;
            }
            n>>=1; //n=n>>1
        }
        return count;
    }
};

4. n&(n-1)运算

来源:LeetCode K神解析

• n − 1 n-1 n−1解析：n的最后一位1变为0，1之后的变为1
• n&(n-1) 解析: 将最后一个1变为0
• 这样有多少个1，就可以进行多少次与运算

时间复杂度： O ( M ) , M 为 n 中 1 O(M),M为n中1 O(M),M为n中1的个数
空间复杂度： O ( 1 ) O(1) O(1) ,只使用了一个变量count, 是常数大小

class Solution {
public:
    int hammingWeight(uint32_t n) {
        //移位运算
        int count=0;
        while(n!=0)
        {
            n=n&(n-1);
            count++;
        }
        return count;
    }
};