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.

Algorithm

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;
 } 
}

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;
 }
}

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

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

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