[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?

Solution 1. O(n) runtime

 1 public class Solution {
 2     /**
 3      * @param num: an integer
 4      * @return: an integer, the number of ones in num
 5      */
 6     public int countOnes(int num) {
 7         int count = 0;
 8         for(int i = 0; i < Integer.SIZE; i++){
 9             if(((num >>> i) & 1) == 1){
10                 count++;    
11             }
12         }
13         return count;
14     }
15 }

Solution 2. O(m) runtime

1 public int countOnes(int num) {
2     int count = 0;
3     while(num != 0){
4         num = num & (num - 1);
5         count++;
6     }
7     return count;
8 }