Pular para o conteúdo

Truques com XOR

Aula 2 de 5 · 4 min

Truques com XOR

Passo 1 de 7

XOR dobra uma lista inteira num único acumulador. Comece em zero; o primeiro valor é 4.

A ideia

O XOR tem duas propriedades que fazem todo o trabalho: x ^ x é 0, e x ^ 0 é x. Ele também ignora a ordem.

Então aplique XOR em uma lista inteira e todo valor que aparece duas vezes se apaga. O que sobra apareceu um número ímpar de vezes — em O(n) de tempo e O(1) de memória.

Exemplo do mundo real

O RAID 5 guarda um disco de paridade que é o XOR dos outros. Perca qualquer disco e o conteúdo dele é reconstruído aplicando XOR em tudo o que restou: o bloco que falta é o valor que ficou sem par.

O código

Sua vez

Preencha a lacuna.

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

Quanto é `x ^ x`?