How to Count number of 1s (Set Bits) in a binary number in Java [Solved]

Good morning folks, In today's article, we are going to discuss one of the frequently asked bit manipulation-based interview questions, how do you count the number of set bits in a given bit sequence?  Bit Manipulation is an important topic in programming interviews and a good programmer should have sufficient knowledge and skill to work with binary numbers. This kind of question tests the skill of the programmer. Sometimes, it is also asked as to how to count the number of 1s (ones) in a given number? Both are the same question because 1 is also known as set bit.  For example, if the given input is 1000110010 then your program should return 4, as three are only four set bits in this bit sequence.

There are many techniques to solve this problem and you might have your unique way as well, but let's explore some tried and tested ways to solve the problem. 

Btw, if you are the first time seeing this problem then I suggest you solve it yourself first because the best way to learn why a given algorithm works are to take a pencil and run through 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. This means you must know how to move bits and how to test a particular bit to find whether it's one or zero.

When no set bit is left in the number i.e. number becomes zero then the number of iterations is returned. That's your number of 1s or set bits in a given bit sequence. Let's learn more about how this algorithm works.

Btw, I am assuming that you are familiar with binary numbers and understand how they are represented in Java like in 2's complement form. I also assume that you know how to use bitwise operators like &, | and ^, I mean bitwise AND, OR and XOR operators and bit shift operators like <<, >>, and >>> i.e. left shift operator, right shift operator, and right shift without sign operator.

If you are not familiar with them then I suggest you first understand them by joining a comprehensive course like The Complete Java Masterclass, otherwise, it would be really difficult to understand and solve bit manipulation-based problems.

The algorithm to count the number of 1s in Given Bit Sequence

As I said, there are many techniques to count a number of set bits in a given bit sequence, and one of them is starting 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 the number of set bits in a given number.

Here are the exact steps of this algorithm:

    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

The 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 on your own, I suggest you read Hacker's delight at least once. One of the best books for Programmers interested in learning binary, and you know, there are only two types of programmers, one who knows binary, and others who don't.

Btw, If you have difficulty reading this book, which is quite possible because it's not one of the easiest books to read, I also suggest checking a good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java which covers this topic in much simpler language.

How to find the number of set bits in a 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 ways to count the number of set bits in a given binary number in Java.

If you have any difficulty 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

Btw, if you have any difficulty learning the algorithm, here is a nice slide that explains, step by step,  how this bit manipulation algorithm works:

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 in learning more about how to work with bits and bytes in Java, I strongly suggest you join a good course on Algorithms like Data Structures and Algorithms: Deep Dive Using Java one of the best courses to learn binary manipulation. It contains many essential tricks to deal with bit sequence.

Related Bit Manipulation and Data Structure Algorithms tutorials on Java

• How to check if a number is a power of two in Java? (answer)
• 10 Best Data Structure and Algorithms Courses in Java (best courses)
• How to find the GCD of two numbers in Java? (answer)
• Top 5 Books to learn Data Structure and Algorithms (best books)
• How to check if a given number is even or odd in Java? (answer)
• 10 Free Data Structure and Algorithms courses (free courses)
• How to swap two integers without using the temp variable? (trick)
• 21 String Coding Problems from interviews (coding problems)
• The difference between the bitwise and bit-shift operators in Java? (answer)
• How to add two numbers without using the arithmetic operator in Java? (tip)
• What is the difference between left and right shift operators in Java? (answer)
• 100+ Data Structure and Algorithm Questions for Programmers (list)
• 75+ Coding Questions to crack any programming interviews (questions)
• 10 Data Structure and Algorithm courses for Interviews (courses)

Thanks for reading this article so far. If you like this coding problem and my explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are keen to master data structure and algorithms and don't mind learning from free resources then you can also check this list of free algorithms courses to start with.