Manipulación de bits

Número binario

Un número binario es un número expresado en el sistema de numeración en base 2 o sistema de numeración binario; es un método de expresión matemática que usa solo dos símbolos: típicamente “0” (cero) y “1” (uno).

Decimos que un bit está set (activado) si vale uno, y cleared (apagado) si vale cero.

El número binario $(a_k a_{k-1} \dots a_1 a_0)_2$ representa el número:

$$(a_k a_{k-1} \dots a_1 a_0)$$2 = a_k \cdot 2^k + a{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0.

Por ejemplo, el número binario $1101_2$ representa el número $13$:

$$\begin{array}{rllll}& {\displaystyle {1101}_2}& {\displaystyle =1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0}& & \\ & {\displaystyle }& {\displaystyle =1\cdot 8+1\cdot 4+0\cdot 2+1\cdot 1=13}& & \end{array}$$$$\begin{align} 1101_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \ &= 1\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13 \end{align}$$

Las computadoras representan los enteros como números binarios. Los enteros positivos (tanto con signo como sin signo) se representan simplemente con sus dígitos binarios, y los números negativos con signo (los números con signo pueden ser positivos y negativos) suelen representarse con el complemento a dos .

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);
 
int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);
 
int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

Las CPUs son muy rápidas manipulando esos bits con operaciones específicas. En algunos problemas podemos aprovechar estas representaciones de números binarios y acelerar el tiempo de ejecución. Y en algunos problemas (típicamente de combinatoria o programación dinámica) en los que queremos llevar registro de qué objetos ya tomamos de un conjunto dado, podemos usar un entero lo suficientemente grande donde cada dígito representa un objeto y, según si tomamos o descartamos el objeto, activamos (set) o apagamos (clear) el dígito.

Operadores de bits

Todos los operadores que se presentan a continuación son instantáneos (misma velocidad que una suma) en una CPU para enteros de longitud fija.

Operadores bit a bit

• $&$ : El operador AND bit a bit compara cada bit de su primer operando con el bit correspondiente de su segundo operando. Si ambos bits son 1, el bit correspondiente del resultado se pone a 1. En caso contrario, el bit correspondiente del resultado se pone a 0.

• $|$ : El operador OR inclusivo bit a bit compara cada bit de su primer operando con el bit correspondiente de su segundo operando. Si alguno de los dos bits es 1, el bit correspondiente del resultado se pone a 1. En caso contrario, el bit correspondiente del resultado se pone a 0.

• $\wedge$ : El operador OR exclusivo (XOR) bit a bit compara cada bit de su primer operando con el bit correspondiente de su segundo operando. Si un bit es 0 y el otro es 1, el bit correspondiente del resultado se pone a 1. En caso contrario, el bit correspondiente del resultado se pone a 0.

• $\sim$ : El operador complemento bit a bit (NOT) invierte (flip) cada bit de un número: si un bit está activado (set) el operador lo apaga (clear), y si está apagado el operador lo activa.

Ejemplos:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

Operadores de desplazamiento

Hay dos operadores para desplazar bits.

• $\gg$ Desplaza un número hacia la derecha eliminando los últimos dígitos binarios del número. Cada desplazamiento de uno representa una división entera por 2, así que un desplazamiento a la derecha de $k$ representa una división entera por $2^k$.

  P. ej. $5 \gg 2 = 101_2 \gg 2 = 1_2 = 1$, que es lo mismo que $\frac{5}{2^2} = \frac{5}{4} = 1$. Para una computadora, sin embargo, desplazar bits es mucho más rápido que hacer divisiones.

• $\ll$ Desplaza un número hacia la izquierda añadiendo dígitos cero. De forma análoga a un desplazamiento a la derecha de $k$, un desplazamiento a la izquierda de $k$ representa una multiplicación por $2^k$.

  P. ej. $5 \ll 3 = 101_2 \ll 3 = 101000_2 = 40$, que es lo mismo que $5 \cdot 2^3 = 5 \cdot 8 = 40$.

  Nótese, sin embargo, que para un entero de longitud fija esto implica descartar los dígitos más a la izquierda, y si se desplaza demasiado se termina con el número $0$.

Trucos útiles

Activar (set) / invertir (flip) / apagar (clear) un bit

Con desplazamientos de bits y algunas operaciones bit a bit básicas podemos activar (set), invertir (flip) o apagar (clear) un bit fácilmente. $1 \ll x$ es un número con solo el $x$-ésimo bit activado, mientras que $\sim(1 \ll x)$ es un número con todos los bits activados excepto el $x$-ésimo.

• $n | (1 \ll x)$ activa (set) el $x$-ésimo bit del número $n$
• $n \wedge (1 \ll x)$ invierte (flip) el $x$-ésimo bit del número $n$
• $n & \sim(1 \ll x)$ apaga (clear) el $x$-ésimo bit del número $n$

Comprobar si un bit está activado

El valor del $x$-ésimo bit se puede comprobar desplazando el número $x$ posiciones a la derecha, de modo que el $x$-ésimo bit quede en la posición de las unidades, tras lo cual lo extraemos haciendo un & bit a bit con 1.

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

Comprobar si el número es divisible por una potencia de 2

Usando la operación AND, podemos comprobar si un número $n$ es par porque $n & 1 = 0$ si $n$ es par, y $n & 1 = 1$ si $n$ es impar. Más en general, $n$ es divisible por $2^{k}$ exactamente cuando $n & (2^{k} − 1) = 0$.

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

Podemos calcular $2^{k}$ desplazando 1 hacia la izquierda $k$ posiciones. El truco funciona porque $2^k - 1$ es un número que consiste exactamente de $k$ unos. Y un número divisible por $2^k$ debe tener dígitos cero en esas posiciones.

Comprobar si un entero es una potencia de 2

Una potencia de dos es un número que tiene un solo bit activado (p. ej. $32 = 00100000_2$), mientras que el predecesor de ese número no tiene ese dígito activado y sí todos los dígitos posteriores ($31 = 00011111_2$). Así, el AND bit a bit de un número con su predecesor siempre será 0, porque no tienen ningún dígito activado en común. Se puede comprobar fácilmente que esto solo ocurre para las potencias de dos y para el número $0$, que ya no tiene ningún dígito activado.

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

Apagar el bit activado más a la derecha (clear the right-most set bit)

La expresión $n & (n-1)$ se puede usar para apagar el bit activado más a la derecha de un número $n$. Esto funciona porque la expresión $n-1$ invierte todos los bits posteriores al bit activado más a la derecha de $n$, incluyendo el propio bit activado más a la derecha. Así, todos esos dígitos son distintos de los del número original, y al hacer un AND bit a bit todos quedan en 0, lo que da el número original $n$ con el bit activado más a la derecha invertido.

Por ejemplo, consideremos el número $52 = 0011~0100_2$:

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

Algoritmo de Brian Kernighan

Podemos contar la cantidad de bits activados con la expresión anterior.

La idea es considerar solo los bits activados de un entero apagando su bit activado más a la derecha (después de contarlo), de modo que la siguiente iteración del bucle considere el siguiente bit activado más a la derecha.

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

Contar bits activados hasta $n$

Para contar la cantidad de bits activados de todos los números hasta el número $n$ (inclusive), podemos ejecutar el algoritmo de Brian Kernighan sobre todos los números hasta $n$. Pero esto provocará un “Time Limit Exceeded” (límite de tiempo excedido) en los envíos de un contest.

Podemos usar el hecho de que para números hasta $2^x$ (es decir, de $1$ a $2^x - 1$) hay $x \cdot 2^{x-1}$ bits activados. Esto se puede visualizar así.

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

Podemos ver que todas las columnas excepto la más a la izquierda tienen $4$ (es decir, $2^2$) bits activados cada una; es decir, hasta el número $2^3 - 1$, la cantidad de bits activados es $3 \cdot 2^{3-1}$.

Con este conocimiento nuevo podemos plantear el siguiente algoritmo:

• Encontrar el mayor $x$ tal que $2^x$ sea menor o igual que el número dado.
• Calcular la cantidad de bits activados de $1$ a $2^x - 1$ usando la fórmula $x \cdot 2^{x-1}$.
• Contar la cantidad de bits activados en el bit más significativo desde $2^x$ hasta $n$ y sumarla.
• Restar $2^x$ de $n$ y repetir los pasos anteriores con el nuevo $n$.

int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            int x = std::bit_width(n) - 1;
            count += x << (x - 1);
            n -= 1 << x;
            count += n + 1;
        }
        return count;
}

Trucos adicionales

• $n & (n + 1)$ apaga todos los unos finales (trailing ones): $00110111_2 \rightarrow 00110000_2$.
• $n | (n + 1)$ activa el último bit apagado (cleared): $00110101_2 \rightarrow 00110111_2$.
• $n & -n$ extrae el último bit activado (set): $00110100_2 \rightarrow 00000100_2$.

Se pueden encontrar muchos más en el libro Hacker’s Delight .

Soporte del lenguaje y del compilador

C++ soporta algunas de esas operaciones desde C++20 a través de la biblioteca estándar bit :

• has_single_bit: comprueba si el número es una potencia de dos
• bit_ceil / bit_floor: redondea hacia arriba/abajo a la siguiente potencia de dos
• rotl / rotr: rota los bits del número
• countl_zero / countr_zero / countl_one / countr_one: cuenta los ceros/unos a la izquierda/derecha (leading/trailing)
• popcount: cuenta la cantidad de bits activados

Además, hay funciones predefinidas en algunos compiladores que ayudan a trabajar con bits. P. ej. GCC define una lista en Built-in Functions Provided by GCC  que también funcionan en versiones anteriores de C++:

• __builtin_popcount(unsigned int) devuelve la cantidad de bits activados (__builtin_popcount(0b0001'0010'1100) == 4)
• __builtin_ffs(int) encuentra el índice del primer bit activado (el más a la derecha) (__builtin_ffs(0b0001'0010'1100) == 3)
• __builtin_clz(unsigned int) la cantidad de ceros a la izquierda (leading zeros) (__builtin_clz(0b0001'0010'1100) == 23)
• __builtin_ctz(unsigned int) la cantidad de ceros a la derecha (trailing zeros) (__builtin_ctz(0b0001'0010'1100) == 2)
• __builtin_parity(x) la paridad (par o impar) de la cantidad de unos en la representación de bits

Nótese que algunas de las operaciones (tanto las funciones de C++20 como las Built-in del compilador) pueden ser bastante lentas en GCC si no se habilita un target específico del compilador con #pragma GCC target("popcnt").

Problemas de práctica

• Codeforces - Raising Bacteria 
• Codeforces - Fedor and New Game 
• Codeforces - And Then There Were K