Подсчет установленных битов в целом числе на языке C

Введение

В этом лабораторном занятии (LabEx) вы научитесь подсчитывать количество установленных битов (единиц) в целом числе с использованием побитовых операций в языке программирования C. Лабораторное занятие состоит из трех этапов: чтение целочисленного ввода, использование побитовых операций для подсчета установленных битов и вывод подсчитанного количества. По завершении этого лабораторного занятия вы лучше поймете концепции теории чисел и дискретной математики, а также узнаете, как применять их в программировании на языке C.

Лабораторное занятие начинается с демонстрации того, как прочитать целочисленный ввод от пользователя, что является первым этапом упражнения по подсчету битов. Затем вводится функция, которая использует побитовые операции для подсчета количества установленных битов в заданном целом числе. Наконец, программа отображает пользователю подсчитанное количество установленных битов.

Skills Graph

Чтение целого числа

На этом этапе вы научитесь считывать целочисленный ввод в программировании на языке C для подсчета установленных битов. Мы создадим простую программу, которая демонстрирует ввод целого числа.

Сначала создадим файл исходного кода на языке C для нашей программы по подсчету битов:

cd ~/project
nano bit_counter.c

Теперь добавьте следующий код в файл:

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

Скомпилируем и запустим программу:

gcc bit_counter.c -o bit_counter
./bit_counter

Пример вывода:

Enter an integer: 42
You entered: 42

Пояснение к коду:

• #include <stdio.h> подключает стандартную библиотеку ввода-вывода
• scanf("%d", &number) считывает целочисленный ввод от пользователя
• printf() используется для вывода подсказок и введенного числа
• %d - спецификатор формата для целых чисел

Эта простая программа демонстрирует, как считывать целочисленный ввод, что является первым этапом нашего упражнения по подсчету установленных битов.

Использование побитовых операций для подсчета единиц

На этом этапе вы научитесь подсчитывать количество установленных битов (единиц) в целом числе с использованием побитовых операций в языке C.

Изменим предыдущий файл bit_counter.c, чтобы реализовать подсчет битов:

cd ~/project
nano bit_counter.c

Замените предыдущее содержимое следующим кодом:

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

Скомпилируйте и запустите программу:

gcc bit_counter.c -o bit_counter
./bit_counter

Пример вывода:

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

Пояснение к коду:

• Функция countSetBits() использует побитовые операции для подсчета установленных битов
• number & 1 проверяет младший бит (возвращает 1, если бит установлен, и 0 в противном случае)
• number >>= 1 сдвигает число вправо, переходя к следующему биту
• Цикл продолжается до тех пор, пока все биты не будут проверены

Разбор побитовых операций:

• 42 в двоичной системе - 101010
• Позиции битов: 1 0 1 0 1 0
• Количество установленных битов: 3

Этот метод эффективно подсчитывает количество единиц в целом числе с использованием минимального количества вычислительных шагов.

Вывод подсчитанного количества

На этом последнем этапе мы улучшим нашу программу по подсчету битов, чтобы получить более детальный вывод и продемонстрировать различные способы вывода количества установленных битов.

Изменим файл bit_counter.c, чтобы добавить более полный вывод:

cd ~/project
nano bit_counter.c

Обновите код следующей реализацией:

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

Скомпилируйте и запустите программу:

gcc bit_counter.c -o bit_counter
./bit_counter

Пример вывода:

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

Пояснение к коду:

• Добавлен вывод двоичного представления
• Включен подсчет процента установленных битов
• Использованы побитовые операции для извлечения отдельных битов
• Отформатирован вывод для предоставления нескольких аспектов подсчета битов

Теперь программа предоставляет полное представление о битовом составе целого числа, показывая:

• Десятичное значение
• Полное 32-битное двоичное представление
• Общее количество установленных битов
• Процент установленных битов

Резюме

В этом лабораторном занятии (LabEx) вы сначала научились считывать целочисленный ввод в программировании на языке C. Это включало использование функции scanf() для получения ввода от пользователя и функции printf() для вывода введенного числа. Затем вы реализовали функцию countSetBits(), которая использует побитовые операции для подсчета количества установленных битов (единиц) в заданном целом числе. Эта функция проходит по битам числа, проверяя младший бит с помощью побитовой операции И (AND), а затем сдвигает число вправо, переходя к следующему биту. Количество установленных битов накапливается и возвращается.