Brian Kernighan Algorithm Algorithm
The Brian Kernighan Algorithm is a popular technique used for efficiently counting the number of set bits (1s) in an integer's binary representation. This algorithm is named after the renowned computer scientist Brian W. Kernighan, who was one of the co-authors of the widely-used programming book "The C Programming Language". The algorithm works by repeatedly subtracting the value of the least significant set bit from the given integer until it eventually becomes zero.
The key idea behind the Brian Kernighan Algorithm is that subtracting 1 from an integer flips all the bits following the rightmost set bit (including that set bit). Therefore, performing a bitwise AND operation between the integer and its decremented value effectively eliminates the rightmost set bit, leading to a faster convergence to zero. This operation is repeated until the integer becomes zero, and the number of such iterations is equal to the count of set bits in the binary representation of the original integer. The Brian Kernighan Algorithm is considered highly efficient, especially when the number of set bits is relatively small compared to the size of the integer.
package Others;
import java.util.Scanner;
/**
* @author Nishita Aggarwal
* <p>
* Brian Kernighan’s Algorithm
* <p>
* algorithm to count the number of set bits in a given number
* <p>
* Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the
* rightmost set bit).
* So if we subtract a number by 1 and do bitwise & with itself i.e. (n & (n-1)), we unset the rightmost set bit.
* <p>
* If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
* <p>
* <p>
* Time Complexity: O(logn)
*/
public class BrianKernighanAlgorithm {
/**
* @param num: number in which we count the set bits
* @return int: Number of set bits
*/
static int countSetBits(int num) {
int cnt = 0;
while (num != 0) {
num = num & (num - 1);
cnt++;
}
return cnt;
}
/**
* @param args : command line arguments
*/
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int setBitCount = countSetBits(num);
System.out.println(setBitCount);
sc.close();
}
}
