GitHub
Задачи с собеседований: без посредников
Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?
Решить задачу можно, используя арифметические или побитовые операции. Арифметические проще, но есть одно «но».
Пусть у нас есть A и B.
A = A + B
B = A – B // После этого B становится A, т.к. получаем (A + B) – B = A
A = A – B
В этом решении есть большой минус: возможность переполнения.
Поэтому лучше использовать поразрядную операцию XOR.
A = A ^ B
B = A ^ B
A = A ^ B
Как это работает: в первой строке мы получаем маску на различающиеся биты, в этих разрядах будут стоять единички. Далее производится сброс и выставление нужных бит для обмена значений.
На примере будет наглядней. Рассмотрим обмен чисел 5 и 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001