Count number of Set Bits in Integer

Count set bits in Integer OR
Count number bits set in an Integer OR
Count number of ones in Binary.

---

We need to write an algorithm to determine the number of set bits in integer.
In other words, count the number of 1's present in binary representation of number.

Let's see what is the input and expected output for better understanding,

Case 1:
Input: 6 Binary equivalent of 6:   0 1 1 0
Number of bits set(1's) :  2
Output: 2

Case 2: 
Input:14
Binary equivalent of 14:   1 1 1 0
Number of bits set(1's) :  3
Output: 3

Case 3: 
Input: 8
Binary equivalent of 8:   1 0 0 0
Number of bits set(1's) :  1
Output: 1

Algorithm

---

Approach 1: 

In this apprach, we will use the modulo and divide technique to find number of set bits, 
We will convert the number into its Binary equivalent and count the set bits.

How we convert Decimal number to Binary number 
We divide the given number by 2, 
     If number is perfectly divisible by 2 with 0 remainder then copy 0.
     If number is not perfectly divisible by 2 with 1 remainder then copy 1.

For next iteration, divide number by 2, Continue till given number become 0.

In this approach, 

1. we will initialize "counter=0" and start converting given number to its binary representation. 
2. Divide number by 2 and if it is not perfectly divisible by 2 then remainder is 1 that is bit is set here and we will increment our "counter". 
3. Divide number by 2 for next iteration and continue till given number becomes 0. 
4. Print "counter". 

Count number of set bits Java Program using Approach 1

---

package javabypatel;

public class CountSetBitsInInteger {

 public static void main(String[] args) {
  int n = 13;
  System.out.println(countSetBit(n));
 }
 
 private static int countSetBit(int number){
  int counter = 0;
  
  while(number>0){
   if(number%2 == 1){
    counter++;
   }
   number = number/2; //or number = number >> 1
  }
  return counter;
 } 
}

Approach 2: 

In this approach, we will use Bit operator for counting bit set in number.
For a given number, check whether Right most bit of number is set or not. If set, we will increment counter.

How to check whether right most bit is set?

1. If we do bitwise AND between given number and 1 (number & 1),
   we will get result either 1 or 0.
   If Right most bit is set, then result will be 1. (we will increment counter at this time).
   If Right most bit is not set, then result will be 0. 
2. We are done checking for Right most bit and now time is to check second last bit.
   We will Right shift number by 1, now second last bit is at Right most position.
   (number >> 1) 
3. Repeat steps untill number become 0. 
4. Return "counter".

Java Program to count number of set bits in Integer using Approach 2.

---

package javabypatel;

public class CountSetBitsInNumber {

 public static void main(String[] args) {
  int n = 13;
  System.out.println(countSetBits(n));
 }
 
 private static int countSetBits(int number){
  int count = 0;
  while(number>0){
   int result = number & 1;
   count += result;
   number >>= 1;
  }
  return count;
 }
}

Approach 1 and 2 check all the bits of a number to count number of set bits.
So if number is 8 (binary = 1000), in this case, above approaches requires 4 scan to count number of bits set.
Can we optimize it? Yes. Lets look at optimized approach.

Approach 3: 

In this approach, we will use Bit operator for counting bit set in number.
Instead of scanning all the bits of a number, we will only look at set bits in this approach.

Before looking into this approach, we need to understand algorithm that is going to be used in this approach,

When we do bitwise AND between (number) & (number-1), Right most SET bit of "number" will be unset.

Lets see example,
number       = 6, binary representation = 0 1 1 0 (from right, bit is set at position 1 and 2)
(number-1) = 5, binary representation = 0 1 0 1
                                                             ------------------ 
(number) & (number-1)                = 0 1 0 0 
Right most SET bit(at position 1) is unset from original number 6.

Remaining number = 4 = 0 1 0 0

number       = 4, binary representation = 0 1 0 0 (from right, bit is set at position 2)
(number-1) = 3, binary representation = 0 0 1 1
                                                             ------------------ 
(number) & (number-1)                = 0 0 0 0  
Right most SET bit(at position 2) is unset from original number 4.

So each time you do bitwise AND between (number) & (number-1), Right most set bit is unset.

Algorithm

1.  We will do Bitwise AND between (number) & (number-1) and increment counter as right most bit of number will be unset.
   number = number & number-1
   
2.  Repeat step 1, until number become 0.

Count number of Bits set bits in Number in Java Approach 3.

---

package javabypatel;

public class CountSetBitsInInteger {

 public static void main(String[] args) {
  int n = 13;
  System.out.println(countSetBits(n));
 }
 
 private static int countSetBits(int n){
     int count = 0;
     while (n > 0){
       n &= (n-1) ;
       count++;
     }
     return count;
 }
}

You may also like to see

---

Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.