XOR kendini götürür

XOR'un üç özelliği bir araya gelince küçük bir sihir çıkar: bir sayının kendisiyle XOR'u 0'dır (x ^ x == 0), 0 ile XOR'u kendisidir (x ^ 0 == x) ve sıra önemli değildir. Yani bir yığın sayıyı birbirine XOR'larsan, çift sayıda geçen her şey birbirini götürür; geriye tek sayıda geçenler kalır.

1odd_one = 0
2for v in [7, 3, 7, 9, 3]:
3    odd_one ^= v
4# odd_one is 9

Sözlükle saymaya gerek yok, ek bellek yok: tek bir değişken ve tek geçiş. 7'ler birbirini, 3'ler birbirini götürür.

Aynı fikir "eksik olan hangisi?" sorusunu da çözer. 0'dan n'e kadar bütün sayıları ve listedeki bütün sayıları birbirine XOR'la: listede olan her sayı iki kez geçmiş olur ve gider, eksik olan bir kez geçer ve kalır. Toplayıp çıkarmak da aynı işi görür; XOR'un üstünlüğü, sayılar ne kadar büyürse büyüsün taşma derdinin olmamasıdır.

Görevler