Count set bits in an integer using Brian and Kerningham Algorithm in Java
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
Leave a Reply