/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/others/BrianKernighanAlgorithm.java
50 строк
1 KB
Piotr Idzik
style: enable `HideUtilityClassConstructor` in checkstyle (#5147)
08 май 2024, 09:58
Не верифицирован
08 май 2024, 09:58
d3bb691
Код
Авторство
О чём код?
package com.thealgorithms.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 final class BrianKernighanAlgorithm { private 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(); } }