How to Count number of 1s (Set Bits) in Given Bit Sequence in Java

Good morning folks, In today's article, we are going to discuss one of the frequently asked bit manipulation based interview question, how do you count the number of set bits in given bit sequence? It is also asked as how to count the number of 1s in given number? Both are the same question because 1 is also known as set bit.  For example if given input is 1000110010 than your program should return 4, as three are only four set bits in this bit sequence. There are many techniques to solve this problem. Best way to learn why a given algorithm works is to take a pencil and run though a few examples. The solution presented in this article, you might have seen this already in hackers delight, runs through a loop and clears the lowest set bit of number during each iteration. When no set bit is left (i.e. number==0) than the number of iterations is returned. That's your number of 1s or set bits in given bit sequence. Let's learn more about how this algorithm works.



As I said, there are many techniques to count number of set bits in a given bit sequence, and one of them is start a loop and in each step clear the lowest set bit, Once all set bit will be cleared number will become zero and your loop should stop there. The number of iteration required is equal to number of set bits in given number.




    1. set the loop counter to zero to start-with
    2. loop until number > 0
         -- clear the least significant bit of number : number &= (number-1)
     -- increment the loop counter by 1 : count++;
    3. return the loop counter

Second step is most important where we are using bitwise AND operator, to clear the least significant bit of number.

If you like to solve this problem another way, here is an alternate algorithm:

n = n & ~(n & ~(n-1));

If you cannot understand it by your own, I suggest you to read Hacker's delight at least once. One of the best book for Programmers interested in learning binary, and you know, there are only two types of programmers, once who knows binary, and others who doesn't.

Here is a nice slide of algorithm to understand the technique better:

How to find number of set bits in given binary number

Here is our Java program which is based upon the first algorithm we have seen in this article. It's one of the simplest way to count number of set bits in given binary number in Java.  If you have any difficult understanding this program, feel free to comment.

/**
 * Java Program to count number of 1s in the given bit sequence
 * input : 1001010100111
 * output : 7
 * 
 * @author WINDOWS 8
 */

public class BitSequenceTest{

    public static void main(String args[]) {

        System.out.println("Testing our countBits() method with bit sequences");
        
        String[] input = {"000000", "001000", "101", "111",
                            "1110001", "111110000"};
        
        for(int i=0; i<input.length; i++){
            int binary = Integer.parseInt(input[i], 2);
            int count = countBits(binary);
            System.out.println("bit sequence : " + input[i]  + ",
                     number of 1s : " + count);
        }

    }
    
    /**
     * Java method  to calculate number of set bits in a given bit sequence.
     *
     * @param number is the integer but represent binary value
     * @return count of set bits in bit sequence 
     */
    public static int countBits(int number) {
        if (number == 0) {
          return number;
        }
        
        int count = 0;
        while (number != 0) {
          number &= (number - 1);
          count++;
        }
        return count;
      }

}

Output :
Testing our countBits method with bit sequences
bit sequence: 000000, number of 1s : 0
bit sequence : 001000, number of 1s : 1
bit sequence : 101, number of 1s : 2
bit sequence : 111, number of 1s : 3
bit sequence : 1110001, number of 1s : 4
bit sequence : 111110000, number of 1s : 5

That's all about how to count the number of set bits or 1s in the given bit sequence in Java. If you are interested on learning more about how to work with bits and bytes in Java, I strongly suggest you to read Hacker's delight one of the best book to learn binary manipulation. IT contains many essential tricks to deal with bit sequence.