How to Count number of Set bits or 1's of Integer in Java? Example

There are multiple ways to count the number of 1's or set bits in an integer number in Java. You can use a bitwise and bit shift operator on your own, or, you can use Java API to count the number of set bits. Java 1.5 added two utility methods called bitCount(int i) which returns a number of 1's in your integer number, java.lang.Long class has a similar bitCount(long number) for long primitives. As I have said earlier, Coding questions are an important part of any Java interview, and from that recursion and bitwise operations are most popular. 

Questions like, How to Swap two numbers without a temp variable or How to find if a number is positive or negative are some of such questions, which you see now and then in various Java interviews.

In this Java tutorial, we will see, How to count the number of set bits in a number, for those who don't know what is set bit is, it's a bit with value 1. For example, 2, which is binary 0010 has just one set bit. On the other hand, 10, which is 1010 in binary has two set bit or a number of one's.

In most cases, the Interviewer will ask you to write a Java method without using API. In this article, we will see a couple of ways to calculate the number of set bits in a number on a Java program.

Question:

Write a function with signature int countOnes(int a), the method should return a number of bits that are "set" or "on" in the binary representation of the number provided. For example, countOne(10) should return 2, because the binary format of 10, which is 1010 has two bits on it.

Counting number of set bit using Java API method- Example

Before writing your own method to count a number of 1's let's have a look at Java API. Integer.bitCount(int number) and Long.bitCount(int number) are two super easy methods that can give you a count of a number of set bits in Java int or Java long primitive type. 

These methods are added from Java 1.5 and their code is based on Hacker Delight book. 

Here is how bitCount(int i) looks like from java.lang.Integer class :

public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
 }

You can see, it's based on hacker delight, figure 5-2.

1. Simple way to count the number of 1's in a Java Integer

Integral numbers represented by int and long primitive are represented as 2's complement binary format. Also worth knowing is size of int primitive is 32 bit and size of long is 64 bit. 

If we go with simplest way, we can check LSB(Least Significant Bit) of number by doing AND operation with 1. This can give us count of 1's if we shift bits on the right direction.

We can use right shift without sign operator for that. Here is sample code to count number of 1's in Java integers :

 public static int countOne(int number){

        int count = 0;
        for(int i =0; i<32; i++){
            if( (number&1) == 1) {
                count++;
            }
            number = number >>> 1;
        }
        return count;
}

Now if you write this method, the interviewer will most likely ask you about optimization. If you look closely, you can see that this method always loops 32 times, which is the size of int. 

If you write a similar method for long, it will loop 64 times, can you think of what to optimize now? You can optimize this loop. Instead of making a loop proportional to the size of bits, you can make it proportional to a number of set bits. 

Here is a modified version :

public static int countSetBits(long number){
        int count = 0;
        while(number>0){
            ++count;
            number &= number-1;
        }
        return count;
}

In this function, we are using AND operation and number -1 to gradually reduce the number of 1's from the original number. It means this loop will only run 4 times if the number contains 4 set bits. Here is a complete Java program to count a number of set bits on numbers.

/**
  * Java Program to count number of 1's in a integer.
  * @author Javin Paul
  */
public class CountSetBits {   

    public static void main(String args[]){
        System.out.println("Java method to count number of 1's in a integer");
        System.out.printf("Number of one's in %d is %d %n", 2, countOne(2));
        System.out.printf("Number of one's in %d is %d %n", 3, countOne(3));
        System.out.printf("Number of 1's in %d is %d %n", 10, countOne(10));
       
       
        //A short and sweet Java API trick to find count of set 
        //bits in a integer or long
        System.out.println("Counting number of set bits on integer 
                              and long using Java API");
        int count = Integer.bitCount(2);
        System.out.printf("Number of set bit on %d is %d  %n", 2, count);
        System.out.printf("Number of set bit on %d is %d  %n", 3, 
                                  Integer.bitCount(10));
       
        //One optimized way to count number of one's in a number in Java
        //this method is proportional to number of set bit's rather 
        //than bit size e.g. 32 for int, 64 for long
        System.out.println("Another optimized Java method to count number
                                 of set bits");
        System.out.printf("Number of set bit on %d is %d  %n", 2, 
                                  countSetBits(2));
        System.out.printf("Number of set bit on %d is %d  %n", 3, 
                                  countSetBits(3));
    }
   
   
    /** 
      * This method is not optimized, as it iterates 32 times for 
      * integer numbers in all cases, can you optimize it?
      */
    public static int countOne(int number){
        int count = 0;
        for(int i =0; i<32; i++){
            if( (number&1) == 1) {
                count++;
            }
            number = number >>> 1;
        }
        return count;
    }
   
    /**
      * Optimized version of previous one, loop is proportional to number
      * of 1's instead bit size of number.
      */
    public static int countSetBits(long number){
        int count = 0;
        while(number>0){
            ++count;
            number &= number-1;
        }
        return count;
    }
   
  
}
Output:
Java method to count number of 1's in a integer
Number of one's in 2 is 1
Number of one's in 3 is 2
Number of 1's in 10 is 2
Counting number of set bits on integer and long using Java API
Number of set bit on 2 is 1 
Number of set bit on 3 is 2 
Another optimized Java method to count number of set bits
Number of set bit on 2 is 1 
Number of set bit on 3 is 2 

That's all on How to count a number of set bits or 1's on integer numbers in Java. We have seen one way of doing it using Java bitwise and bit shift operator and further optimized that. By the way, there can be multiple ways of doing this, using the bitwise operator. If you love playing with bits, you must check hackers delight, an awesome book on bit twiddling.

And now is the quiz time , what is difference between bitwise and bit shift operator in Java? What are the examples of bit wise and bit shift operator in Java?