Code Pumpkin

Program to find number of set bits in the Binary number

August 20, 2017
Posted by Pumpkin
Subscribe

In this post, we will discuss about one of the easiest and commonly asked Bit Manipulation Interview Question i.e. Find total number of set bits in the given number? 

There are many approach to solve this problem. Here, we will discuss about below two approaches:

  1. & and >> Approach (Naive Approach)
  2. Brian Kernighan's Approach


1) & and >> Approach (naive Approach)

In this approach, we perform bitwise and (&) and  bitwise right shift (>>) operations for each bit in a number.

Step 1: (n&1) operation returns 1, if right most bit of the number is 1. 

Step 2 : If this returns 1, we increment our counter.

Step 3 : perform n=(n>>1) , so that we can check the value of 2nd right most bit.

Continue this process, until becomes 0.

Let's understand this by below example.

Number of Set Bits

Java Program Implementation


public static int getNumberOfSetBitsApproachOne(int n){
    int count = 0;
    while(n>0)
    {
        
        if((n&1) == 1)   // Similarly Condition (n&1)==0 can be used to calculate
        {                 //number of zeros in the given number
            count++;
        }
        n = n>>1;
    }
    System.out.println(count);
    return count;
}

The naive approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.

For Example, it will require 8 iiteraton to check number of set bits in number 128  (1000 0000)


2) Brian Kernighan's Approach  

First of all, its not KerniGHAN, its pronounced as Kernihan, the G is silent 😉 

This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. For above Example of 128, it will give the answer only in one iteration.

In the worst case, it passes once per each bit and takes same time as naive approach. i.e. when all bits are 1 as in 255 (1111 1111)

What is Brian Kernighan's Approach?

It uses n = n & (n-1) approach.

If you perform bitwise operation on n and (n-1), it produces the number with set bits one less than the original number.  For example, if has 4 set bits and if you perform n&(n-1), it produces the number with 3 set bits.

For example, let's try all the 4-bit combinations:


 n     n     n-1     n&(n-1)
--   ----   ----   -------
 0   0000   0111    0000 
 1   0001   0000    0000 
 2   0010   0001    0000 
 3   0011   0010    0010
 4   0100   0011    0000 
 5   0101   0100    0100
 6   0110   0101    0100
 7   0111   0110    0110
 8   1000   0111    0000 
 9   1001   1000    1000
10   1010   1001    1000
11   1011   1010    1010
12   1100   1011    1000
13   1101   1100    1100
14   1110   1101    1100
15   1111   1110    1110

So after performing each & operation, we will increment the counter. We will continue this process until n!=0

Java Program Implementation 


public static int getNumberOfSetBitsApproach2(int n){

	int count = 0;
	while(n != 0){
		n = n&(n-1);
		count++;
	}

	System.out.println(count);
	return count;
}

We can use above two approaches to write a program to check if a given number is power of two or not?

That's all for this topic. If you guys can think of any more similar java programs, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

Happy Learning 🙂


Further Reading For interview Preparation

  1. Program To Find Unique Array Element
  2. Program To Check Whether A Number Is Prime Or Not
  3. Program To Check If A Given Number Is Power Of Two Or Not?
  4. N Queen Problem
  5. Sudoku Solver
  6. Trapping Rain Water
  7. Graph Search – Breadth First Search
  8. Graph Search – Depth First Search
  9. interface VS abstract class
  10. Access Modifiers (public, private, protected and default scope)
  11. HashMap vs Hashtable Vs SynchronizedMap Vs ConcurrentHashMap
  12. CountDownLatch Vs CyclicBarrier

Tags: , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank