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<int> Deque; 这是一个类型的声明，而不是一个变量的声明，std::deque<int> nQeque;这样才是一个变量。

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-08-10