Number of 1 Bits

Problem Description
Calculate Hamming Weight of an unsigned integer.
NOTE: Hamming Weight of an unsigned integer is the number of 1 bits in its unsigned representation.
Solution
In order to solve the problem, we iteratively check the right most bit if it is 1, then shift all the bits to the right 1 bit (i.e divide it by 2). The code for this implementation is in part I (java) & part II (C++).

We can also do a trick here. It's good to know that we can drop the rightmost set bit by the operation (n&(n-1)).

It is in part III & IV. In part V, we see different naive implementations.
I. Java

view plainprint?

1. public class Solution {  
2.     // you need to treat n as an unsigned value  
3.     public int hammingWeight(int n) {  
4.         int count = 0;  
5.           
6.         while(n != 0){  
7.             if((n & 1) == 1) count++;  
8.             n >>>= 1;  
9.         }  
10.         return count;  
11.     }  
12. }  

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        
        while(n != 0){
            if((n & 1) == 1) count++;
            n >>>= 1;
        }
        return count;
    }
}

II. C++

view plainprint?

1. class Solution {  
2. public:  
3.     int hammingWeight(uint32_t n) {  
4.         int count = 0;  
5.         while(n != 0){  
6.             if(n & 1) count++;  
7.             n >>=1;  
8.         }  
9.         return count;  
10.     }  
11. };  

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

III. Java with (n & (n-1)) Solution

view plainprint?

1. public class Solution {  
2.     // you need to treat n as an unsigned value  
3.     public int hammingWeight(int n) {  
4.         int count = 0;  
5.         while(n!=0){  
6.             n &= (n-1);  
7.             count++;  
8.         }  
9.         return count;  
10.     }  
11. }  

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            n &= (n-1);
            count++;
        }
        return count;
    }
}

IV. C++ with (n & (n-1)) Solution

view plainprint?

1. class Solution {  
2. public:  
3.     int hammingWeight(uint32_t n) {  
4.         int count = 0;  
5.       
6.         while (n) {  
7.             n &= (n - 1);  
8.             count++;  
9.         }  
10.       
11.         return count;  
12.     }  
13. };  

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

V. Naive Java Solutions (From Wiki: Hamming Weight with modification)

view plainprint?

1. public class Solution {  
2.       
3.     public int hammingWeight(int n) {  
4.         return popcount_3(n);     
5.     }  
6.     // you need to treat n as an unsigned value  
7.     final int m1  = 0x55555555; //binary: 0101...  
8.     final int m2  = 0x33333333; //binary: 00110011..  
9.     final int m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...  
10.     final int m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...  
11.     final int m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...  
12.     final int hff = 0xffffffff; //binary: all ones  
13.     final int h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...  
14.       
15.     //This is a naive implementation, shown for comparison,  
16.     //and to help in understanding the better functions.  
17.     //It uses 24 arithmetic operations (shift, add, and).  
18.     int popcount_1(int x) {  
19.         x = (x & m1 ) + ((x >>>  1) & m1 ); //put count of each  2 bits into those  2 bits   
20.         x = (x & m2 ) + ((x >>>  2) & m2 ); //put count of each  4 bits into those  4 bits   
21.         x = (x & m4 ) + ((x >>>  4) & m4 ); //put count of each  8 bits into those  8 bits   
22.         x = (x & m8 ) + ((x >>>  8) & m8 ); //put count of each 16 bits into those 16 bits   
23.         x = (x & m16) + ((x >>> 16) & m16); //put count of each 32 bits into those 32 bits   
24.         return x;  
25.     }  
26.       
27.     //This uses fewer arithmetic operations than any other known    
28.     //implementation on machines with slow multiplication.  
29.     //It uses 17 arithmetic operations.  
30.     int popcount_2(int x) {  
31.         x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits  
32.         x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits   
33.         x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits   
34.         x += x >>>  8;  //put count of each 16 bits into their lowest 8 bits  
35.         x += x >>> 16;  //put count of each 32 bits into their lowest 8 bits  
36.         return x & 0x7f;  
37.     }  
38.       
39.     //This uses fewer arithmetic operations than any other known    
40.     //implementation on machines with fast multiplication.  
41.     //It uses 12 arithmetic operations, one of which is a multiply.  
42.     int popcount_3(int x) {  
43.         x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits  
44.         x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits   
45.         x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits   
46.         return (x * h01)>>>24;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...   
47.     }  
48. }  

public class Solution {
    
    public int hammingWeight(int n) {
        return popcount_3(n);   
    }
    // you need to treat n as an unsigned value
    final int m1  = 0x55555555; //binary: 0101...
    final int m2  = 0x33333333; //binary: 00110011..
    final int m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...
    final int m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...
    final int m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...
    final int hff = 0xffffffff; //binary: all ones
    final int h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...
    
    //This is a naive implementation, shown for comparison,
    //and to help in understanding the better functions.
    //It uses 24 arithmetic operations (shift, add, and).
    int popcount_1(int x) {
        x = (x & m1 ) + ((x >>>  1) & m1 ); //put count of each  2 bits into those  2 bits 
        x = (x & m2 ) + ((x >>>  2) & m2 ); //put count of each  4 bits into those  4 bits 
        x = (x & m4 ) + ((x >>>  4) & m4 ); //put count of each  8 bits into those  8 bits 
        x = (x & m8 ) + ((x >>>  8) & m8 ); //put count of each 16 bits into those 16 bits 
        x = (x & m16) + ((x >>> 16) & m16); //put count of each 32 bits into those 32 bits 
        return x;
    }
    
    //This uses fewer arithmetic operations than any other known  
    //implementation on machines with slow multiplication.
    //It uses 17 arithmetic operations.
    int popcount_2(int x) {
        x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits
        x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits 
        x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits 
        x += x >>>  8;  //put count of each 16 bits into their lowest 8 bits
        x += x >>> 16;  //put count of each 32 bits into their lowest 8 bits
        return x & 0x7f;
    }
    
    //This uses fewer arithmetic operations than any other known  
    //implementation on machines with fast multiplication.
    //It uses 12 arithmetic operations, one of which is a multiply.
    int popcount_3(int x) {
        x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits
        x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits 
        x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits 
        return (x * h01)>>>24;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
    }
}