Count set bits in an integer using Brian and Kerningham Algorithm in Java

By Harsh Gupta

In this article, we will learn Brian and Kerningham Algorithm to count the number of set bits of a number in Java.

Java program to count set bits in an integer using Brian and Kerningham Algorithm

We know that if we subtract 1 from a decimal number then it flips all the bits starting from right side till it encounters a set bit(i.e. 1) including the set bit.

binary representation of 8 is 00001000

binary representation of 7 is 00000111

Now, suppose we are given a number ‘num’ and if we do bitwise AND of (num) and (num-1) then we unset the rightmost set bit of num. Hence if we perform bitwise AND of num and num-1 in a loop and store result in num itself then the number of times this loop iterates is the count of set bits of given number num.

Code:

import java.io.*; 

class cntSetBits { 

  static int cntSetBits(int num) 
  { 
    int cnt = 0; 
    while (num > 0) { 
      num = num & (num - 1); 
      cnt++; 
    } 
    return cnt; 
  } 

  public static void main(String args[]) 
  { 
    int num = 5;
    int val=cntSetBits(num);
    System.out.println("No. of set bits are "+val); 
  } 
} 
 

Output:

No. of set bits are 2

Time Complexity: O(log(num))

Recursive Implementation: 

We can also apply a recursive approach to this algorithm

 import java.io.*; 

class cntSetBits { 

  // Recursive Function to count set bits of a number 
  public static int cntSetBits(int num) 
  { 

    // base case 
    if (num == 0) 
      return 0; 
    else
      return 1 + cntSetBits(num & (num - 1)); 
  } 

  public static void main(String[] args) 
  { 

    int num = 5; 

    val=cntSetBits(num);
    System.out.println("No. of set bits are "+val); 
  } 
} 
 

Output:

No. of set bits are 2