[LintCode] Count 1 in Binary

Count how many 1 in binary representation of a 32-bit integer.

Example

Given 32, return 1

Given 5, return 2

Given 1023, return 9

Challenge

If the integer is n bits with m 1 bits. Can you do it in O(m) time?

常规解法：

class Solution {
public:
    /**
     * @param num: an integer
     * @return: an integer, the number of ones in num
     */
    int countOnes(int num) {
        // write your code here
        int cnt = 0;
        while(num != 0){
            cnt += (num&1);
            num >>= 1;
        }
        return cnt;
    }
};

使用STL的解法： 

#include <bitset>
class Solution{
public:
/**
* @param num: an integer
* @return: an integer, the number of ones in num
*/
int countOnes(int num) {
// write your code here
bitset<sizeof(int)*8> bitvec(num);
return bitvec.count();
}
};