Given an Integer and you have to count its set bits.

So here, Actually we have to find number of digits with value 1 in the given number when it is represented in its binary form.
i.e (5)₁₀ = (0101)₂
So number of count bits in 5 = 2
We have to just count number of 1's in given binary number.

We have explored two approaches:

• Naive approach
• Brian Kernighan Algorithm

Now how can we count ?

Naive Approach

As we know if we take AND of any number N with 1 then it returns the last or least significant or right most bit of N.
if LSB = 0, it returns 0
if LSB = 1, it returns 1
i.e

   i) 5 = 0101 
        1 = 0001
        5&1 = 0101 & 0001 = 0001, here the we get result = 1 ---> LSB of N = 1
   ii)  4 = 0100
        1 = 0001
        4&1 = 0100 & 0001 = 0000, here we get the result = 0 ---> LSB of N = 0

So what if we make it possible to shift every bit one by one at LSB position and check if it is 1 or 0 ?
This is a good idea, we everytime (uptil N get equals to 0) right shift N and check its LSB by taking AND of N with 1.
if result = 1, count = count+1
if result = 0, count = count+0
Actually what we are doing is we are addding the result of AND to the count.
i.e

N = 5 = 0101

initially count = 0

0101 & 0001 = 0001 ---> count = 1

Now right shift N  ---> 0010

0010 & 0001 = 0000 ---> 0000

Now right shift N  ---> 0001

0001 & 0001 = 0001 ---> count = 2

Now right shift N  ---> 0000

Now N = 0 so we stop here.

So we got count = 2 implies 2 set bits in 5.

Pseudo-Code

• CountSetBits(N)
• int count = 0.
• while N not equal 0
  count = count + (N&1)
  Right-Shift N
• return count

Code

import java.util.* ;
public class OpenGenus {
    //method to count number of set bits.
    public static int CountSetBits(int N)
    {
        int count = 0;
        // Right shift N untill it gets equal to 0
        // for each value of right shifted N, AND it with 1 and add the result to count
        while(N != 0){
            count = count + (N & 1);
            N = N >> 1;
        }
        return count;
    }

    // Driver method

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Input the number
        System.out.println("Enter the number");
        int N = sc.nextInt();
        // call CountSetBits method and print the result.
        System.out.println("Number of set bits in number are "+" "+ CountSetBits(N));
    }
}

Time-Complexity

As it right-shift the binary number to check everytime the right-most bit until the number get equals to 0.
Its time coplexity is O(logN).

Brian Kernighan Algorithm

This algorithm basically based on one observation as follow:-

When 1 is subtracted from any number then all the bits after rightmost bit having value 1(set bit) and including the right-most set bit itself gets flipped.
i.e

     12 is 00001100 in binary
     11 is 00001011 in binary
     10 is 00001010 in binary
     9  is 00001001 in binary

We can observe that we will get 11 from 12 if we flip all the bits to the right of right-most set bit including itself.
i.e

00001100 have rightmost set bit at 3rd position from right and if we flip
---> 00001011 which is equal to 11.

now if you could observe what happens if we do 11 & 12
 12   00001100
 11   00011011
     -----------
      00001000      it flips rightmost set bit of 12.

So the idea is what if we repeat this again and again untill all the bits converted to unset bits or number converts to 0.
In each turn every right-most set bit will get flipped so, count of set bits will be equal to number of turns/loops required to make number equal to 0.
for example.

we want to count the set bits in 12.
1)
12   00001100
&
11   00011011
     -----------
     00001000  = 8
2)
8    00001000
&
7    00000111
     -----------
     00000000 = 0
     
     It takes 2 turns/loops to make the number equal to 0.
     Therefore there are 2 set bits in 12.

Pseudo-Code

• CountSetBits(N)
• int count = 0
• while N not equal 0
  N = N & (N-1)
  count++
• return count

Code

import java.util.* ;
public class OpenGenus {
    //method to count number of set bits.
    public static int CountSetBits(int N)
    {
        int count = 0;
        // run while loop until N gets equals to 0
        // N & N-1 flips the right most set bit to 0.
        while(N != 0){
            N = N & (N-1);
            count++;
        }
        return count;
    }

    // Driver method

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Input the number
        System.out.println("Enter the number");
        int N = sc.nextInt();
        // call CountSetBits method and print the result.
        System.out.println("Number of set bits in number are "+" "+ CountSetBits(N));
    }

Time-complexity

As its loops over the binary number to flip everytime the right-most set bit until the number get equals to 0.
Its time complexity is O(logN).

One more Approach(Recursive)

It is again based on an observation

We write number from 0 to 15

0 = 0000        9 = 1001
1 = 0001       10 = 1010
2 = 0010       11 = 1011
3 = 0011       12 = 1100
4 = 0100       13 = 1101
5 = 0101       14 = 1110
6 = 0110       15 = 1111
7 = 0111
8 = 1000

if we notice count of set bits in
1 = set bits in ((1/2)=0)+1 = 0+1 = 1
2 = set bits in ((2/2)=1) = 1
3 = set bits in ((3/2)=1)+1 = 1+1 = 2
4 = set bits in ((4/2)=2) = 1
5 = set bits in ((5/2)=2)+1 = 1+1 = 2

It concludes:-
1.If number N is even then count of set bits equals to count of set bits in N/2.
2.If number N is odd then count of set bits equals to (count of set bits in N/2) + 1 

Pseudo-Code

• CountSetBits(N)
• if N = 0 then return 0
• if N%2 = 0
  return CountSetBits(N/2)
  else
  return CountSetBits(N/2)+1

Code

import java.util.* ;
public class OpenGenus {
    //method to count number of set bits.
    public static int CountSetBits(int N)
    {
        int count = 0;
        // if N = 0 return 0 as 0 contains zero number of set bits
        if(N==0){
            return 0;
        }
        // else call the method CountSetBits for N/2
        // if N is odd add 1 and return
        if(N % 2 ==0){
            return CountSetBits(N/2)
        }
        else{
            return CountSetBits( N/2)+1;
        }

    }

    // Driver method

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Input the number
        System.out.println("Enter the number");
        int N = sc.nextInt();
        // call CountSetBits method and print the result.
        System.out.println("Number of set bits in number are "+" "+ CountSetBits(N));
    }
}

Time-Complexity

As every time N is getting divided by 2 in a loop.
Its time-complexity is O(logN).

Space-Complexity

Because of stack used in recursion space complexity is O(logN).

With this article at OpenGenus, you must have the complete idea of Counting the number of set bits (1) in a number using naive approach and Brian Kernighan Algorithm.