Tutorial

Ideias com XOR

Aplicações comuns e não triviais do XOR

Introdução

Definições

XOR, representado por $\oplus$, é uma operação binária que pode ser definida a partir da seguinte tabela:

Esta operação pode ser naturalmente extendida para inteiros maiores que $1$: Basta considerar a representação binária dos números, e fazer a operação para cada bit respectivamente.

Exemplo: $5 \oplus 6 = 101_2 \oplus 110_2 = 011_2 = 3$.

Esta extensão da operação de XOR é chamada de bitwise XOR, ou “XOR para cada bit”. Em C++, a operação é feita com o operador ^.

Propriedades

A operação de XOR é comutativa e associativa, ou seja,

para quaisquer $a$, $b$ e $c$. Além disso, temos que

Ideias

1. Cancelando valores iguais

Uma aplicação direta do fato que $a \oplus a = 0$ é que se temos o XOR de alguns elementos $A \oplus B \oplus C \ oplus D$, e queremos apenas $A \oplus B$, por exemplo, podemos simplesmente calcular o XOR com $C \oplus D$:

Com isso, podemos fazer algo semelhante a soma de prefixos com XOR, por exemplo.

Problema. Você recebe um array de inteiros onde cada elemento aparece exatamente duas vezes no array, exceto um único elemento, que aparece exatamente uma vez. Encontre o elemento que aparece apenas uma vez.

Aqui, nós abusamos do fato que o XOR é comutativo, e que $a \oplus a = 0$. Se calcularmos o XOR de todos os números do array, cada número que aparece duas vezes vai ser cancelado, e o que vai sobrar é exatamente o elemento que aparece uma vez.

2. Hashing com XOR

A ideia é usar a comutatividade do xor para verificar se dois conjuntos tem os mesmos elementos. Se dois conjuntos tem os mesmos elementos, o XOR deles também é igual.

Há um problema com essa abordagem: imagine que queremos verificar se $(1, 2, 3)$ é igual a $(4, 5, 6, 7)$. Ambos os conjuntos tem XOR $0$, então o algoritmo diria que os conjuntos são iguais.

Uma forma de resolver esse problema é a seguinte:

• Não calcular o XOR dos números diretamente.
• Em vez disso, manter um map para associar cada número possível de um conjunto com um número aleatório.
• Na hora de calcular o XOR, não usamos os números do conjunto em si, e sim os números mapeados.
• Com isso, a probabilidade de dois conjuntos diferentes terem o mesmo XOR é reduzida significativamente.

Problema. Você recebe uma permutação dos números $(1, 2, \dots, n)$, e você precisa processar $q$ queries da seguinte forma: dados $l$, $r$, verifique se os números $a_l, a_{l + 1}, \dots, a_{r - 1}$ são números consecutivos em alguma ordem. Por exemplo, os números $5, 3, 7, 4, 6$ são números consecutivos ($3, 4, 5, 6, 7$) permutados.

Vamos aplicar a ideia acima. Para isso, precisamos saber qual o conjunto de números deveria estar no intervalo. Podemos usar qualquer estrutura para encontrar o mínimo e o máximo em um intervalo, como uma sparse table ou uma segment tree. Dados o mínimo e o máximo, digamos $a$ e $b$, os números devem ser $a, a + 1, \dots, b$.

Agora vem a parte do XOR. Para cada número $1, 2, \dots, n$, vamos associar um número aleatório, e precisamos calcular o XOR dos números associados a $a, a + 1, \dots, b$ de forma eficiente, e podemos fazer isso com soma de prefixos com XOR. Finalmente, só precisamos calcular o XOR dos números associados a elementos do array original em um intervalo, que também podemos fazer com soma de prefixos com XOR.

Se usarmos sparse table para encontrar o mínimo e o máximo, a complexidade final fica $O(1)$ por query.

Problemas

• Distinct Numbers
• Adding Chords
• Multisets