Count Set Bits

Given a positive integer N, print count of set bits in it. 

The Question is what is set bit?

 

Ans: The total number of ones "1" in the binary representation of a number are the set bits

Ex: let the number be 10  its binary equivalent is 1010 so total set bits are 2.

similarly let the number be 21 its binary equivalent is 10101 total set bits are 3.

 

To count the set bits we will use 2 methods .

1.First one is by converting number to its Binary equivalent and counting the number of ones.

2.Second will be using bit manipulation.

 

Method 1:Convert the number to binary string and count ones.

Code:

public class SetBits {
 
    static int getBits(int N)
    {
        int count=0;
        String binary=Integer.toBinaryString(N);
        for(int i=0;i<binary.length();i++)
        {
            if(binary.charAt(i)=='1')
            {
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int N=11;
        int count=getBits(N);
        System.out.println("Set Bits are : "+count);

    }

}

Method 2: Using Bit Manipulation

Algo:

• we use bitwise & to get the set bits to recall what & operator does lets see.

{1,0}->0

{0,1}->0

{1,1}->1 

{0,0}->0 

 

• now lets see what n&(n-1) does , let n=10 

10&(10-1)=10&9=1 0 1 0  &  1 0 0 1  = 1 0 0 0

                                              ^

  As you can see this removes the set bit from last , so if we run through the number till the number becomes 0  we can count the number of set bits using the above &  operator.

 

 

Code:

 
public class SetBits {

    static int getSetBits(int N)
    {
        int count=0;
        while(N>0)
        {
            count++;
            N=N&(N-1);
        }
        return count;
       
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int N=11;
        int count=getSetBits(N);
        System.out.println("Set Bits are : "+count);

    }

}

lets evaluate the code:

1. N=11 is passed to the function , it initailizes the count=0
2. We run the while loop till the N=0
3. After iteration N will be addressed in the binary form  N=11 means -->1011
   

1.Count=1 --> N= 1010

2. Count =2 -> N=1000

3.Count =3 ->N=0000

 

     now we come out of the loop and return count.