Trucos para contar bits en C

Trucos de bits clásicos con & y resta.

int popcount(unsigned n) {
    int count = 0;
    while (n) {
        n &= n - 1;  /* apaga el bit encendido más bajo */
        count++;
    }
    return count;
}

int is_power_of_two(unsigned n) {
    return n != 0 && (n & (n - 1)) == 0;
}

Cómo funciona

1. n &= n - 1 apaga el bit encendido más bajo en cada pasada.
2. Contar las pasadas da el conteo de bits encendidos.
3. La misma identidad detecta potencias de dos.

Palabras clave y builtins usados aquí

• int
• return
• unsigned
• while

El intento, en números

Líneas

12

Caracteres a escribir

205

Tokens

62

Ritmo de tres estrellas

100 tpm

Al ritmo de tres estrellas de 100 tokens por minuto, este intento toma unos 37 segundos.

Escribe este fragmento

Paso 2 de 2 en Manipulación de bits; paso 18 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →