Zählen der gesetzten Bits in einer Ganzzahl in C

Einführung

In diesem Lab werden Sie lernen, wie Sie die Anzahl der gesetzten Bits (1en) in einer Ganzzahl mithilfe von Bitoperationen in der Programmiersprache C zählen. Das Lab besteht aus drei Schritten: Einlesen einer Ganzzahl-Eingabe, Verwenden von Bitoperationen zum Zählen der gesetzten Bits und Ausgeben der Anzahl. Am Ende dieses Labs werden Sie die Konzepte der Zahlentheorie und der diskreten Mathematik besser verstehen und wissen, wie Sie sie in der C-Programmierung anwenden können.

Das Lab beginnt mit der Demonstration, wie man eine Ganzzahl-Eingabe vom Benutzer einliest, was der erste Schritt in der Übung zum Zählen der Bits ist. Anschließend wird eine Funktion eingeführt, die Bitoperationen verwendet, um die Anzahl der gesetzten Bits in der gegebenen Ganzzahl zu zählen. Schließlich zeigt das Programm die Anzahl der gesetzten Bits dem Benutzer an.

Einlesen einer Ganzzahl

In diesem Schritt werden Sie lernen, wie Sie in der C-Programmierung eine Ganzzahl-Eingabe zum Zählen der gesetzten Bits einlesen. Wir werden ein einfaches Programm erstellen, das die Eingabe einer Ganzzahl demonstriert.

Zunächst erstellen wir eine C-Quelldatei für unser Programm zum Zählen der Bits:

cd ~/project
nano bit_counter.c

Fügen Sie jetzt den folgenden Code zur Datei hinzu:

#include <stdio.h>

int main() {
    int number;

    // Prompt the user to enter an integer
    printf("Enter an integer: ");

    // Read the integer input
    scanf("%d", &number);

    // Display the entered number
    printf("You entered: %d\n", number);

    return 0;
}

Kompilieren und führen wir das Programm aus:

gcc bit_counter.c -o bit_counter
./bit_counter

Beispielausgabe:

Enter an integer: 42
You entered: 42

Code-Erklärung:

• #include <stdio.h> inkludiert die Standard-Eingabe/Ausgabe-Bibliothek
• scanf("%d", &number) liest eine Ganzzahl-Eingabe vom Benutzer ein
• printf() wird verwendet, um Hinweise und die eingegebene Zahl anzuzeigen
• %d ist der Format-Spezifizierer für Ganzzahlen

Dieses einfache Programm demonstriert, wie man eine Ganzzahl-Eingabe einliest, was der erste Schritt in unserer Übung zum Zählen der gesetzten Bits ist.

Verwendung von Bitoperationen zum Zählen der Einsen

In diesem Schritt werden Sie lernen, wie Sie die Anzahl der gesetzten Bits (1en) in einer Ganzzahl mithilfe von Bitoperationen in C zählen.

Ändern wir die vorherige bit_counter.c-Datei, um das Zählen der Bits zu implementieren:

cd ~/project
nano bit_counter.c

Ersetzen Sie den vorherigen Inhalt durch den folgenden Code:

#include <stdio.h>

// Function to count set bits using bitwise AND operation
int countSetBits(int number) {
    int count = 0;

    while (number) {
        // Check the least significant bit
        count += number & 1;

        // Right shift the number
        number >>= 1;
    }

    return count;
}

int main() {
    int number;

    // Prompt the user to enter an integer
    printf("Enter an integer: ");
    scanf("%d", &number);

    // Count and display the number of set bits
    int setBitCount = countSetBits(number);
    printf("Number of set bits in %d: %d\n", number, setBitCount);

    return 0;
}

Kompilieren und führen Sie das Programm aus:

gcc bit_counter.c -o bit_counter
./bit_counter

Beispielausgabe:

Enter an integer: 42
Number of set bits in 42: 3

Code-Erklärung:

• Die Funktion countSetBits() verwendet Bitoperationen, um die gesetzten Bits zu zählen
• number & 1 überprüft das least significant bit (gibt 1 zurück, wenn das Bit gesetzt ist, sonst 0)
• number >>= 1 verschiebt die Zahl um eine Stelle nach rechts und geht zum nächsten Bit über
• Die Schleife wird fortgesetzt, bis alle Bits überprüft wurden

Zerlegung der Bitoperationen:

• 42 in Binärdarstellung ist 101010
• Bit-Positionen: 1 0 1 0 1 0
• Anzahl der gesetzten Bits: 3

Diese Methode zählt effizient die Anzahl der 1en in einer Ganzzahl mit minimalen Rechenschritten.

Ausgabe der Anzahl

In diesem letzten Schritt verbessern wir unser Programm zum Zählen der Bits, um detailliertere Ausgaben zu liefern und verschiedene Methoden zur Ausgabe der Anzahl der gesetzten Bits zu demonstrieren.

Ändern wir die bit_counter.c-Datei, um umfassendere Ausgaben hinzuzufügen:

cd ~/project
nano bit_counter.c

Aktualisieren Sie den Code mit der folgenden Implementierung:

#include <stdio.h>

// Function to count set bits using bitwise AND operation
int countSetBits(int number) {
    int count = 0;

    while (number) {
        count += number & 1;
        number >>= 1;
    }

    return count;
}

int main() {
    int number;

    // Prompt the user to enter an integer
    printf("Enter an integer: ");
    scanf("%d", &number);

    // Count the number of set bits
    int setBitCount = countSetBits(number);

    // Print the count in multiple formats
    printf("Decimal Number: %d\n", number);
    printf("Binary Representation: ");

    // Print binary representation
    for (int i = 31; i >= 0; i--) {
        int bit = (number >> i) & 1;
        printf("%d", bit);
    }
    printf("\n");

    // Print set bit count results
    printf("Number of Set Bits: %d\n", setBitCount);
    printf("Set Bit Percentage: %.2f%%\n",
           (float)setBitCount / 32 * 100);

    return 0;
}

Kompilieren und führen Sie das Programm aus:

gcc bit_counter.c -o bit_counter
./bit_counter

Beispielausgabe:

Enter an integer: 42
Decimal Number: 42
Binary Representation: 00000000000000000000000000101010
Number of Set Bits: 3
Set Bit Percentage: 9.38%

Code-Erklärung:

• Hinzugefügt: Ausgabe der Binärdarstellung
• Eingeschlossen: Berechnung des Prozentsatzes der gesetzten Bits
• Verwendung von Bitoperationen zum Extrahieren einzelner Bits
• Formatierte Ausgabe, um verschiedene Perspektiven auf die Anzahl der Bits zu bieten

Das Programm bietet jetzt einen umfassenden Überblick über die Bit-Zusammensetzung der Ganzzahl und zeigt:

• Dezimalwert
• Vollständige 32-Bit-Binärdarstellung
• Gesamtanzahl der gesetzten Bits
• Prozentsatz der gesetzten Bits

Zusammenfassung

In diesem Lab haben Sie zunächst gelernt, wie man in der C-Programmierung eine Ganzzahl-Eingabe einliest. Dies beinhaltete die Verwendung der Funktion scanf(), um die Benutzereingabe zu erfassen, und der Funktion printf(), um die eingegebene Zahl anzuzeigen. Anschließend haben Sie eine Funktion namens countSetBits() implementiert, die Bitoperationen verwendet, um die Anzahl der gesetzten Bits (1en) in der gegebenen Ganzzahl zu zählen. Diese Funktion iteriert durch die Bits der Zahl, überprüft das least significant bit mithilfe der bitweisen AND-Operation und verschiebt dann die Zahl um eine Stelle nach rechts, um zum nächsten Bit zu gelangen. Die Anzahl der gesetzten Bits wird aufsummiert und zurückgegeben.