XOR

• XOR é uma operação que resulta em 1 quando dois bits são diferentes; ela pode ser entendida conectando, em um único comportamento, OR exclusivo, “diferente de”, inversão condicional e soma/subtração mod 2
• O XOR bit a bit sobre inteiros processa cada posição de forma independente, revelando a diferença bit a bit; ele se comporta como uma soma binária sem carry e mantém comutatividade, associatividade, identidade em 0 e a propriedade de cada valor ser seu próprio inverso
• Em criptografia, é usado para combinar texto claro com um keystream; em gráficos de pixels antigos, reduzia o uso de memória e CPU ao apagar uma imagem redesenhando a mesma figura
• As propriedades do XOR são usadas diretamente em cálculos que criam diferenças e depois as cancelam, como a identidade do meio somador, troca de bits, swap com três XORs e a condição de vitória no jogo Nim
• Ele se estende à diferença simétrica de conjuntos, grupos de expoente 2, nim-sum, álgebra linear e polinômios sobre GF(2), conectando-se também a técnicas de detecção/correção de erros e criptografia como códigos de Hamming, CRC, AES, GCM e Classic McEliece

---

O significado básico de XOR

• XOR é uma operação booleana com dois bits de entrada e um bit de saída; sua tabela-verdade é 00→0, 01→1, 10→1, 11→0
• Visto como “exclusive OR”, o resultado é 1 quando apenas uma das duas entradas é verdadeira; se ambas forem verdadeiras, é 0
• Visto como “not equals”, a XOR b é igual a a ≠ b, produzindo 1 quando os dois valores booleanos são diferentes
• Visto como inversão condicional, quando a=0 mantém b como está; quando a=1, inverte b
  • Pelo mesmo motivo, também é possível interpretá-lo tomando b como entrada de controle e invertendo a
• Pela perspectiva de paridade, ele informa se a quantidade de 1s nas entradas é ímpar
  • Para dois bits, é igual a a+b mod 2
  • Também é igual a a-b mod 2
  • Ao aplicar XOR a vários valores, é possível saber se a quantidade total de 1s nas entradas é ímpar ou par

Propriedades algébricas do XOR

• XOR satisfaz as leis comutativa e associativa
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • Em uma longa lista de XORs, a ordem e a forma de agrupamento não afetam o resultado
• 0 é o elemento identidade do XOR
  • a XOR 0 = 0 XOR a = a
  • Em uma longa lista de XORs, zeros podem ser removidos
• Todo valor é seu próprio inverso
  • a XOR a = 0
  • Se a mesma variável aparecer duas vezes, os dois termos podem ser removidos juntos
  • Como em (a XOR b) XOR b = a, é possível remover de um valor já misturado um termo conhecido aplicando XOR com ele mais uma vez

XOR bit a bit em inteiros

• O XOR bit a bit de inteiros coloca dois inteiros em binário e aplica XOR independentemente aos bits de cada posição
• As propriedades do XOR de um único bit se aplicam da mesma forma a inteiros
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • a XOR 0 = a
  • a XOR a = 0
• O XOR bit a bit informa a diferença bit a bit entre dois inteiros
  • Se a=b, então a XOR b = 0
  • Se a≠b, pelo menos um bit é diferente, então a XOR b ≠ 0
  • Os bits 1 no resultado indicam as posições em que as duas entradas diferem
• O XOR bit a bit também pode ser visto como um inversor condicional de bits
  • Ele inverte os bits dos dados apenas nas posições em que o valor de controle tem bit 1
  • Em ASCII e em algumas codificações posteriores, letras latinas maiúsculas e minúsculas diferem por apenas um bit, então aplicar XOR do valor do caractere com 32 pode alternar entre maiúscula e minúscula
  • Essa regra não se aplica a todos os caracteres Unicode, e há muitos caracteres que não têm conceito de maiúscula/minúscula ou não seguem essa regra
• O XOR bit a bit é igual à soma binária sem carry
  • Em cada posição, ele faz apenas a soma mod 2 e não propaga carry para a próxima posição

XOR em criptografia

• Em criptografia, usa-se um método que cria um keystream do mesmo comprimento que o texto claro e o combina com bytes ou words do texto claro para produzir o texto cifrado
• XOR é geralmente usado nessa etapa de combinação
  • O receptor pode recuperar o texto claro original aplicando XOR com o mesmo keystream novamente
  • O fato de remetente e receptor usarem a mesma operação também é um pouco mais conveniente
• A forma de gerar o keystream em si pode ser mais complexa
  • Um one-time pad usa dados verdadeiramente aleatórios do tamanho da mensagem inteira e é inquebrável, mas é muito impraticável para a maioria dos propósitos
  • Em geral, uma cifra de fluxo ou uma cifra de bloco operando em counter mode gera, a partir de uma chave pequena, um keystream do comprimento necessário
• Esse método pode oferecer confidencialidade quando há um bom keystream, mas não oferece integridade para detectar adulteração de mensagens
  • A proteção de integridade é um problema separado
  • Omitir integridade é um erro comum no projeto de sistemas criptográficos por iniciantes, e também leva a resultados incorretos em esquemas de criptografia mais complexos
• Em hardware, XOR é mais simples que adição
  • A adição requer propagação de carry entre bits, o que consome mais área de chip e tempo
  • Como o XOR não tem carry, ele é mais barato em circuitos personalizados

Desenho com XOR e gráficos de pixels

• Computadores domésticos dos anos 1980 tinham limites de bits por pixel na tela e de RAM, tornando difícil armazenar duas cópias da tela inteira
• Ao desenhar um objeto em movimento com XOR, é possível restaurar a tela original apenas desenhando o mesmo objeto novamente
  • Aplica-se XOR entre o valor do pixel S e o pixel M do objeto em movimento para criar C; mais tarde, aplica-se XOR com o mesmo M novamente para recuperar S
• Em telas nas quais vários pixels eram packed em um byte ou que usavam uma estrutura de bit planes, a composição baseada em adição era complicada
  • Na adição comum, o carry de um pixel podia passar para o pixel seguinte
  • XOR não tem carry algum, então esse problema não ocorre
• Ao desenhar linhas com XOR, o pixel em que duas linhas se cruzam é invertido duas vezes e volta à cor de fundo, podendo parecer uma pequena falha
  • Essa falha era aceita como o preço de apagar uma linha sem danificar a outra
• Desenho com XOR também era vantajoso para animações simples
  • Desenha-se uma nova linha e redesenha-se uma linha antiga para apagá-la, formando o próximo frame
  • Não é necessário redesenhar todos os pixels nem todas as linhas da tela atual, reduzindo o uso de memória e CPU
  • Esse método foi usado nas linhas em movimento do jogo Qix, de 1981, e nos contornos de janelas em movimento nas primeiras GUIs

Identidade do meio somador

• Na soma de um bit, o bit baixo de a+b é a XOR b, e o bit alto é a AND b
• A mesma relação vale para operações bit a bit em inteiros
  • a + b = (a XOR b) + 2 × (a AND b)
  • a XOR b é o valor somado sem carry, e a AND b contém os bits de carry que deveriam ter surgido em cada posição
• Essa relação pode ser vista como a identidade do meio somador
  • Um meio somador em hardware usa portas AND e XOR para produzir o carry e o bit baixo da soma de dois bits
  • Isso não constrói uma soma inteira completa apenas com operações simples; o + do lado direito da expressão finaliza a propagação do carry
• Essa identidade pode ser usada para calcular a média de dois inteiros sem overflow
  • Simplesmente fazer a+b e depois shift à direita pode perder o bit mais significativo de uma soma de 33 bits
  • Em CPUs sem carry flag ou sem instruções como RRX/RCR, ou em que elas sejam inconvenientes, a forma (a XOR b) >> 1 + (a AND b) serve como alternativa
  • Por exemplo, MIPS, RISC-V e DEC Alpha não têm carry flag, e o Arm Thumb inicial não incluía RRX
• Em CPUs sem instrução XOR, é possível inverter essa identidade para construir XOR
  • a XOR b = (a + b) − 2 × (a AND b)
  • CPUs Data General dos anos 1970 tinham AND, mas não tinham XOR bit a bit

Troca de bits e valores

• O problema de trocar dois bits se reduz ao seguinte: se os dois bits forem iguais, nada precisa ser feito; se forem diferentes, ambos devem ser invertidos
• Usando XOR e shift, é possível descobrir se dois bits são diferentes e inverter ambas as posições quando necessário
  • diff_all = input XOR (input >> distance) calcula a diferença entre pares de bits separados por uma distância fixa
  • AND seleciona apenas as posições de interesse
  • Depois de replicar a diferença selecionada para a outra posição, aplica-se XOR à entrada para inverter os dois bits somente quando necessário
• O mesmo método também pode ser usado para trocar de uma só vez vários pares de bits separados pela mesma distância
  • Em vez de uma máscara de um bit, usa-se uma máscara contendo vários bits
  • Uma Beneš network pode representar uma permutação arbitrária trocando, em várias etapas, muitos pares com a mesma distância
• Também é possível trocar dois valores inteiros com um swap de três XORs
  • a = a XOR b
  • b = b XOR a
  • a = a XOR b
  • Mesmo sem variável temporária, os dois valores são trocados entre si
• O swap de três XORs tem um problema de aliasing
  • Ele funciona ao trocar variáveis diferentes
  • Se os dois nomes apontarem para a mesma posição de armazenamento, como ao trocar um elemento de array consigo mesmo, o valor pode virar 0

O jogo Nim e XOR

• Nim é um jogo em que, em vários montes, cada jogador escolhe um monte por turno e remove uma ou mais peças, em qualquer quantidade desejada; quem não puder mais jogar perde
• Na versão simples de Nim, uma posição perdedora é aquela em que o XOR bit a bit dos tamanhos de todos os montes é 0
• Se, em uma posição cujo XOR é 0, o tamanho de um monte a for alterado para outro valor b, o XOR total muda em a XOR b; como a≠b, ele deixa de ser 0
• Em uma posição cujo XOR não é 0, observando o bit 1 mais alto do valor total de XOR x, escolhe-se um monte que tenha 1 nesse bit e reduz-se seu tamanho para pile XOR x, tornando o XOR total igual a 0
• Por exemplo, os tamanhos de monte 12, 10 e 3 são, em binário, 1100, 1010 e 0011, e o XOR é 0101
  • Apenas o maior monte, 12, é reduzido para 9 ao aplicar XOR com 0101
  • A jogada vencedora é remover 3 peças de 12, deixando-o em 9

Estruturas matemáticas que se parecem com XOR

• A diferença simétrica X∆Y da teoria dos conjuntos é uma operação que inclui um elemento quando ele pertence a exatamente um dos dois conjuntos
  • Se a pertinência de um elemento for vista como um valor booleano, a diferença simétrica é igual ao XOR
  • Portanto, ela compartilha propriedades do XOR, como comutatividade e associatividade
• Na teoria dos grupos, um grupo de expoente 2 é um grupo em que todo elemento é seu próprio inverso
  • A operação desses grupos satisfaz a associatividade e, como exercício padrão, também se segue a comutatividade
  • O fato de dois elementos iguais se cancelarem juntos se parece com XOR
  • Todo grupo de expoente 2 pode ser entendido como alguma forma de XOR bit a bit de funções com valores em {0,1}
• Na análise de Sprague-Grundy, atribui-se um Grundy number a muitas posições de impartial games
  • O Grundy number de um composite que combina vários subjogos é calculado como o XOR bit a bit dos Grundy numbers de cada jogo componente
  • Em game theory, o XOR bit a bit de inteiros não negativos também é chamado de nim-sum
• O corpo GF(2) é um corpo finito cujos únicos elementos são 0 e 1
  • Adição e subtração se comportam como XOR
  • Multiplicação se comporta como AND
  • Portanto, a AND (b XOR c) = (a AND b) XOR (a AND c) é válido

Álgebra linear sobre GF(2) e correção de erros

• Vetores e matrizes sobre GF(2) são estruturas cujos componentes são 0 ou 1, e a soma de vetores ou matrizes é o XOR componente a componente
• Multiplicar uma matriz M por um vetor v é o mesmo que somar com XOR as colunas de M selecionadas pelos componentes 1 de v
• Códigos de correção de erros expandem uma mensagem de m bits para uma codeword mais longa de n bits, permitindo detectar ou corrigir alguns erros de bit
  • Se codewords válidas diferirem entre si em muitos bits, um pequeno número de erros de bit não a transformará em outra codeword válida
  • Se duas codewords válidas diferem em pelo menos k bits, erros em número menor que k podem ser detectados, e erros em número menor que k/2 podem ser corrigidos encontrando-se a codeword mais próxima
• Códigos lineares usam uma generator matrix e uma check matrix sobre GF(2)
  • O sender usa a generator matrix para expandir a mensagem de m bits em uma codeword de n bits
  • O receiver usa a check matrix para verificar se a codeword recebida é válida e, se houver erro, obter o syndrome
  • O mesmo padrão de erro gera o mesmo syndrome, independentemente da mensagem
• O código de Hamming é um exemplo para comprimentos de código n iguais a 2^d−1
  • Se n=15, as 15 posições de bits são numeradas com números não zero de 4 bits, de 0001 a 1111
  • O receptor aplica XOR a todos os índices dos bits que são 1; se o resultado for 0, a codeword é válida
  • Se um bit for invertido, o resultado do XOR será diretamente o índice do bit invertido, permitindo corrigir um erro de 1 bit sem lookup table
  • Um código de Hamming de 15 bits carrega 11 bits de dados e usa 4 bits para correção de erros

Polinômios em GF(2), CRC e corpos finitos maiores

• Polinômios sobre GF(2) são polinômios formais cujos coeficientes são 0 ou 1, e sua adição equivale a aplicar XOR aos coeficientes de mesmo grau
• A multiplicação de polinômios é feita criando produtos parciais como em polinômios comuns e reduzindo os coeficientes mod 2
  • Vista como uma sequência de bits, essa representação se parece com multiplicação de inteiros, mas usa XOR sem carry em vez de adição comum ao combinar produtos parciais
  • x86 oferece instruções de carryless multiplication, incluindo CLMUL, e Arm oferece instruções da família polynomial multiplication
• CRC é uma técnica que usa o resto da divisão de polinômios sobre GF(2) como checksum
  • A sequência de bits da mensagem enviada é vista como um grande polinômio M, e mantém-se o resto M mod P da divisão pelo polinômio acordado P
  • É usado para verificação de pacotes de rede semelhantes aos de Ethernet
  • CRC não corrige erros, apenas os detecta, sendo adequado a situações em que quase todas as transmissões são corretas e, raramente, ocorrem inversões de bits ou ruído
• Corpos finitos maiores podem ser construídos como a estrutura dos restos de polinômios sobre GF(p) divididos por um irreducible polynomial Q
  • Se o grau de Q for d, o novo corpo finito terá p^d elementos
  • No caso de p=2, o irreducible polynomial pode ser escrito como um padrão de bits na forma de um inteiro, e essa sequência está registrada na OEIS A014580
• Corpos finitos de tamanho potência de 2 aparecem em várias técnicas criptográficas
  • O corpo finito de tamanho 2^8 é um componente central de AES e Twofish
  • O corpo finito de tamanho 2^128 é usado no GCM, que combina bulk encryption e integrity protection
  • Corpos finitos de tamanho potência de 2 também aparecem em algumas técnicas de elliptic-curve cryptography e no algoritmo de decoding do Classic McEliece, um método pós-quântico

[GN⁺]

Comentários do Hacker News

• Minha técnica amaldiçoada favorita com XOR é a lista duplamente encadeada com XOR: https://en.m.wikipedia.org/wiki/XOR_linked_list
  Em vez de cada nó armazenar separadamente os ponteiros para o próximo e o anterior, ele armazena um único valor com o XOR dos dois. Naturalmente, isso é um ponteiro inválido, mas ao percorrer a estrutura, fazer XOR entre o ponteiro do nó anterior e o ponteiro combinado revela o ponteiro do próximo nó, permitindo também a travessia nos dois sentidos. Parece meio ilegal

  • Em comparação com uma lista duplamente encadeada comum, você perde a capacidade de remover um item quando só tem o endereço desse item ou apenas iteradores estáveis mesmo após inserções/remoções. E esse costuma ser justamente um dos principais motivos para usar uma lista duplamente encadeada
    Um defeito menos essencial é que, em C estritamente conforme ao padrão, implementar uma lista encadeada com XOR é extremamente incômodo. O padrão não garante que converter o mesmo ponteiro para inteiro resulte sempre no mesmo inteiro, então, na prática, você acaba tendo que transformar tudo em uintptr_t para manter uma versão canônica da conversão para inteiro
  • Mesmo em processadores de 64 bits, se você assumir que a maioria dos apps se vira com menos de 4 GB de RAM, dá para economizar ainda mais usando apenas um espaço de endereçamento de 32 bits
    Indo além, talvez também dê para usar ponteiros relativos/de curto alcance de 16 bits. Isso pode combinar bem com design orientado a dados, por exemplo com blocos de 64K elementos em que os elementos internos apontam uns para os outros com índices uint16
  • Isso faria o coletor de lixo odiar você. Ou pelo menos faria com que ele tratasse essa estrutura de dados como lixo
  • Fico curioso sobre por que alguém iria querer usar essa técnica
  • Isso não é muito diferente de armazenar a diferença entre dois ponteiros em vez de um ponteiro em si. Se você armazenar a diferença, naturalmente também dá para percorrer nos dois sentidos

• Tinha uma coisa faltando. XOR também é uma função hash linear 3-wise independente, então pode ser usado para amostragem uniforme aproximada probabilística e contagem das soluções de funções booleanas. É realmente útil e é usado para construir contadores que, embora probabilísticos, fornecem contagens comprovadas. Escrevi uma explicação mais fácil de entender aqui https://www.msoos.org/2018/12/how-approximate-model-counting...
  Basicamente, ele reduz o espaço de soluções quase exatamente pela metade a cada vez. Então você vai adicionando restrições XOR até que, por exemplo, sobrem 10 soluções; se k for o número de XORs adicionados, basta multiplicar 10 por 2^k. Como reduz pela metade a cada etapa, você chega rapidamente à faixa de 10 soluções, então escala bem
  Os artigos relacionados estão em https://arxiv.org/abs/1306.5726 e https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, e as ferramentas estão em https://github.com/meelgroup/approxmc e https://github.com/meelgroup/unigen. Na última competição de model counting, quando combinado com um contador exato, isso superou com folga os outros concorrentes, e os slides estão em https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

• Uma das minhas histórias favoritas sobre XOR é a que Bryan Cantrill, da Oxide, Joyent e Sun, conta nesta apresentação https://speakerdeck.com/bcantrill/oral-tradition-in-software... e neste vídeo https://www.youtube.com/watch?v=4PaWFYm0kEw
  Resumindo para você não precisar clicar nos links: quando estava na Sun, ele estava conversando com o colega Roger Faulkner sobre por que C não tem XOR lógico. Faulkner disse que era porque não dá para fazer short-circuit, e Brian achou isso estranho. Então Roger enviou um e-mail para Dennis Ritchie perguntando, e Ritchie confirmou que Faulkner estava certo. A forma como Cantrill conta isso é engraçada, mas o mais impressionante é que eles podiam perguntar diretamente à pessoa envolvida

  • DMR era surpreendentemente gentil, prestativo e acessível. Em meados dos anos 80, quando eu ainda era universitário, li sobre o “primeiro” porte do Unix v6 para o Interdata 8/32, em vez do PDP-11, e mandei um e-mail do nada para [e-mail] perguntando se havia mais informações sobre a arquitetura
    Na época não existia Google e a biblioteca da universidade também não tinha nada; alguns dias depois ele pediu meu endereço físico, e algumas semanas mais tarde uma cópia do manual resumido do conjunto de instruções chegou à minha caixa de correio. Tinha um ar de família IBM 360, e eu ainda o tenho
  • C tem XOR lógico, e ele é o operador !=. Diferente dos outros operadores lógicos, ele precisa normalizar os argumentos para um único valor de verdade, e combina bem com o idiomático !! de conversão booleana em C
  • Não entendo por que “não dá para fazer short-circuit” seria um impedimento para adicionar o operador. Queria que alguém explicasse
  • O tópico em questão começa em 37:18
  • C já tem, há mais de 40 anos, o operador XOR em nível de bit ^: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

• Descobri hoje que, se você fizer XOR do emoji de automóvel com 0x20, ou seja, “colocá-lo em minúsculas”, ele vira o emoji de proibido pedestres. Parece coincidência boa demais para ser acaso, então fiquei curioso se alguém sabe se isso foi intencional
  Se forçar muito a barra, dá até para pensar na ideia estranha de que a minúscula do emoji de automóvel é a placa de “proibido pedestres”

  • Para contornar o processador de comentários do HN que remove emojis, dá para verificar assim:
    >>> from unicodedata import lookup, name
>>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
'NO PEDESTRIANS'
  • A minúscula de automóvel parece que deveria ser kart
  • :tada: → :tophat:, :rocket: → :mountain_cableway: também funcionam

• Uma boa analogia do mundo real para explicar XOR é o interruptor de luz de uma escada. Há um interruptor embaixo e outro em cima, e ambos controlam a mesma luz
  No começo, os dois estão na posição desligada; ao ligar o interruptor de baixo, a luz acende. Você sobe a escada e liga o interruptor de cima, e então, mesmo com os dois interruptores na posição “ligada”, a luz apaga. A luz só acende quando um interruptor está “ligado” e o outro está “desligado”; fora isso, fica apagada

  • Talvez o eletricista do nosso escritório tenha feito a fiação errada. Há dois interruptores na sala e, pensando bem, eles se comportam mais como uma porta AND do que como XOR. Os dois interruptores da sala de estar com certeza se comportam como XOR

• Realmente não gosto que essa função lógica seja comumente chamada de XOR, ou “OR exclusivo”. Quase sempre, o significado real é “soma módulo 2”, isto é, paridade, e não OR exclusivo
  “Soma módulo 2”/paridade e “OR exclusivo” são funções lógicas diferentes, e só coincidem por acaso quando os operandos de entrada são 2. Isso porque só existe um número ímpar menor ou igual a 2
  Quando há 3 ou mais entradas, o que a maioria chama de XOR na verdade é paridade: vale 1 quando há uma quantidade ímpar de entradas iguais a 1. Já o OR exclusivo, com 3 ou mais entradas, é a função que vale 1 apenas quando exatamente uma entrada é 1 e todas as outras são 0
  Em hardware de computadores, a paridade é muito mais importante do que o OR exclusivo. O principal motivo é que a adição módulo 2 é usada como bloco de construção para implementar adição de números maiores. Em contrapartida, na matemática, o OR exclusivo é muito mais importante do que a paridade
  Por exemplo, quantificadores que expressam que algum elemento de um conjunto, todos os elementos ou um elemento único satisfazem um predicado se baseiam respectivamente em OR, AND e OR exclusivo. O “or” da linguagem natural sempre significa OR inclusivo ou OR exclusivo, nunca a paridade que muitos programadores chamam de XOR
  Em programação, raramente é preciso calcular a função lógica de OR exclusivo, mas ela é muito usada para descrever o comportamento de programas. Por exemplo, ao dizer que, em uma instrução composta select/case/switch, a primeira instrução ou a segunda ou a terceira será executada, ou ao descrever os tipos que o valor atual de uma variável de união/soma pode ter

  • O padrão de símbolos eletrotécnicos IEC 60617 trata isso corretamente. A porta XOR é marcada com =1, e a porta de paridade com 2k + 1. Mas, ao usar software de projeto de circuitos para PCB ou FPGA, você ainda pode acabar recebendo algo diferente do que esperava
  • O que foi mencionado em matemática é chamado de quantificador de existência única, e tem seu próprio símbolo ∃!
  • A explicação de que “OR exclusivo”, com 3 ou mais entradas, é verdadeiro quando exatamente uma delas é 1 precisa de fundamentação
  • Essa interpretação também é discutida no ensaio principal

• Existe também a tabela hash distribuída Kademlia: kademlia distributed hash table. A grande ideia é que cada nó recebe bits aleatórios no intervalo [0, 2^m), e a distância é definida por XOR. Quer-se encontrar um algoritmo distribuído que envie informação rapidamente de X para Y sem conhecer a rede inteira
  Dá para provar que funciona só pela matemática, mas a intuição visual de que gosto é a seguinte. Suponha que o nó inicial X esteja procurando o nó k. Defina a “árvore de distância de X” como uma árvore binária cujas folhas têm índices 0, 1, 2..., e rotule cada folha com X^leaf_index para representar sua distância até X. Por exemplo, como dist(x, x) = x^x = 0, o rótulo do nó original X fica na folha mais à esquerda, 0
  O intervalo [2^i, 2^(i+1)) é uma subárvore da árvore de distância de X. Se você sabe que a distância até k está nesse intervalo, consulta algum nó Y ali dentro como vizinho aproximado
  Não importa qual Y você escolha: na árvore de distância de Y, o prefixo resultante sempre será alguma permutação da subárvore [2^i, 2^(i+1)) escolhida na árvore de distância de X. Mais precisamente, pode-se ver que labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)). Os índices são por distância, mas os rótulos podem mudar
  Para comparação com outras tabelas hash distribuídas, como Chord, há materiais muito mais rigorosos, tanto matematicamente quanto empiricamente. Mas essa intuição visual dá uma boa noção do que é a “simetria” do Kademlia, a sensação de que cada um tem seus próprios vizinhos locais e sua própria subárvore
  Já o Chord, mesmo implementado em duas direções, parece exigir o dobro de memória e também parecer mais arriscado de implementar, além de ser difícil obter esse nível de “isolamento”. A janela deslizante de vizinhos de tamanho S está sempre se movendo, e há 2^m vizinhos diferentes para cada bit. Mesmo que a maioria dos vizinhos pareça semelhante, não fica elegante
  O Kademlia tem 1 + 2 + 4 ... + 2^m-1 vizinhos, e tudo é organizado

• Para quem estiver curioso, essa pessoa é o Simon Tatham do Simon Tatham's Portable Puzzle Collection. Se você não conhece, vale a pena para passar o tempo offline quando estiver sem nada para fazer
  Gastei muito tempo com isso no ensino médio: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • Ele também é o Simon Tatham que criou o PuTTY: https://www.chiark.greenend.org.uk/~sgtatham/putty/
  • A melhor parte é que o algoritmo de Campo Minado cria jogos que não exigem adivinhação

• Hoje em dia, muitas solucionadoras de otimização customizadas, por exemplo a Ising Machine, usam o problema XOR como benchmark. Na prática, resolver vários cláusulos XOR é possível em tempo polinomial com eliminação de Gauss, então sua utilidade real é um pouco limitada, mas como todas essas solucionadoras mostram escalabilidade exponencial, isso acaba sendo uma boa forma de medir desempenho
  Uma segunda implementação interessante está relacionada ao criptossistema McEliece. Trata-se de uma criptografia de chave pública dos anos 70, que hoje volta a receber atenção por causa da resistência quântica. O ataque de decodificação é o problema de encontrar a solução de um conjunto de equações XOR, que novamente está em tempo polinomial, mas com a condição adicional de que a distância de Hamming deve ser igual a um certo número incluído na chave pública

• Quando eu estava aprendendo assembly Z80 para programar no TI-83, cada byte de código de máquina importava. Isso porque o espaço total de armazenamento da calculadora era de apenas 24 KB
  Para inicializar com 0 o registrador acumulador principal a, eu usava XOR a em vez de LD a, 0. Nas instruções matemáticas, a é o operando implícito, então XOR a faz o XOR de a com ele mesmo, e a instrução inteira ocupa só 1 byte. Já para carregar explicitamente 0 em a, o literal 0 precisa entrar no opcode, então LD a, 0 é uma instrução de 2 bytes