XOR

• XOR es una operación que da 1 cuando dos bits son distintos entre sí, y puede entenderse conectando en una sola idea el OR exclusivo, la desigualdad, la inversión condicional y la suma/resta módulo 2
• El XOR bit a bit sobre enteros procesa cada posición de forma independiente y revela la diferencia por bit, funcionando como una suma binaria sin acarreo mientras conserva las propiedades conmutativa, asociativa, el elemento identidad 0 y el inverso de sí mismo
• En criptografía se usa para combinar texto plano con un keystream, y en los gráficos por píxeles del pasado permitía borrar redibujando la misma figura, reduciendo la carga de memoria y CPU
• Las propiedades de XOR se aprovechan directamente en cálculos que crean diferencias y luego las cancelan, como la identidad del half adder, el intercambio de bits, el swap con tres XOR y la condición ganadora del juego Nim
• Se extiende a la diferencia simétrica de conjuntos, los grupos de exponente 2, el nim-sum y hasta el álgebra lineal y los polinomios sobre GF(2), conectándose también con técnicas de detección/corrección de errores y criptografía como Hamming code, CRC, AES, GCM y Classic McEliece

---

Significado básico de XOR

• XOR es una operación booleana con dos bits de entrada y un bit de salida, y su tabla de verdad es 00→0, 01→1, 10→1, 11→0
• Visto como “exclusive OR”, da 1 cuando solo una de las dos entradas es verdadera, y 0 cuando ambas lo son
• Visto como “not equals”, a XOR b es igual a a ≠ b, así que produce 1 cuando los dos valores booleanos son distintos
• Visto como inversión condicional, cuando a=0 deja b tal como está, y cuando a=1 invierte b
  • Por la misma razón, también puede interpretarse viendo b como entrada de control e invirtiendo a
• Desde la perspectiva de la paridad, indica si la cantidad de unos en la entrada es impar
  • Con dos bits, es igual a a+b mod 2
  • También es igual a a-b mod 2
  • Si se hace XOR de varios valores, se puede saber si la cantidad total de unos en la entrada es impar o par

Propiedades algebraicas de XOR

• XOR satisface las propiedades conmutativa y asociativa
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • En una lista larga de XOR, ni el orden ni la forma de agrupar cambian el resultado
• 0 es el elemento identidad de XOR
  • a XOR 0 = 0 XOR a = a
  • En una lista larga de XOR, se pueden eliminar los 0
• Todo valor es su propio inverso
  • a XOR a = 0
  • Si la misma variable aparece dos veces, ambos términos pueden eliminarse juntos
  • En un valor ya mezclado, como (a XOR b) XOR b = a, se puede eliminar un término conocido aplicando XOR una vez más

XOR bit a bit sobre enteros

• El XOR bit a bit de enteros toma dos enteros en binario y aplica XOR de forma independiente a cada posición
• Las propiedades del XOR de un solo bit se aplican igual a los enteros
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • a XOR 0 = a
  • a XOR a = 0
• El XOR bit a bit muestra la diferencia por bit entre dos enteros
  • Si a=b, entonces a XOR b = 0
  • Si a≠b, al menos un bit difiere, así que a XOR b ≠ 0
  • Los bits en 1 del resultado indican las posiciones en que las dos entradas son distintas
• El XOR bit a bit también puede verse como un inversor condicional de bits
  • Solo invierte los bits de datos en las posiciones donde el valor de control tiene bits en 1
  • En ASCII y algunas codificaciones derivadas, las letras latinas mayúsculas y minúsculas difieren en un solo bit, por lo que hacer XOR con 32 sobre el valor del carácter puede cambiar entre mayúsculas y minúsculas
  • Esta regla no se aplica a todos los caracteres Unicode, y muchos no tienen distinción entre mayúsculas y minúsculas o no siguen esa regla
• El XOR bit a bit es equivalente a una suma binaria sin acarreo
  • En cada posición solo se hace una suma módulo 2, sin propagar acarreo a la posición siguiente

XOR en criptografía

• En criptografía, se usa un método que genera un keystream del mismo largo que el texto plano, y produce el texto cifrado combinando los bytes o palabras del texto plano con ese keystream
• En esa etapa de combinación se usa normalmente XOR
  • El receptor puede recuperar el texto plano original aplicando XOR otra vez con el mismo keystream
  • También resulta un poco más conveniente que emisor y receptor usen la misma operación
• La forma de generar el keystream puede ser más compleja
  • El one-time pad usa datos verdaderamente aleatorios del tamaño completo del mensaje y es irrompible, pero para la mayoría de los fines es muy poco práctico
  • Lo habitual es que un cifrador de flujo o un cifrador de bloque operando en counter mode genere un keystream del largo necesario a partir de una clave pequeña
• Este método puede proporcionar confidencialidad cuando el keystream es bueno, pero no proporciona integridad para detectar manipulación del mensaje
  • La protección de integridad es un problema aparte
  • Omitir la integridad es un error común en el diseño de sistemas criptográficos principiantes, y también causa resultados incorrectos en esquemas más complejos
• En hardware, XOR es más simple que la suma
  • La suma necesita propagar el acarreo entre bits, lo que consume más espacio en el chip y más tiempo
  • Como XOR no tiene acarreo, es más barato en circuitos dedicados

Dibujo con XOR y gráficos por píxeles

• En las computadoras domésticas de los años 1980, la cantidad de bits por píxel y la RAM eran limitadas, por lo que era difícil guardar dos copias completas de la pantalla
• Si un objeto en movimiento se dibuja con XOR, basta con dibujar el mismo objeto otra vez para restaurar la pantalla original
  • Se hace XOR entre el valor del píxel S y el píxel M del objeto móvil para obtener C, y luego se vuelve a aplicar XOR con el mismo M para recuperar S
• En pantallas donde varios píxeles van packed dentro de un byte o se usa una estructura de bit planes, la composición basada en suma se vuelve complicada
  • La suma normal puede hacer que el acarreo de un píxel pase al siguiente
  • XOR no tiene ningún acarreo, así que evita ese problema
• Si se dibujan líneas con XOR, los píxeles donde se cruzan dos líneas se invierten dos veces y vuelven al color de fondo, por lo que pueden verse como una pequeña imperfección
  • Esa imperfección se aceptaba a cambio de poder borrar una línea sin dañar la otra
• El dibujo con XOR también favorecía las animaciones simples
  • Dibujar una línea nueva y volver a dibujar una línea vieja para borrarla producía el siguiente cuadro
  • No era necesario redibujar todos los píxeles ni todas las líneas de la pantalla actual, así que el uso de memoria y CPU era bajo
  • Este método se usó en la línea móvil del juego Qix de 1981 y en los contornos de movimiento de ventanas en interfaces gráficas tempranas

Identidad del half adder

• En la suma de un bit, el bit bajo de a+b es a XOR b y el bit alto es a AND b
• La misma relación también vale para las operaciones bit a bit sobre enteros
  • a + b = (a XOR b) + 2 × (a AND b)
  • a XOR b es el valor sumado sin acarreo, y a AND b contiene los bits de acarreo que debían producirse en cada posición
• Esta relación puede verse como la identidad del half adder
  • Un half adder de hardware usa compuertas AND y XOR para generar el acarreo y el bit bajo de una suma de dos bits
  • No significa que la suma completa de enteros se construya solo con operaciones simples; el + del lado derecho es el que termina la propagación de acarreos
• Esta identidad puede usarse para calcular el promedio de dos enteros sin overflow
  • Si simplemente se hace a+b y luego un shift a la derecha, se puede perder el bit más alto de una suma de 33 bits
  • En CPUs donde no existe o no resulta conveniente una carry flag o instrucciones como RRX/RCR, una forma como (a XOR b) >> 1 + (a AND b) puede ser una alternativa
  • Ejemplos: MIPS, RISC-V y DEC Alpha no tienen carry flag, y Arm Thumb temprano no incluía RRX
• En CPUs sin instrucción XOR, esta identidad puede invertirse para construir XOR
  • a XOR b = (a + b) − 2 × (a AND b)
  • Las CPUs de Data General de los años 1970 tenían AND, pero no XOR bit a bit

Intercambio de bits y valores

• El problema de intercambiar dos bits se reduce a que, si los dos bits son iguales, no hay que hacer nada, y si son distintos, basta con invertir ambos bits
• Con XOR y shifts se puede detectar si dos bits difieren y, si hace falta, invertir ambas posiciones
  • diff_all = input XOR (input >> distance) calcula la diferencia entre pares de bits separados por una distancia fija
  • Con AND se seleccionan solo las posiciones de interés
  • Luego esa diferencia seleccionada se replica en la otra posición y se aplica XOR sobre la entrada para invertir ambas solo cuando haga falta
• El mismo método también puede usarse para intercambiar al mismo tiempo varios pares de bits separados por la misma distancia
  • En vez de una máscara de un solo bit, se usa una máscara con varios bits
  • Una Beneš network puede representar una permutación arbitraria intercambiando muchos pares a la misma distancia a lo largo de varias etapas
• También es posible hacer el swap con tres XOR de dos valores completos
  • a = a XOR b
  • b = b XOR a
  • a = a XOR b
  • Así, los dos valores quedan intercambiados sin usar una variable temporal
• El swap con tres XOR tiene un problema de aliasing
  • Funciona cuando se intercambian variables distintas
  • Si dos nombres apuntan a la misma ubicación de memoria, como al intercambiar un elemento de un arreglo consigo mismo, el valor puede convertirse en 0

El juego Nim y XOR

• Nim es un juego en el que, por turnos, se elige un montón entre varios y se retiran una o más fichas, en la cantidad que se quiera, y pierde quien ya no puede mover
• En la versión simple de Nim, una posición perdedora es aquella donde el XOR bit a bit de los tamaños de todos los montones da 0
• Si en una posición con XOR 0 se cambia el tamaño de un montón de a a otro valor b, el XOR total cambia en a XOR b, y como a≠b, deja de ser 0
• En una posición donde el XOR no es 0, se observa el bit más alto en 1 del valor total x, y si se elige un montón que tenga ese bit en 1 y se reduce su tamaño a pile XOR x, el XOR total puede llevarse a 0
• Por ejemplo, los tamaños 12, 10 y 3 en binario son 1100, 1010 y 0011, y su XOR es 0101
  • Solo el montón grande 12 se reduce a 9 al aplicarle XOR con 0101
  • La jugada ganadora consiste en quitar 3 fichas del 12 para dejarlo en 9

Estructuras matemáticas que se parecen a XOR

• En teoría de conjuntos, la diferencia simétrica X∆Y es la operación que incluye un elemento cuando pertenece exactamente a uno de los dos conjuntos
  • Si la pertenencia de un elemento se ve como un valor booleano, la diferencia simétrica es igual a XOR
  • Por eso comparte propiedades de XOR como la conmutatividad y la asociatividad
• En teoría de grupos, un grupo de exponente 2 es un grupo en el que todo elemento es su propio inverso
  • La operación de estos grupos satisface la asociatividad y, como ejercicio estándar, también se deduce la conmutatividad
  • El hecho de que dos elementos iguales juntos se cancelen recuerda a XOR
  • Todo grupo de exponente 2 puede entenderse como una forma de XOR bit a bit sobre ciertas funciones con valores en {0,1}
• En el análisis de Sprague-Grundy, a muchas posiciones de impartial game se les asigna un número de Grundy
  • El número de Grundy de un composite formado por varios subjuegos se calcula haciendo XOR bit a bit de los números de Grundy de cada juego componente
  • En teoría de juegos, al XOR bit a bit de enteros no negativos también se le llama nim-sum
• El cuerpo GF(2) es un cuerpo finito con solo los elementos 0 y 1
  • La suma y la resta funcionan como XOR
  • La multiplicación funciona como AND
  • Por eso se cumple a AND (b XOR c) = (a AND b) XOR (a AND c)

Álgebra lineal sobre GF(2) y corrección de errores

• Los vectores y matrices sobre GF(2) son estructuras cuyas componentes son 0 o 1, y la suma de vectores o matrices es XOR componente por componente
• Multiplicar una matriz M por un vector v equivale a combinar con XOR las columnas de M seleccionadas por las componentes en 1 de v
• Los códigos de corrección de errores expanden un mensaje de m bits en una palabra de código más larga de n bits para poder detectar o corregir algunos errores de bits
  • Si las palabras de código válidas difieren entre sí en muchos bits, una pequeña cantidad de errores no las convierte en otra palabra válida distinta
  • Si dos palabras válidas difieren al menos en k bits, menos de k errores pueden detectarse, y menos de k/2 errores pueden corregirse buscando la palabra válida más cercana
• Los códigos lineales usan una generator matrix y una check matrix sobre GF(2)
  • El sender expande el mensaje de m bits a una palabra de código de n bits usando la generator matrix
  • El receiver verifica con la check matrix si la palabra recibida es válida y, si hay error, obtiene un syndrome
  • El mismo patrón de error genera el mismo syndrome sin importar el mensaje
• El Hamming code es un ejemplo cuando la longitud del código n es 2^d−1
  • Si n=15, las posiciones de los 15 bits se numeran con números binarios no cero de 4 bits, de 0001 a 1111
  • El receptor hace XOR de todos los índices de los bits en 1, y si el resultado es 0, la palabra de código es válida
  • Si un bit se invierte, el resultado del XOR pasa a ser exactamente el índice del bit invertido, lo que permite corregir un error de 1 bit sin tabla de búsqueda
  • El Hamming code de 15 bits almacena 11 bits de datos y usa 4 bits para corrección de errores

Polinomios sobre GF(2), CRC y cuerpos finitos más grandes

• Los polinomios sobre GF(2) son polinomios formales cuyos coeficientes son 0 o 1, y sumarlos equivale a hacer XOR entre coeficientes del mismo grado
• La multiplicación de polinomios se hace como en los polinomios normales, formando productos parciales y reduciendo los coeficientes módulo 2
  • Si esta representación se ve como una secuencia de bits, se parece a la multiplicación de enteros, pero al combinar los productos parciales se usa XOR sin acarreo en lugar de suma normal
  • x86 ofrece instrucciones de multiplicación sin acarreo, incluido CLMUL, y Arm ofrece instrucciones de la familia de multiplicación polinomial
• El CRC usa como checksum el residuo de una división de polinomios sobre GF(2)
  • La secuencia de bits del mensaje enviado se ve como un gran polinomio M, y se conserva el residuo M mod P al dividirlo por un polinomio acordado P
  • Se usa para verificar paquetes de red como los de Ethernet y tecnologías similares
  • El CRC no corrige errores, solo los detecta, y está pensado para situaciones donde casi todas las transmisiones son correctas y solo ocasionalmente aparecen bits volteados o ruido
• Los cuerpos finitos más grandes pueden construirse como la estructura de residuos al dividir polinomios sobre GF(p) por un irreducible polynomial Q
  • Si el grado de Q es d, el nuevo cuerpo finito tiene p^d elementos
  • Cuando p=2, el irreducible polynomial puede escribirse como un patrón de bits parecido a un entero, y esa secuencia aparece en OEIS A014580
• Los cuerpos finitos de tamaño potencia de 2 aparecen en varias técnicas criptográficas
  • El cuerpo finito de tamaño 2^8 es un componente central de AES y Twofish
  • El cuerpo finito de tamaño 2^128 se usa en GCM, que combina bulk encryption con protección de integridad
  • Los cuerpos finitos de tamaño potencia de 2 también aparecen en algunas formas de elliptic-curve cryptography y en el algoritmo de decodificación del esquema post-cuántico Classic McEliece

[GN⁺]

Opiniones de Hacker News

• Mi técnica maldita favorita con XOR es la lista doblemente enlazada XOR: https://en.m.wikipedia.org/wiki/XOR_linked_list
  En vez de que cada nodo guarde por separado los punteros al siguiente/anterior, guarda un único valor que es el XOR de ambos. Obviamente es un puntero no válido, pero al recorrer la lista, si haces XOR entre el puntero al nodo anterior y el puntero combinado, obtienes el puntero al siguiente nodo, y también se puede recorrer en ambos sentidos. Se siente como algo ilegal.

  • Frente a una lista doblemente enlazada normal, pierdes la capacidad de eliminar ese elemento cuando solo tienes la dirección del elemento o un iterador estable ante inserciones/eliminaciones. Y muchas veces esa es la razón principal para usar una lista doblemente enlazada.
    Un defecto menos esencial es que escribir una lista enlazada XOR en C estrictamente conforme al estándar es muy molesto. El estándar no garantiza que, al castear el mismo puntero a un entero, se obtenga el mismo entero, así que en la práctica hay que hacer que todo sea uintptr_t para mantener una versión normalizada casteada a entero.
  • Incluso en procesadores de 64 bits, si suponemos que a la mayoría de las apps les basta con menos de 4 GB de RAM, se puede reducir aún más el almacenamiento usando solo un espacio de direcciones de 32 bits.
    Yendo más allá, quizá también sean posibles punteros cercanos/relativos de 16 bits. Podría encajar bien con el diseño orientado a datos: por ejemplo, tener bloques de 64K elementos y apuntar a los elementos internos con índices uint16.
  • Esto haría que el recolector de basura lo odiara. O, como mínimo, probablemente consideraría esta estructura de datos como basura.
  • Me da curiosidad por qué alguien querría usar esta técnica.
  • Esto no es muy distinto de guardar la diferencia entre dos punteros, más que un puntero en sí. Si guardas la diferencia, por supuesto también puedes recorrer en ambos sentidos.

• Falta algo. XOR también es una función hash lineal 3-wise independiente, así que se puede usar para muestreo casi uniforme probabilístico de soluciones de funciones booleanas y para conteo. Es realmente útil, y se usa para crear contadores que dan conteos probabilísticos pero demostrados. Dejé una explicación más fácil de entender aquí: https://www.msoos.org/2018/12/how-approximate-model-counting...
  Básicamente, cada vez reduce el espacio de soluciones casi exactamente a la mitad. Entonces se siguen agregando condiciones XOR hasta que, por ejemplo, quedan 10 soluciones; si la cantidad de XOR agregados es k, basta con multiplicar 10 por 2^k. Como se reduce a la mitad en cada paso, se llega rápido incluso al orden de 10 soluciones, por lo que escala bien.
  Los artículos relacionados están en https://arxiv.org/abs/1306.5726 y https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, y las herramientas están en https://github.com/meelgroup/approxmc y https://github.com/meelgroup/unigen. En la última competencia de conteo de modelos, al combinarlo con un contador exacto, aplastó a los demás competidores; las diapositivas están en https://mccompetition.org/assets/files/2024/MC2024_awards.pd....

• Una de mis anécdotas favoritas sobre XOR es la que contó Bryan Cantrill, de Oxide, Joyent y Sun, en esta presentación https://speakerdeck.com/bcantrill/oral-tradition-in-software... y en este video https://www.youtube.com/watch?v=4PaWFYm0kEw
  Para resumir sin que tengan que abrir el enlace: cuando estaba en Sun, hablaba con su colega Roger Faulkner sobre por qué C no tiene un XOR lógico; Faulkner dijo que era porque no podía tener evaluación de cortocircuito, y a Brian eso le pareció raro. Entonces Roger le preguntó por email a Dennis Ritchie, y Ritchie confirmó que Faulkner tenía razón. La forma en que Cantrill lo cuenta también es graciosa, pero lo sorprendente es que pudieran preguntarle directamente a la persona involucrada.

  • DMR era una persona sorprendentemente amable, dispuesta a ayudar y accesible. A mediados de los 80, cuando era estudiante de grado, leí sobre el “primer” caso de port de Unix v6 a una Interdata 8/32 que no era PDP-11, y envié un email sin más a [e-mail] preguntando si había más información de arquitectura.
    En esa época no había Google y tampoco había material en la biblioteca de la universidad; unos días después me pidió mi dirección física, y unas semanas más tarde llegó a mi buzón una copia de un manual resumido del conjunto de instrucciones. Tenía aire a la familia IBM 360, y todavía lo conservo.
  • C sí tiene XOR lógico: es el operador !=. A diferencia de otros operadores lógicos, hay que normalizar sus argumentos a un único valor verdadero, y encaja bien con el modismo de conversión booleana de C, !!.
  • No entiendo por qué “porque no puede tener evaluación de cortocircuito” sería un obstáculo para agregar un operador. Ojalá alguien lo explique.
  • Ese tema empieza en 37:18.
  • C ha tenido el operador XOR bit a bit ^ durante más de 40 años: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

• Hoy me enteré de que si haces XOR del emoji de auto con 0x20, es decir, si lo “pasas a minúsculas”, se convierte en el emoji de prohibido el paso a peatones. Parece una coincidencia demasiado perfecta, así que me pregunto si alguien sabe si fue intencional.
  Si uno lleva la idea demasiado lejos, hasta se puede pensar algo raro como que la minúscula del emoji de auto es la señal de “prohibido peatones”.

  • Para evitar el procesador de comentarios de HN que elimina emojis, se puede comprobar así:
    >>> from unicodedata import lookup, name
>>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
'NO PEDESTRIANS'
  • La minúscula de un auto debería ser un go-kart.
  • También se puede hacer :tada: → :tophat:, :rocket: → :mountain_cableway:.

• Una buena analogía del mundo real para explicar XOR es el interruptor de luz de una escalera en casa. Hay un interruptor abajo y otro arriba, y ambos controlan la misma luz.
  Al principio los dos están en posición de apagado; si enciendes el interruptor de abajo, la luz se prende. Subes la escalera y enciendes el interruptor de arriba, y aunque ambos interruptores están en posición de “encendido”, la luz se apaga. La luz solo está prendida cuando un interruptor está en “encendido” y el otro en “apagado”; en los demás casos está apagada.

  • Quizá el electricista de nuestra oficina cableó mal. En una sala hay dos interruptores y, pensándolo bien, se comportan más como una compuerta AND que como XOR. Los dos interruptores de la sala sí se comportan claramente como XOR.

• Realmente no me gusta que a esta función lógica se le llame comúnmente XOR, es decir, “OR exclusivo”. Casi siempre lo que en realidad significa es “suma módulo 2”, o sea paridad, no OR exclusivo.
  “Suma módulo 2”/paridad y “OR exclusivo” son funciones lógicas distintas, y solo coinciden por casualidad cuando hay 2 operandos de entrada. Esto se debe a que hay un solo número impar menor o igual que 2.
  Cuando hay 3 o más entradas, lo que la mayoría llama XOR en realidad es paridad: una función que vale 1 cuando una cantidad impar de entradas vale 1. En cambio, el OR exclusivo con 3 o más entradas es una función que solo vale 1 cuando exactamente una entrada vale 1 y todas las demás valen 0.
  En hardware de computadoras, la paridad es mucho más importante que el OR exclusivo. La razón principal es que la suma módulo 2 se usa como bloque de construcción para implementar la suma de números más grandes. En cambio, en matemáticas el OR exclusivo es mucho más importante que la paridad.
  Por ejemplo, los cuantificadores que expresan que un predicado es verdadero para algunos elementos, para todos los elementos o para un único elemento de un conjunto se basan respectivamente en OR, AND y OR exclusivo. El “or” del lenguaje natural siempre significa OR inclusivo u OR exclusivo, no la paridad que muchos programadores llaman XOR.
  En programación es raro tener que calcular la función lógica de OR exclusivo, pero se usa con frecuencia para describir el comportamiento de un programa. Por ejemplo, cuando se dice que en una construcción select/case/switch se ejecuta una de la primera, la segunda o la tercera sentencia, o al describir los tipos que puede tener el valor actual de una variable de unión/tipo suma.

  • El estándar de símbolos electrotécnicos IEC 60617 maneja bien esta parte. Una compuerta XOR se marca como =1, y una compuerta de paridad como 2k + 1. Pero al usar software de diseño de circuitos para PCB o FPGA, todavía puedes terminar recibiendo algo distinto de lo que esperabas.
  • Lo que se mencionó en matemáticas se llama cuantificación de existencia única y tiene su propio símbolo, ∃!.
  • Hace falta sustento para afirmar que, con 3 o más entradas, “OR exclusivo” es verdadero cuando exactamente una sola entrada vale 1.
  • Esta interpretación también se trata en el ensayo principal.

• También está la tabla hash distribuida Kademlia: kademlia distributed hash table. La gran idea es que cada nodo recibe bits aleatorios en el rango [0, 2^m), y la distancia se define con XOR. Se busca un algoritmo distribuido que permita enviar información rápidamente de X a Y sin conocer toda la red.
  Se puede demostrar que funciona solo con las matemáticas, pero mi intuición visual favorita es esta. Supongamos que el nodo inicial X quiere encontrar el nodo k. Definimos el “árbol de distancias desde X” como un árbol binario cuyos índices de hoja son 0, 1, 2..., y a cada hoja le ponemos una etiqueta X^leaf_index para indicar su distancia respecto de X. Por ejemplo, como dist(x, x) = x^x = 0, la etiqueta del nodo original X queda en la hoja 0, la de más a la izquierda.
  El intervalo [2^i, 2^(i+1)) es algún subárbol del árbol de distancias desde X. Si sabemos que la distancia de k cae dentro de ese intervalo, consultamos como vecino aproximado a algún nodo Y dentro de él.
  Elijas el Y que elijas, en el árbol de distancias desde Y el prefijo resultante siempre será alguna permutación del subárbol [2^i, 2^(i+1)) elegido en el árbol de distancias desde X. Más precisamente, puede verse como labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)). Los índices se basan en la distancia, aunque las etiquetas pueden cambiar.
  Hay mucho material bastante más riguroso, tanto matemático como empírico, que compara esto con otras tablas hash distribuidas como Chord. Pero esta intuición visual da una idea de qué es la “simetría” de Kademlia: todos tienen sus propios vecinos locales y su propio subárbol.
  En cambio, Chord, aunque se implemente en ambas direcciones, usa el doble de memoria, parece más riesgoso de implementar y es difícil obtener este nivel de “aislamiento”. Una ventana deslizante de vecinos de tamaño S siempre se está moviendo, y por cada bit existen 2^m vecinos distintos. Aunque la mayoría de los vecinos se parezcan, no queda tan limpio.
  Kademlia tiene 1 + 2 + 4 ... + 2^m-1 vecinos, y todo queda ordenado.

• Para quien tenga curiosidad, esta persona es el Simon Tatham de Simon Tatham's Portable Puzzle Collection. Si no la conoces, vale la pena probarla cuando estés aburrido sin conexión.
  En la secundaria gasté muchísimo tiempo con estos juegos: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • También es el mismo Simon Tatham que creó PuTTY: https://www.chiark.greenend.org.uk/~sgtatham/putty/
  • Lo mejor es que el algoritmo de Buscaminas crea partidas que no requieren adivinar.

• Hoy en día, muchos solucionadores de optimización personalizados, por ejemplo Ising Machine, usan el problema XOR como benchmark. En realidad, resolver varias cláusulas XOR es posible en tiempo polinómico mediante eliminación gaussiana, así que su utilidad es algo limitada, pero como todos los solucionadores muestran escalamiento exponencial, sí sirve como una buena forma de estimar el rendimiento.
  La segunda implementación interesante está relacionada con el criptosistema McEliece. Es un sistema de criptografía de clave pública de los años 70, y últimamente vuelve a llamar la atención por su resistencia cuántica. Un ataque de descifrado consiste en encontrar una solución a un conjunto de ecuaciones XOR; también es de tiempo polinómico, pero con la condición adicional de que la distancia de Hamming debe ser igual a cierto número incluido en la clave pública.

• Cuando aprendía ensamblador Z80 para programar la TI-83, cada byte de código máquina importaba. Eso era porque el almacenamiento total de la calculadora era de apenas 24 KB.
  Para inicializar en 0 el registro acumulador principal a, se usaba XOR a en vez de LD a, 0. En las instrucciones matemáticas, a es el operando automático, así que XOR a hace XOR de a consigo mismo, y la instrucción completa ocupa solo 1 byte. En cambio, para cargar explícitamente 0 en a, el literal 0 tiene que estar incluido en el opcode, por lo que LD a, 0 es una instrucción de 2 bytes.