LeetCode算法解题集：Number of 1 Bits

题目：
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

思路-1：
32位数据，先计算出每位的值存储到一个数组里。然后循环这个数组，使用目标值去比较，若目标值小于当前位的值，继续循环；若当前目标值等于当前位值，计数并终止；若当前目标值大于当前位值，计数并重新计算当前目标值继续循环。算法复杂度：O(2 * 32)

代码-1：

class Solution {
public:

int hammingWeight(uint32_t n) {
    std::deque<uint32_t> nAllVaule;
    for (uint32_t i = 0; i <= 31; i++)
    {
        uint32_t cur_vaule = pow(2, i);
        nAllVaule.push_front(cur_vaule);
    }

    uint32_t letf_value = n;
    int count = 0;
    for (uint32_t i = 0; i < nAllVaule.size(); i++)
    {
        if (letf_value < nAllVaule[i])
        {
            continue;
        }

        if (letf_value == nAllVaule[i])
        {
            count++;
            break;
        }

        if (letf_value > nAllVaule[i])
        {
            count++;
            letf_value = letf_value - nAllVaule[i];
            continue;
        }
    }

    return count;
}

};
思路-2：
当前剩余值除2，若除不尽则计数，n取 n/2；若n为0，则终止。算法复杂度：O(16)
代码-2：

class Solution {
public:

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        if (n {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 2 == 1) {
            ++count;
        }
        n /= 2;
    }
    return count;
}

};
总结：
1、该算法较简单，但思路有很多种，比如爆破法（思路-1），即从最大位开始模糊匹配，较为复杂；还有一种就是取模法（思路-2）。
2、爆破法和取模法的算法复杂度相差还是很大的，官网上的显示是爆破法：15ms，取模法的时间是5ms；相差三倍
3、提交错误地方: typedef std::deque Deque; 这是一个类型的声明，而不是一个变量的声明，std::deque nQeque;这样才是一个变量。