[LeetCode]191.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.

思路

每次左移一位，进行&运算。

代码

/*------------------------------------------------------
*   日期：2014-04-12
*   作者：SJF0115
*   题目: 191.Number of 1 Bits
*   网址：https://leetcode.com/problems/number-of-1-bits/
*   结果：AC
*   来源：LeetCode
*   博客：
--------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

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

int main(){
    Solution solution;
    uint32_t num = 1;
    cout<<""<<solution.hammingWeight(num)<<endl;
    return 0;
}

思路二

每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。

代码二

/*------------------------------------------------------
*   日期：2014-04-12
*   作者：SJF0115
*   题目: 191.Number of 1 Bits
*   网址：https://leetcode.com/problems/number-of-1-bits/
*   结果：AC
*   来源：LeetCode
*   博客：
--------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

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

int main(){
    Solution solution;
    uint32_t num = 11;
    cout<<""<<solution.hammingWeight(num)<<endl;
    return 0;
}