Desafio C

Contar bits e inverter nibbles

Enunciado

Leia um inteiro sem sinal de 32 bits. Conte quantos bits estão ligados (popcount) sem usar funções de biblioteca. Em seguida, inverta a ordem dos quatro nibbles (grupos de 4 bits) e imprima o resultado em hexadecimal. Por fim, imprima o popcount do valor invertido.

Requisitos

  • Implementar count_bits com laço e x &= x - 1.
  • Inverter nibbles usando shifts e máscaras.
  • Imprimir os três valores: popcount original, valor invertido em hex, popcount invertido.

Código inicial

#include <stdio.h>

int count_bits(unsigned int x) {
    // implemente
}

unsigned int reverse_nibbles(unsigned int x) {
    // implemente
}

int main(void) {
    unsigned int num;
    scanf("%u", &num);
    // use as funções e imprima
    return 0;
}

Saída esperada

popcount original = 4
valor invertido = 0x1B
popcount invertido = 4
Ver dica

Para inverter nibbles, extraia cada nibble com (x >> shift) & 0xF e reposicione com << no lugar certo.

Mostrar solução 
#include <stdio.h>

// Conta bits ligados sem funções de biblioteca
int count_bits(unsigned int x) {
    int count = 0;
    while (x) {
        x &= x - 1;  // remove o bit 1 mais baixo
        count++;
    }
    return count;
}

// Inverte a ordem dos quatro nibbles de um inteiro de 32 bits
unsigned int reverse_nibbles(unsigned int x) {
    unsigned int result = 0;
    for (int i = 0; i < 4; i++) {
        unsigned int nibble = (x >> (i * 4)) & 0xF;  // extrai nibble i
        result |= nibble << ((3 - i) * 4);            // coloca na posição invertida
    }
    return result;
}

int main(void) {
    unsigned int num;
    scanf("%u", &num);

    int pc_orig = count_bits(num);
    unsigned int rev = reverse_nibbles(num);
    int pc_rev = count_bits(rev);

    printf("popcount original = %d\n", pc_orig);
    printf("valor invertido = 0x%X\n", rev);
    printf("popcount invertido = %d\n", pc_rev);
    return 0;
}

Passo a passo

  1. count_bits usa o truque x &= x - 1, que apaga o bit 1 mais baixo. O laço executa exatamente o número de bits ligados.
  2. reverse_nibbles percorre os quatro nibbles (i = 0 a 3).
  3. Para cada nibble, (x >> (i * 4)) & 0xF isola os 4 bits na posição i (0 = menos significativo).
  4. Em seguida, nibble << ((3 - i) * 4) move esse nibble para a posição invertida (nibble 0 vai para a posição 3, etc.).
  5. O resultado é acumulado com |=.
  6. No main, lemos o número, calculamos o popcount original, invertemos os nibbles, calculamos o popcount do invertido e imprimimos.

Por que funciona

A inversão de nibbles é uma permutação de grupos de 4 bits. Usando shifts e máscaras, extraímos cada grupo e o reposicionamos. O popcount com x &= x - 1 é eficiente porque cada iteração elimina um bit 1, independentemente de onde ele esteja. Juntas, essas técnicas mostram como manipular bits diretamente sem depender de funções prontas.

Erros comuns

  • Usar x >> (i * 4) sem máscara: isso traz bits indesejados dos nibbles superiores. O correto é & 0xF.
  • Confundir a ordem dos nibbles: o nibble 0 (bits 0-3) deve ir para a posição 3 (bits 12-15). Verifique com um exemplo pequeno.
  • Em count_bits, usar x >>= 1 em vez de x &= x - 1: funciona, mas é menos eficiente e não demonstra o truque.

Outra forma de resolver

Pode-se inverter nibbles com uma tabela de lookup de 16 entradas, pré-calculando a inversão de cada nibble. Para 4 nibbles, a tabela é pequena e o código fica mais rápido, porém mais verboso.

Saída esperada

popcount original = 4
valor invertido = 0x1B
popcount invertido = 4