Getting the number of set bits in a number using Java

Suppose, you are given an integer number. You have to tell how many set bits are there in the number.

If we know bit operations, it is easy to get the count. First, I am explaining how to get this using bitwise AND operations.

If a bit is a set bit of a number, that bit will be 1. For n=16, there is only one set bit. Because in binary representation we have these bits: 10000. For n=23, there are 4 set bits. Because in binary representation we have these bits: 10111.

Now I need to know how bitwise AND works. The output of bitwise AND of two integers depends on the bit representation of the respective numbers. Let’s see an example:

for two integers 23 and 45, bitwise AND of these numbers is:-

23 & 45
=> 010111
 & 101101
----------
   000101 (which is equivalent to 5 in decimal system)

So we are seeing if we get 1 in the same position of the respective bit, bitwise AND is giving me 1 for that position, otherwise, it becomes 0. Using this, we can easily know if there is a set bit in a position of a number.

Suppose, we want to know if the 4th LSB of 45 is 1 or 0. So we will do bitwise AND of 45 and (1<<(4-1)).

Why (1<<(4-1))? Because it will give me a number with only one set bit in the 4th LSB.

1<<(4-1) will give me the number 8 with a binary representation of 1000. So now if we do the bitwise AND of 45 and 8, and it gives me 0, then, the 4th LSB of 45 is 0. If we get 8 itself, the 4th LSB of 45 is 1.

45 & 8 
=> 101101
 & 001000
----------    
   001000 (which is equivalent to 8 in decimal system)

So coming to the solution using bitwise AND. We need to run a loop from 0 to 30 (as the integer is 32 bit, MSB is reserved for the sign) and need to check every bit. We will count if we get a non-zero value as an output of bitwise AND.

int count = 0;
for(int i=0;i<=30;i++) {
    if(((1<<i)&45) > 0)
        count++;
}

So here count represents the number of set bits.

Now how will you do this in Java? You can do this easier way in Java. Just write this:

BitSet bitSet = BitSet.valueOf(new long[] {45});
int count = bitSet.cardinality();

Easier, na? Happy Coding!

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s