Напишете функция, която разменя стойностите на променливи, без да използва временни променливи

Това е класическо интервю за работа, което хората обичат да предлагат, и е достатъчно лесно. Нека a0 е първоначалната стойност на a и b0 е първоначалната стойност на b. Нека diff е разликата a0-b0.

Нека покажем относителната позиция на всички тези стойности върху числовата ос за случая, когато a > б:

Задайте a на разл. Ако добавим стойността на b и diff, тогава получаваме a0 (резултатът трябва да се съхранява в b). Сега имаме b = a0 и a = diff. Всичко, което трябва да направим, е да присвоим на b стойността a0-diff и тази стойност е b-a.

Следният код прилага този алгоритъм:

Можете да разрешите този проблем, като използвате битова манипулация. Този подход ще ни позволи да работим с различни типове данни, а не само с integer.

Този код използва операцията XOR. Най-лесният начин да разберете как работи кодът е да разгледате два бита, p и q. Нека означим с p0 и q0 началните стойности.

Ако можем да разменим два бита, тогава алгоритъмът ще работи правилно. Нека да разгледаме как работи алгоритъмът стъпка по стъпка:

p = p0^q0 /* 0 ако p0 = q0, 1 ако p0 != q0 */
q = p^q0 /* е равно на стойността на p0 */
3. p = p^q /* е равно на стойността на q0 */

Ред 1 изпълнява операцията p = p0^q0 , която ще доведе до 0, ако p0 = q0 и 1, ако p0 != q0 .

Ред 2 изпълнява операцията q = p^q0 . Нека анализираме и двете възможни p стойности. Тъй като искаме да разменим стойностите на p и q, резултатът трябва да бъде 0:

p = 0: в този случай p0 = q0, тъй като трябва да върнем p0 или q0. XORing всяка стойност с 0 винаги произвежда оригиналната стойност, така че резултатът от тази операция е q0 (или p0 ).
p = 1 : в този случай p0 != q0 . Трябва да получим 1, ако q0 = 0, и 0, акоако p0 = 1. Това е точно резултатът, получен при XOR на всяка стойност с 1.

Ред 3 изпълнява операцията p = p^q . Нека разгледаме и двете p стойности. В резултат искаме да получим q0. Имайте предвид, че q в момента е равно на p0, така че p^p0 действително се изпълнява.

p = 0: тъй като p0 = q0, искаме да върнем p0 или q0. Правейки 0^p0, ще върнем p0(q0).
p = 1 : Изпълнява се операцията 1^p0. В резултат на това получаваме инверсията на p0 , което е това, от което се нуждаем, тъй като p0 != q0 .

Остава само да присвоим на p стойността q0 , а на q стойността p0 . Уверихме се, че нашият алгоритъм правилно разменя всеки бит, което означава, че резултатът ще бъде правилен.