Data Structures & Algorithms in Java – Binary – Number of 1 bits in an integer

Problem:

Given an integer , count the number of 1 bits in it when converted to a binary

Input:

8

Output:

1 (since the binary representation of 8 is 1000 and it has a single 1 bit)

Try out the solution here:

https://leetcode.com/problems/number-of-1-bits/

Solution:

One way to solve this problem is to do AND operation between the integer and the number 1.

If the result is 1 then the last digit is 1 , keep this value in a counter.

Now right shift the number so that the last digit is popped out and continue the above.

Keep doing it until the number becomes zero.

Here is a code sample:

Code:

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

Time complexity is O(logn) since the number of bits in an integer is maximum 32 . So the above while loop can run for 32 times in the worst case whereas the possible values for the number n is 2^{^}32.

Extra space complexity is O(1) to store the output.

The above code can be implemented in a recursive way.

Recursive version:

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

}

Time complexity and space complexity remain the same.

Brian Kernighan’s Algorithm:

One another way to solve the above problem is using Brian Kernighan’s algorithm.

Below is the algorithm:

Brian Kernighan’s algorithm makes use of the below fact:

When you subtract a number by 1 , it will flip all the bits from the rightmost “1” bit.

For example, if you take the number 10. It is represented in binary as :

1010

Subtracting 1 from the above number gives:

1001

As you see the last two bits are flipped (starting from the rightmost “1” bit )

Now if you do an AND operation between the above two it will make the last two digits zero as they are flipped in the opposite direction in each number.

1010 & 1001 = 1000

Continue doing this until the entire number becomes zero.

In the above example , again subtract 1 with 1000 , it gives 0111.

Perform AND operation between 1000 and 0111:

1000 & 0111 = 0

So you stop there.

The number of times you do this AND operation gives the number of 1 bits in the given integer since at each AND operation you make the rightmost 1 bit and the consecutive bits as 0.

Algorithm:

STEP1: While the given number is not 0,

STEP1a: Subtract the number by 1 and perform AND operation between the original number and the number after subtraction.

STEP1b: Increment a counter

STEP2: Return counter value.

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 & (n-1);
                
                count++;
            }
        
        return count;
    }
    

}

The time complexity of above algorithm is also O(logn) and the space complexity is also the same O(1)

The above algorithm can also be implemented recursively as below:

public class Solution {
    
    public int hammingWeight(int n) {
     
      
        if(n == 0){
            
            return 0;
        }
        return 1 + hammingWeight(n & (n-1));
    }
    

}

That’s it!