Saltar al contenido

Trucos con XOR

Lección 2 de 5 · 4 min

Trucos con XOR

Paso 1 de 7

XOR pliega toda una lista en un solo acumulador. Empieza en cero; el primer valor es 4.

La idea

XOR tiene dos propiedades que hacen todo el trabajo: x ^ x es 0, y x ^ 0 es x. Además, no le importa el orden.

Así que aplica XOR a toda una lista y cada valor que aparece dos veces se borra solo. Lo que sobrevive apareció un número impar de veces, en tiempo O(n) y memoria O(1).

Ejemplo del mundo real

RAID 5 guarda un disco de paridad que es el XOR de los demás. Si pierdes cualquier disco, su contenido se reconstruye aplicando XOR a todo lo que queda: el bloque que falta es el valor que ya no tiene pareja.

El código

Te toca

Completa el espacio en blanco.

def single_number(nums):
  acc = 0
  for x in nums:
      acc = acc ___ x
  return acc

print(single_number([9, 5, 9]))   # want 5

Mini quiz

1 / 3

¿Cuánto es `x ^ x`?