Count 1 in Binary 365

Question

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?

Solution

两种解法。

第一种比较straight forward，将每一位和1取&操作，若非0则记一次1。

第二种比较巧妙，num－1可以将最低位的1变为0，然后和num取&操作将num中最低位的1删去并将剩下的1保留下来，如此重复直到num中的1全部变为0，变换的次数即为num中1的个数。

代码如下：

public class Solution {
    /**
     * @param num: an integer
     * @return: an integer, the number of ones in num
     */
    public int countOnes(int num) {
        // write your code here
        int a;
        int count = 0;
        for(int i = 0; i < 32; i++){
            a = 1 << i;
            if((num & a) != 0){
                count++;
            }
        }

        return count;
    }
}

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