Una dintre cele mai frecvente probleme care apare în programare este necesitatea de a interschimba valorile a două variabile (a doua variabilă trebuie să ajungă să conțină valoarea inițială a primeia, iar prima variabilă trebuie să ajungă să conțină valoarea inițială a celei de-a doua). Mulți încep cu soluția naivă (presupunem că vatriabilele sunt a și b):
|
1 2 |
a = b; b = a; |
Destul de repede ne dăm seama că nu am realizat nicio interschimbare și, la sfârșit, ambele variabile vor avea valoarea inițială a variabilei a. Nu este greu să ne prindem și că avem nevoie de o variabilă auxiliară pentru a realiza interschimbarea (așa cum, în principiu, avem nevoie de un al treilea pahar dacă dorim să interschimbăm conținuturile a două pahare). Codul nostru devine:
|
1 2 3 |
aux = a; a = b; b = aux; |
Dar, oare chiar nu putem fără variabilă auxiliară? Uneori putem! Cel mai simplu caz este atunci când avem numere întregi.
Să considerăm următoarea secvență:
|
1 2 3 |
a = a + b; b = a - b; a = a - b; |
Probabil intuiți că secvența realizează o interschimbare. Să vedem de ce! Presupunem că, inițial, variabila a conține un număr α, iar variabila b conține un număr β.
În urma executării primei instrucțiuni, valoarea variabilei a va deveni α + β, iar valoarea variabilei b va fi nemodificată (β).
După executarea celei de-a doua instrucțiuni, valoarea variabilei b va deveni α + β - β = α, adică exact valoarea inițială a variabilei a. Valoarea variabilei a va rămâne α + β.
În sfârșit, după executarea ultimei instrucțiuni, valoarea variabilei a va deveni α + β - α = β, iar cea a variabilei b va fi nemodificată (α).
Așadar, acum variabila a conține numărul β, iar variabila b conține numărul α, deci am interschimbat valorile.
Putem să începem și cu o scădere? Da! Puteți verifica destul de ușor că următoarea secvență este și ea corectă:
|
1 2 3 |
a = a - b; b = a + b; a = b - a; |
Mai avem câteva variante asemănătoare. Puteți încerca să le găsiți singuri...
Dar, funcționează întotdeauna? Aproape! Am putea avea probleme dacă vreuna dintre sume sau diferențe este prea mare sau prea mică pentru a fi reprezentată ca număr întreg. Chiar și atunci, în majoritatea limbajelor overflow-urile se compensează și rezultatul este corect. Dar, nu e bine să ne bazăm pe așa ceva!
Putem folosi și alte operații? Să încercăm cu înmulțiri și împărțiri:
|
1 2 3 |
a = a * b; b = a / b; a = a / b; |
Funcționează și așa, deși acum riscăm mult mai mult ca produsul să fie prea mare. De data aceasta overflow-ul creează probleme.
Putem identifica și o a doua problemă la varianta cu înmulțiri și împărțiri; ce se întâmplă dacă unul dintre numere este zero?
Putem începe cu o împărțire? Nu! Deși ar părea că este cam același lucru, împărțirea este întreagă deci s-ar pierde informație. Secvența "logică" ar fi:
|
1 2 3 |
a = a / b; b = a * b; a = b / a; |
Toate ar fi bune și frumoase dacă a ar fi multiplu al lui b (nu s-ar pierde restul la împărțirea întreagă). Dar, de cele mai multe ori nu va fi cazul!
Dacă avem numere reale, putem face și așa (vom avea eventual probleme cu rotunjirile).
Există și alte operații pentru care funcționează "șmecheria"? Trebuie să observăm o caracteristică a perechilor de operații folosite. Totul se baza pe faptul că β - β = 0 și α + 0 = α, respectiv că β / β = 1 și α * 1 = α. Mai riguros, putem spune că rezultatul aplicării unei operații asupra a doi operanzi cu aceeași valoare trebuie să fie elementul neutru al primei operații. Dacă scădem β din β, obținem 0, elementul neutru al adunării. Dacă împărțim β la β, obținem 1, elementul neutru al înmulțirii.
Avem o operație simpatică care poate face pereche cu ea însăți și are această caracteristică. E destul de greu să ne dăm seama care este, dar va părea natural după ce o vom preciza. Este vorba de disjuncția exclusivă pe biți (xor, notat ^). Este destul de ușor de observat că β ^ β = 0 și α ^ 0 = α. Secvența de cod ar fi:
|
1 2 3 |
a = a ^ b; b = a ^ b; a = a ^ b; |
Observăm că nu mai avem probleme nici cu overflow-ul.
Variantele pot fi prescurtate dacă vrem; de exemplu, prima variantă ar putea fi scrisă și:
|
1 2 3 |
a += b; b = a - b; a -= b; |
Ultima variantă devine acum și mai simpatică:
|
1 2 3 |
a ^= b; b ^= a; a ^= b; |
