LE Extrem de greu de înțeles. Intuitiv îmi dau seama că perechile de numere identice se anulează reciproc (un număr xor cu el însuși dă mereu zero) și cumva iese în evidență numărul singuratic, care se propagă până la final. Evident, dacă strecori numere alandala, rezultatul va fi si el alandala, dar e o idee foarte interesantă.
Sigur ca are sens, iar intuitiv putem construi altfel putin problema;
Sa luam proprietatile XOR pentru orice numar:
a XOR a = 0
a XOR 0 = a
0 XOR a = a
0 XOR 0 = 0
Si este si o operatie comutativa pe deasupra Adica a XOR b = b XOR a
Hai sa luam si un exemplu de sir si sa XOR-uim toate elementele rand pe rand:
3 3 5 => 3 XOR 3 XOR 5 => 0 XOR 5 => 5 (poti sa te gandesti la acest rezultat ca fiind singurul numar care nu are pereche din sir)
Acum pentru exemplul de mai sus, unde sirurile difera doar printr-un singur numar (asta e esential ca sa mearga trucul cu XOR):
sir1: 1 2 3
sir2: 1 3
Trucul aici este ca nu te gandesti la ele ca fiind doua siruri separate ci la un singur sir cu numere duplicate. Reducem deja problema la aceasi chestie de mai sus.
1 2 3 1 3 => (cum este comutativa, putem sa schimbam ordinea ca sa ne fie noua mai usor [ca oameni]) => 1 1 3 3 2 => ramai cu 0 XOR 2 => raspuns 2
Pe linkul care l-a postat @std.bless , e mult mai in detaliu explicat si vad ca are mult mai multe goodies.
Da, da, în momentul în care am încetat să consider cele două row-uri de numere ca fiind separate, am înțeles instant care-i trick-ul, pur și simplu se anulau între ele numerele identice și rămânea doar cel “în plus”. În acest caz este valabil și un șir de genul, poziția perechilor este complet irelevantă:
5 5 6 6
7 7 8 8 9
Și, evident, rezultatul va fi 9. Păcat ca arta asta a biților aproape că s-a pierdut
Apropo de chestii din astea contraintuitive, știu că în C/C++ compilatorul uneori optimizează operațiile de împărțire a numerelor întregi folosind tehnică bizară cu care mi-am scrântit mintea încercând s-o înțeleg, division by multiplication.
Da, asa este. Dar asta e un lucru bun Cand lucram sa accelerez masiv un algoritm in CUDA si compilatoarele nu erau inca optimizate pentru arhitectura de la vremea aceea (Kepler), am avut un blocaj imens de performanta. Ma asteptam ca dupa cateva modificari sa am o crestere de 20x a vitezei, dar in schimb aveam doar 2x. Am stat vreo 2 luni sa-mi dau seama ca lovitura cea mai mare erau niste operatii de baza:
c + a*b => asta era slow-ish si nici nu avea precizie excelenta
a*b + c => asta era mult mai rapida si avea si precizie buna
Prin 2014, compilatorul CUDA (nvcc) nu stia sa optimizeze pentru fma - fused multiply-add o instructiune clasica acum. Tot ce am facut a fost sa ajut compilatorul putin schimband ordinea operatiilor. Un face-palm moment pentru mine si o realizare ca nici compilatoarele nu-s perfecte.
Asta nu prea are cum să se întâmple, din câte știu ordinea de evaluare în C este garantată să fie de la stânga la dreapta, din acest motiv este safe să faci teste de genul ăsta:
if(ptr && ptr->isRed()) {
[...]
}
Dacă nu era garantată ordinea de evaluarea primeai instant segfault în cazul în care pointerul era NULL.
Era pe un proiect vechi in urma cu 20 ani, environmentul era cu HP-UX si compilatorul cu care venea sistemul de operare (nu gcc).
Probabil ca nu mai tin minte detaliile exact dar era o problema data de optimizare in cazul unei expresii conditionale.