Count number of set bits

To count a number of set bits we & each bit position with 1 if this is set then increment the count.

 Setbit count using Brian Kernighan algorithm

Example 1:

Input : n=10 
Output: 2

Example 2:

Input : n=15
Output: 4

Approach 1: Iterate for all bits of the given number in binary form

Java

public class SetbitsCount {
    public static void main(String[] args) {
        // 1010
        int n = 10;
        int setbit = countOfSetBits(n);
        System.out.println("Set bits are " + setbit);
    }

    // method to cont set bit
    public static int countOfSetBits(int num) {
        int setbit = 0;
        while (num > 0) {
            // if num%2==0 then increase setbit
            if (num % 2 != 0) {
                setbit++;
            }
            num = num / 2;
        }
        return setbit;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the set
//bits of the given number
int countOfSetBits(int n)
{
    int count=0;

    //iterate till the number 
    //beomes 0
    while(n>0)
     {

         //if the bit is set
         //increment the count
         if(n&1)
           count++;
        //move to the next bit
         n=n/2;
     }
    //return the count of set bits
    return count;
}
int main()
{
    //1010
    int n=10;
    int setbit=countOfSetBits(n);
    cout<<"Set bits are ";
    cout<<setbit<<"\n";
    return 0;
}
//Time Complexity: O(log(n))

Approach 2: Using Brian Kernighan algorithm

Java

public class SetbitsCount {
    public static void main(String[] args) {
        // 1010
        int n = 10;
        int setbit = countOfSetBits(n);
        System.out.println("Set bits are " + setbit);
    }

    // method to find the set
    // bits of the given number
    public static int countOfSetBits(int n) {
        int count = 0;
        while (n > 0) {
            count++;
            n = n & (n - 1);
        }
        // return the count of set bits
        return count;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the set
//bits of the given number
int countOfSetBits(int n)
{
    int count=0;
    while(n>0)
     {
           count++;
           n=n&(n-1);
     }
    //return the count of set bits
    return count;
}
int main()
{
    //1010
    int n=10;
    int setbit=countOfSetBits(n);
    cout<<"Set bits are ";
    cout<<setbit<<"\n";
    return 0;
}
//Time Complexity: O(log(n))