Count Set Bits in an Integer in C

Introduction

In this lab, you will learn how to count the number of set bits (1's) in an integer using bitwise operations in C programming. The lab consists of three steps: reading an integer input, using bitwise operations to count the set bits, and printing the count. By the end of this lab, you will have a better understanding of number theory and discrete math concepts, and how to apply them in C programming.

The lab starts by demonstrating how to read an integer input from the user, which is the first step in the bit counting exercise. Then, it introduces a function that uses bitwise operations to count the number of set bits in the given integer. Finally, the program displays the count of set bits to the user.

Skills Graph

Read an Integer

In this step, you will learn how to read an integer input in C programming for counting set bits. We'll create a simple program that demonstrates integer input.

First, let's create a C source file for our bit counting program:

cd ~/project
nano bit_counter.c

Now, add the following code to the file:

#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;
}

Let's compile and run the program:

gcc bit_counter.c -o bit_counter
./bit_counter

Example output:

Enter an integer: 42
You entered: 42

Code Explanation:

• #include <stdio.h> includes the standard input/output library
• scanf("%d", &number) reads an integer input from the user
• printf() is used to display prompts and the entered number
• %d is the format specifier for integers

This simple program demonstrates how to read an integer input, which is the first step in our set bit counting exercise.

Use Bitwise Operations to Count Ones

In this step, you will learn how to count the number of set bits (1's) in an integer using bitwise operations in C.

Let's modify the previous bit_counter.c file to implement bit counting:

cd ~/project
nano bit_counter.c

Replace the previous content with the following 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;
}

Compile and run the program:

gcc bit_counter.c -o bit_counter
./bit_counter

Example output:

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

Code Explanation:

• countSetBits() function uses bitwise operations to count set bits
• number & 1 checks the least significant bit (returns 1 if bit is set, 0 otherwise)
• number >>= 1 right shifts the number, moving to the next bit
• The loop continues until all bits are checked

Bitwise Operation Breakdown:

• 42 in binary is 101010
• Bit positions: 1 0 1 0 1 0
• Set bits count: 3

This method efficiently counts the number of 1's in an integer using minimal computational steps.

Print the Count

In this final step, we'll enhance our bit counting program to provide more detailed output and demonstrate different ways of printing the set bit count.

Let's modify the bit_counter.c file to add more comprehensive printing:

cd ~/project
nano bit_counter.c

Update the code with the following implementation:

#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;
}

Compile and run the program:

gcc bit_counter.c -o bit_counter
./bit_counter

Example output:

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

Code Explanation:

• Added binary representation printing
• Included percentage calculation of set bits
• Used bitwise operations to extract individual bits
• Formatted output to provide multiple perspectives on bit count

The program now offers a comprehensive view of the integer's bit composition, showing:

• Decimal value
• Full 32-bit binary representation
• Total number of set bits
• Percentage of set bits

Summary

In this lab, you first learned how to read an integer input in C programming. This involved using the scanf() function to capture user input and the printf() function to display the entered number. Next, you implemented a function called countSetBits() that uses bitwise operations to count the number of set bits (1's) in the given integer. This function iterates through the bits of the number, checking the least significant bit using the bitwise AND operation, and then right-shifting the number to move to the next bit. The count of set bits is accumulated and returned.