Zählen Sie bei einer gegebenen Ganzzahl ihre gesetzten Bits.
Zum Beispiel,
Output: The total number of set bits in -1 is 32
Input: n = 16 (00001000)
Output: The total number of set bits in 16 is 1
1. Brute-Force-Lösung
Eine einfache Lösung besteht darin, jedes Bit (gesetzt oder nicht gesetzt) in einer Zahl zu berücksichtigen und einen Zähler zu führen, um die gesetzten Bits zu verfolgen. Diese Methode wird unten in C++, Java und Python demonstriert:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <bitset> using namespace std; // Naive Lösung, um die Gesamtzahl der gesetzten Bits in `n` zu zählen int countSetBits(int n) { int count = 0; for (int i = 0; i < 32; i++) { count += (n & 1); // Letztes Bit prüfen n >>= 1; } return count; } int main() { int n = 16; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "The total number of set bits in " << n << " is " << countSetBits(n) << endl; return 0; } |
Ergebnis:
16 in binary is 00010000
The total number of set bits in 16 is 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { // Naive Lösung, um die Gesamtzahl der gesetzten Bits in `n` zu zählen public static int countSetBits(int n) { int count = 0; for (int i = 0; i < 32; i++) { count += (n & 1); // Letztes Bit prüfen n >>= 1; } return count; } public static void main(String[] args) { int n = 16; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); System.out.println("The total number of set bits in " + n + " is " + countSetBits(n)); } } |
Ergebnis:
16 in binary is 10000
The total number of set bits in 16 is 1
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Naive Lösung zum Zählen der Gesamtzahl der gesetzten Bits in `n` def countSetBits(n): count = 0 for _ in range(32): count += (n & 1) # prüft letztes Bit n >>= 1 return count if __name__ == '__main__': n = 16 print(f'The total number of set bits in {str(n)} ({bin(n)}) is {countSetBits(n)}') |
Ergebnis:
16 in binary is 10000
The total number of set bits in 16 (0b10000) is 1
Der obige Brute-Force-Ansatz erfordert eine Iteration pro Bit. Bei einer 32-Bit-Ganzzahl werden also 32 Iterationen durchlaufen.
2. Verwenden des Algorithmus von Brian Kernighan
Wir können den Algorithmus von Brian Kernighan verwenden, um die Leistung des obigen naiven Algorithmus zu verbessern. Die Idee ist, nur die gesetzten Bits einer Ganzzahl zu berücksichtigen, indem das am weitesten rechts stehende gesetzte Bit (nachdem es gezählt wurde) ausgeschaltet wird, sodass die nächste Iteration der Schleife die berücksichtigt nächste rechtes Bit.
Der Ausdruck n & (n-1) kann verwendet werden, um das am weitesten rechts gesetzte Bit einer Zahl auszuschalten n. Dies funktioniert als Ausdruck n-1 dreht alle Bits nach dem am weitesten rechts gesetzten Bit um n, einschließlich des ganz rechts gesetzten Bits selbst. Deswegen, n & (n-1) führt dazu, dass das letzte Bit umgedreht wird n.
Betrachten Sie zum Beispiel die Nummer 52, die ist 00110100 in binär und hat insgesamt 3 Bits gesetzt.
00110100 & (n)
00110011 (n-1)
~~~~~~~~
00110000
2nd iteration of the loop: n = 48
00110000 & (n)
00101111 (n-1)
~~~~~~~~
00100000
3rd iteration of the loop: n = 32
00100000 & (n)
00011111 (n-1)
~~~~~~~~
00000000 (n = 0)
Der Algorithmus kann wie folgt in C++, Java und Python implementiert werden:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <bitset> using namespace std; // Funktion zum Zählen der Gesamtzahl der gesetzten Bits in `n` int countSetBits(int n) { // `count` speichert die Gesamtzahl der in `n` gesetzten Bits int count = 0; while (n) { n = n & (n - 1); // den niedrigstwertigen Bitsatz löschen count++; } return count; } int main() { int n = -1; cout << n << " in binary is " << bitset<32>(n) << endl; cout << "The total number of set bits in " << n << " is " << countSetBits(n) << endl; return 0; } |
Ergebnis:
-1 in binary is 11111111111111111111111111111111
The total number of set bits in -1 is 32
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Main { // Funktion zum Zählen der Gesamtzahl der gesetzten Bits in `n` public static int countSetBits(int n) { // `count` speichert die Gesamtzahl der in `n` gesetzten Bits int count = 0; while (n != 0) { n = n & (n - 1); // den niedrigstwertigen Bitsatz löschen count++; } return count; } public static void main(String[] args) { int n = -1; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); System.out.println("The total number of set bits in " + n + " is " + countSetBits(n)); } } |
Ergebnis:
-1 in binary is 11111111111111111111111111111111
The total number of set bits in -1 is 32
Der Algorithmus von Brian Kernighan durchläuft so viele Iterationen, wie es gesetzte Bits gibt. Wenn wir also ein 32-Bit-Wort haben, bei dem nur das High-Bit gesetzt ist, wird es die Schleife nur einmal durchlaufen.
3. Verwenden der integrierten GCC-Funktion
GCC bietet auch eine eingebaute Funktion int __builtin_popcount (unsigned int n) die die Gesamtzahl der gesetzten Bits in zurückgibt n. Das folgende C++-Programm demonstriert es:
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { int n = 16; cout << "The total number of set bits in " << n << " is " << __builtin_popcount (n) << endl; return 0; } |
Ergebnis:
The total number of set bits in 16 is 1
GCC bietet außerdem zwei weitere integrierte Funktionen, int __builtin_popcountl (unsigned long) und int __builtin_popcountll (unsigned long long), ähnlich zu __builtin_popcount, außer dass ihr Argumenttyp ist unsigned long und unsigned long long, beziehungsweise.
4. Verwenden std::bitset::count Funktion
Können wir auch verwenden std::bitset::count die die Gesamtzahl der gesetzten Bits in a zurückgibt bitset. Diese Methode wird im Folgenden demonstriert:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> #include <bitset> using namespace std; int main() { int n = 30; bitset<8> bs(n); cout << "The total number of set bits in " << n << " (" << bs << ") is " << bs.count() << endl; return 0; } |
Ergebnis:
The total number of set bits in 30 (00011110) is 4
Verweise: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan