Задачи с собеседований: без посредников

Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?

Решить задачу можно, используя арифметические или побитовые операции. Арифметические проще, но есть одно «но».

Пусть у нас есть 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

Еще задачи с собеседований.