CP-UPV Bootcamp - Capítulo 7

Capítulo 7: Manipulación de Bits (Bitwise Operations)

Índice de contenidos

• 1. Representación Binaria y Operadores a Nivel de Bit
• 2. Operaciones Fundamentales sobre Bits (Bitmasking)
• 3. Trucos de Bits Esenciales en CP
• 4. Representación de Subconjuntos mediante Máscaras de Bits
• 5. Funciones Intrínsecas del Compilador (Builtin Functions)
• Ejemplo Práctico: El Almacén Digital de CP-UPV
• Problemas de práctica

1. Representación Binaria y Operadores a Nivel de Bit

En el nivel más elemental de un procesador, toda la información se almacena en forma de ceros y unos (bits). La manipulación directa de bits (o bitwise operations) nos permite ejecutar operaciones lógicas y aritméticas ultraeficientes en tiempo constante $O(1)$ sin consumo adicional de memoria.

Un entero sin signo de $32$ bits puede representar números desde $0$ hasta $2^{32}-1$. El bit situado más a la derecha se denomina Bit Menos Significativo (LSB - Least Significant Bit) y corresponde a $2^0$, mientras que el de la izquierda es el Bit Más Significativo (MSB - Most Significant Bit).

Los 6 Operadores de Bit Fundamentales

• AND (&): Devuelve $1$ si y solo si ambos bits son 1.
• OR (|): Devuelve $1$ si al menos uno de los bits es 1.
• XOR (^ - OR Exclusivo): Devuelve $1$ si los bits son diferentes ($1 \text{ y } 0$). Propiedad clave: $X \mathbin{\hat{}} X = 0$ y $X \mathbin{\hat{}} 0 = X$.
• NOT (~): Invierte todos los bits ($0 \to 1$ y $1 \to 0$).
• Desplazamiento a la Izquierda (<<): Desplaza los bits $k$ posiciones a la izquierda, equivalente a multiplicar por $2^k$.
• Desplazamiento a la Derecha (>>): Desplaza los bits $k$ posiciones a la derecha, equivalente a dividir entre $2^k$ (división entera).

int a = 5;  // 0101 en binario
int b = 3;  // 0011 en binario

int res_and = a & b;   // 0001 -> 1
int res_or  = a | b;   // 0111 -> 7
int res_xor = a ^ b;   // 0110 -> 6
int res_not = ~a;      // Invasión de bits (complemento a dos)
int shift_l = a << 2;  // 010100 -> 20 (5 * 2^2)
int shift_r = a >> 1;  // 0010 -> 2   (5 / 2^1)

a = 5  # 0101 en binario
b = 3  # 0011 en binario

res_and = a & b   # 0001 -> 1
res_or  = a | b   # 0111 -> 7
res_xor = a ^ b   # 0110 -> 6
res_not = ~a      # Complemento en Python
shift_l = a << 2  # 20 (5 * 2^2)
shift_r = a >> 1  # 2  (5 // 2^1)

int a = 5;  // 0101 en binario
int b = 3;  // 0011 en binario

int resAnd = a & b;   // 0001 -> 1
int resOr  = a | b;   // 0111 -> 7
int resXor = a ^ b;   // 0110 -> 6
int resNot = ~a;      // Complemento a dos
int shiftL = a << 2;  // 20 (5 * 2^2)
int shiftR = a >> 1;  // 2  (5 / 2^1)

2. Operaciones Fundamentales sobre Bits (Bitmasking)

Trataremos un entero como si fuera una lista de interruptores o booleanos. Para consultar, encender, apagar o alternar el $k$-ésimo bit (indexado desde $0$ a la derecha), utilizamos la máscara de bit de un solo bit definida como (1 << k).

3. Trucos de Bits Esenciales en CP

Existen varias identidades algebraicas de bits de uso habitual en programación competitiva:

• Comprobar si un número es par o impar: (x & 1) == 0 es par, (x & 1) != 0 es impar.
• Comprobar si $X$ es una potencia de 2: x > 0 && (x & (x - 1)) == 0. Un número potencia de $2$ tiene exactamente un único bit encendido (ej. $1000_2$). Al restarle $1$, todos los bits inferiores pasan a $1$ ($0111_2$), resultando un AND igual a cero.
• Aislar el LSB encendido de $X$: lsb = x & (-x). Gracias a la representación en complemento a dos, esta expresión extrae una máscara con únicamente el bit activo más bajo de $X$.
• Apagar el LSB encendido de $X$: x = x & (x - 1). Elimina el bit activo de menor peso. Es la base del algoritmo de Brian Kernighan para contar bits encendidos.

4. Representación de Subconjuntos mediante Máscaras de Bits

Uno de los usos más habituales del bitmasking en CP es representar un subconjunto de un conjunto finito de $N$ elementos utilizando un único entero de $N$ bits.

Si tenemos $N$ elementos, existen $2^N$ subconjuntos posibles. Podemos iterar fácilmente por todos los subconjuntos haciendo un bucle de $0$ a $2^N - 1$ (es decir, de 0 a (1 << N) - 1):

int n = 3; // Elementos: {0, 1, 2}

// Iterar por los 2^N subconjuntos posibles:
for (int mask = 0; mask < (1 << n); ++mask) {
    cout << "Subconjunto " << mask << ": { ";
    for (int i = 0; i < n; ++i) {
        if (mask & (1 << i)) { // Si el i-ésimo elemento está presente
            cout << i << " ";
        }
    }
    std::cout << "}\n";
}

n = 3 # Elementos: {0, 1, 2}

# Iterar por los 2^N subconjuntos posibles:
for mask in range(1 << n):
    elementos = [i for i in range(n) if (mask & (1 << i))]
    print(f"Subconjunto {mask}: {elementos}")

int n = 3; // Elementos: {0, 1, 2}

for (int mask = 0; mask < (1 << n); mask++) {
    System.out.print("Subconjunto " + mask + ": { ");
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            System.out.print(i + " ");
        }
    }
    System.out.println("}");
}

5. Funciones Intrínsecas del Compilador (Builtin Functions)

Los procesadores modernos disponen de instrucciones de ensamblador dedicadas a operaciones sobre bits. C++, Java y Python exponen funciones optimizadas para usarlas directamente:

Ejemplo Práctico: El entrenamiento en Algomania

Danimania ha publicado $N$ problemas en la plataforma Algomania ($1 \le N \le 20$). Cada problema $i$ tiene una dificultad estimada de $d_i$ puntos.

Un estudiante del bootcamp dispone de una capacidad total de esfuerzo de $K$ puntos para su sesión de entrenamiento. Queremos seleccionar el subconjunto de problemas que maximice la suma total de dificultades sin superar el límite $K$.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<long long> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }

    long long mejor_suma = 0;

    // Recorremos las 2^N máscaras de bits posibles
    for (int mask = 0; mask < (1 << n); mask++) {
        long long suma_actual = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                suma_actual += d[i];
            }
        }

        if (suma_actual <= k) {
            mejor_suma = max(mejor_suma, suma_actual);
        }
    }

    cout << mejor_suma << "\n";

    return 0;
}

import sys
from itertools import combinations

def resolver():
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    n = int(entrada[0])
    k = int(entrada[1])
    dificultades = [int(x) for x in entrada[2:n + 2]]

    mejor_suma = 0

    # Usamos itertools para iterar por todos los subconjuntos eficientemente en CPython
    for r in range(n + 1):
        for combo in combinations(dificultades, r):
            suma_actual = sum(combo)
            if mejor_suma < suma_actual <= k:
                mejor_suma = suma_actual
                if mejor_suma == k:
                    print(k)
                    return

    print(mejor_suma)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;

        String linea = lector.readLine();
        if (linea == null) return;
        tokens = new StringTokenizer(linea);

        int n = Integer.parseInt(tokens.nextToken());
        long k = Long.parseLong(tokens.nextToken());

        long[] dificultades = new long[n];
        tokens = new StringTokenizer(lector.readLine());
        for (int i = 0; i < n; i++) {
            dificultades[i] = Long.parseLong(tokens.nextToken());
        }

        long mejorSuma = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            long sumaActual = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sumaActual += dificultades[i];
                }
            }

            if (sumaActual <= k) {
                mejorSuma = Math.max(mejorSuma, sumaActual);
            }
        }

        PrintWriter escritor = new PrintWriter(System.out);
        escritor.println(mejorSuma);
        escritor.flush();
    }
}

Problemas de práctica

Ponte a prueba completando los problemas asignados en la sección activa de nuestro bootcamp en Codeforces.