Contar Bits Definidos em um Inteiro em C

Introdução

Neste laboratório, você aprenderá a contar o número de bits definidos (1's) em um inteiro usando operações bit a bit na programação C. O laboratório consiste em três etapas: ler uma entrada inteira, usar operações bit a bit para contar os bits definidos e imprimir a contagem. Ao final deste laboratório, você terá uma compreensão melhor dos conceitos de teoria dos números e matemática discreta, e como aplicá-los na programação C.

O laboratório começa demonstrando como ler uma entrada inteira do usuário, que é a primeira etapa do exercício de contagem de bits. Em seguida, apresenta uma função que usa operações bit a bit para contar o número de bits definidos no inteiro fornecido. Finalmente, o programa exibe a contagem de bits definidos para o usuário.

Ler um Inteiro

Nesta etapa, você aprenderá como ler uma entrada inteira em programação C para contar bits definidos. Criaremos um programa simples que demonstra a entrada de inteiros.

Primeiro, vamos criar um arquivo de origem C para nosso programa de contagem de bits:

cd ~/project
nano bit_counter.c

Agora, adicione o seguinte código ao arquivo:

#include <stdio.h>

int main() {
    int number;

    // Solicita ao usuário para inserir um inteiro
    printf("Digite um inteiro: ");

    // Lê a entrada inteira
    scanf("%d", &number);

    // Exibe o número inserido
    printf("Você digitou: %d\n", number);

    return 0;
}

Vamos compilar e executar o programa:

gcc bit_counter.c -o bit_counter
./bit_counter

Saída de exemplo:

Digite um inteiro: 42
Você digitou: 42

Explicação do código:

• #include <stdio.h> inclui a biblioteca de entrada/saída padrão
• scanf("%d", &number) lê uma entrada inteira do usuário
• printf() é usado para exibir solicitações e o número inserido
• %d é o especificador de formato para inteiros

Este programa simples demonstra como ler uma entrada inteira, que é a primeira etapa em nosso exercício de contagem de bits definidos.

Usar Operações Bit a Bit para Contar Uns

Nesta etapa, você aprenderá a contar o número de bits definidos (1's) em um inteiro usando operações bit a bit em C.

Vamos modificar o arquivo anterior bit_counter.c para implementar a contagem de bits:

cd ~/project
nano bit_counter.c

Substitua o conteúdo anterior pelo seguinte código:

#include <stdio.h>

// Função para contar bits definidos usando a operação AND bit a bit
int countSetBits(int number) {
    int count = 0;

    while (number) {
        // Verifica o bit menos significativo
        count += number & 1;

        // Desloca o número para a direita
        number >>= 1;
    }

    return count;
}

int main() {
    int number;

    // Solicita ao usuário para inserir um inteiro
    printf("Digite um inteiro: ");
    scanf("%d", &number);

    // Conta e exibe o número de bits definidos
    int setBitCount = countSetBits(number);
    printf("Número de bits definidos em %d: %d\n", number, setBitCount);

    return 0;
}

Compile e execute o programa:

gcc bit_counter.c -o bit_counter
./bit_counter

Saída de exemplo:

Digite um inteiro: 42
Número de bits definidos em 42: 3

Explicação do código:

• A função countSetBits() usa operações bit a bit para contar bits definidos
• number & 1 verifica o bit menos significativo (retorna 1 se o bit estiver definido, 0 caso contrário)
• number >>= 1 desloca o número para a direita, movendo para o próximo bit
• O loop continua até que todos os bits sejam verificados

Decomposição da operação bit a bit:

• 42 em binário é 101010
• Posições dos bits: 1 0 1 0 1 0
• Contagem de bits definidos: 3

Este método conta eficientemente o número de 1's em um inteiro usando passos computacionais mínimos.

Imprimir a Contagem

Nesta etapa final, vamos aprimorar nosso programa de contagem de bits para fornecer uma saída mais detalhada e demonstrar diferentes maneiras de imprimir a contagem de bits definidos.

Vamos modificar o arquivo bit_counter.c para adicionar impressão mais abrangente:

cd ~/project
nano bit_counter.c

Atualize o código com a seguinte implementação:

#include <stdio.h>

// Função para contar bits definidos usando a operação AND bit a bit
int countSetBits(int number) {
    int count = 0;

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

    return count;
}

int main() {
    int number;

    // Solicita ao usuário para inserir um inteiro
    printf("Digite um inteiro: ");
    scanf("%d", &number);

    // Conta o número de bits definidos
    int setBitCount = countSetBits(number);

    // Imprime a contagem em múltiplos formatos
    printf("Número Decimal: %d\n", number);
    printf("Representação Binária: ");

    // Imprime a representação binária
    for (int i = 31; i >= 0; i--) {
        int bit = (number >> i) & 1;
        printf("%d", bit);
    }
    printf("\n");

    // Imprime os resultados da contagem de bits definidos
    printf("Número de Bits Definidos: %d\n", setBitCount);
    printf("Porcentagem de Bits Definidos: %.2f%%\n",
           (float)setBitCount / 32 * 100);

    return 0;
}

Compile e execute o programa:

gcc bit_counter.c -o bit_counter
./bit_counter

Saída de exemplo:

Digite um inteiro: 42
Número Decimal: 42
Representação Binária: 00000000000000000000000000101010
Número de Bits Definidos: 3
Porcentagem de Bits Definidos: 9.38%

Explicação do código:

• Adicionada a impressão da representação binária
• Incluída o cálculo da porcentagem de bits definidos
• Usadas operações bit a bit para extrair bits individuais
• Saída formatada para fornecer múltiplas perspectivas sobre a contagem de bits

O programa agora oferece uma visão abrangente da composição de bits do inteiro, mostrando:

• Valor decimal
• Representação binária completa de 32 bits
• Número total de bits definidos
• Porcentagem de bits definidos

Resumo

Neste laboratório, você aprendeu inicialmente como ler uma entrada de inteiro em programação C. Isso envolveu o uso da função scanf() para capturar a entrada do usuário e a função printf() para exibir o número inserido. Em seguida, você implementou uma função chamada countSetBits() que utiliza operações bit a bit para contar o número de bits definidos (1's) no inteiro fornecido. Esta função itera pelos bits do número, verificando o bit menos significativo usando a operação AND bit a bit e, em seguida, deslocando o número para a direita para mover para o próximo bit. A contagem de bits definidos é acumulada e retornada.