Generadores basados en desplazamientos de bits

01 · Punto de partida

Adiós multiplicación, hola bits

Los LCG viven de a·x + c y un mod caro. En 2003 Marsaglia mostró otra vía: solo XOR y desplazamientos (<<, >>), las operaciones más baratas de la CPU. Tres líneas, sin multiplicar ni dividir, período 2³²−1 y velocidad endemoniada.

La idea es vieja (registros LFSR de hardware) pero el envase es nuevo: el xorshift32. Entenderlo te abre la puerta a todos los modernos (xoshiro, PCG usa parte de esto).

• ¿Qué hacen ^, << y >> a los bits?
• ¿Por qué tres xorshifts encadenados mezclan y uno solo no?
• ¿Por qué la semilla 0 es letal aquí también?
• ¿Por qué en Python hay que enmascarar con 0xFFFFFFFF?

02 · Definición

XOR, shifts y el trío mágico

03 · Trampa de Python

Enmascarar o morir (en la portabilidad)

En C, uint32_t trunca solo a 32 bits. En Python los enteros son infinitos: x << 13 crece sin cortar y tu secuencia deja de ser xorshift32. La solución es enmascarar tras cada paso:

Máscara

x &= 0xFFFFFFFF tras cada XOR-shift: simula el desborde de 32 bits.

Cero

Si x == 0, el siguiente es 0: validá semilla ≠ 0 al sembrar.

Salida

u = x / 2**32 en [0,1). Nunca x % m con otro m sin pensar (Tema 22).

04 · Ejemplos

Un bit cambia todo

1. 1
   Semilla 12345.

   Cascada de bits que en 3 pasos ya es irreconocible: difusión total.

2. 2
   Semilla 12346 (un bit más).

   Historia totalmente distinta desde el primer valor: sensibilidad extrema.

3. 3
   Semilla 0.

   0^0 = 0 tres veces: secuencia muerta. Validar ≠ 0 es obligatorio.

05 · Implementación en Python

Xorshift32 fiel a C

MASK = 0xFFFFFFFF

def xorshift32(semilla, n=6):
    assert semilla != 0, "semilla 0 prohibida"
    x = semilla & MASK
    sal = []
    for _ in range(n):
        x ^= (x << 13) & MASK
        x &= MASK
        x ^= x >> 17
        x ^= (x << 5) & MASK
        x &= MASK
        sal.append(x / 2**32)
    return sal


print([round(v, 6) for v in xorshift32(12345)])

Seis uniformes irreconocibles desde 12345. Con 12346 sale otra historia desde el valor 1.

El cero mata

def paso(x):
    x ^= (x << 13) & 0xFFFFFFFF
    x &= 0xFFFFFFFF
    x ^= x >> 17
    x ^= (x << 5) & 0xFFFFFFFF
    return x & 0xFFFFFFFF


print(paso(0))

06 · Exploración

Laboratorio: bits que mezclan

Elegí variante y semilla (incluido 0 para ver la muerte). La curva es u(n); el panel muestra los primeros valores, distintos y alerta de cero. Compará xorshift con el LCG didáctico.

Línea plana en cero = semilla prohibida. Todo lo demás debe cubrir sin ciclos visibles en esta ventana.

Preguntas para explorar

1. Poné semilla 0 en xorshift: ¿qué sale? ¿Y en LCG mixto con semilla 0?
2. Cambiá de 12345 a 12346 en xorshift: ¿se parecen las historias? ¿Qué dice de la difusión?
3. Si olvidaras la máscara en Python, ¿seguiría dando en [0,1)? ¿Sería el mismo generador?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: un paso a mano

Partiendo de x = 1, aplicá los 3 xorshifts con máscara y verificá que da 270369.

x = 1
x ^= (x << 13) & 0xFFFFFFFF
x &= 0xFFFFFFFF
x ^= x >> 17
x ^= (x << 5) & 0xFFFFFFFF
x &= 0xFFFFFFFF
print(x)

Ejercicio 2: el cero

Demostrá que el 0 es punto fijo absorbente para cualquier trío.

def paso(x, a=13, b=17, c=5):
    x ^= (x << a) & 0xFFFFFFFF
    x &= 0xFFFFFFFF
    x ^= x >> b
    x ^= (x << c) & 0xFFFFFFFF
    return x & 0xFFFFFFFF


print(paso(0))

Ejercicio 3: sensibilidad

Compará las primeras 5 salidas desde 12345 y 12346. ¿Cuántas coinciden?

def xs(s, n=5):
    x = s
    sal = []
    for _ in range(n):
        x ^= (x << 13) & 0xFFFFFFFF
        x &= 0xFFFFFFFF
        x ^= x >> 17
        x ^= (x << 5) & 0xFFFFFFFF
        x &= 0xFFFFFFFF
        sal.append(round(x / 2**32, 6))
    return sal


print(xs(12345))
print(xs(12346))

09 · Síntesis

Ideas para recordar

En el próximo tema veremos el estado del arte: generadores modernos (Mersenne Twister, PCG, xoshiro, Philox).