Как я учился программировать: обмен значений переменных

Хочу продолжить цикл материалов о том, какие трудности и озарения встречает на своём пути начинающий программист.

Ранее:

Рассмотрим такую задачу.

Есть две переменные, foo и bar. Нужно поменять их значения местами.

Странно писать про это, потому что решение очевидно. Но я отлично помню, что для меня, как начинающего программиста, оно было совсем не очевидно. И когда я получил решение, то почувствовал что-то вроде маленького озарения.

В чём трудность?

Чтобы поменять местами значения, программист пишет так:

foo = bar;
bar = foo;

И тут же обнаруживает, что так не работает, потому что как только мы присвоили foo = bar, то потеряли исходное значение foo, и теперь его нельзя привоить bar.

Именно это вводит в ступор. Да-да, не смейтесь, все с чего-то начинают, и даже такие простые вещи должны сначала "щёлкнуть" в голове.

Решение

Нужно ввести промежуточную переменную для сохранения значения foo:

tmp = foo;
foo = bar;
bar = tmp;

И вот случилось озарение. У него потом будет много последствий. Горизонты возможностей расширились.

Решение уровня "бог"

Иногда эту задачу намеренно усложняют. Спрашивают, а как сделать обмен без использования временной переменной?

Тут уже становится смешно далеко не всем :)

Для этого можно использовать логическую операцию XOR. Про неё я уже писал здесь:

Но тогда не смог внятно рассказать, как это работает, а теперь могу.

Итак, чтобы поменять местами foo и bar без временной переменной, пишем:

foo ^= bar;
bar ^= foo;
foo ^= bar;

Ключ к пониманию это осознание того, что делает операция XOR, она же "исключающее или". Забудьте про это странное название, всё гораздо проще. Если два бита не совпадают, мы получаем результат 1, если же совпадают, то 0. Возможно, легче просто представить такую функцию, работающую для каждого бита:

return bit_foo != bit_bar

(Отсюда же идёт и техника обнуления без присвоения 0: foo ^ foo всегда даст 0, так как все биты будут совпадать.)

Давайте для определённости возьмём foo = 101, bar = 010 в двоичном виде и сделаем foo ^= bar.

foo = 101 ^ 010 = 111

В foo обнулятся все биты, совпадающие с bar, и станут единицами все, которые не совпадают. Дальше делаем bar ^= foo:

bar = 010 ^ 111 = 101

Рассмотреть этот шаг можно в три этапа:

1. Все биты, которые ранее совпали, равны 0. При наложении 0 на любой бит из bar ничего не изменится. Т.е. 1 ^ 0 = 1, 0 ^ 0 = 0. Значит, совпадающие биты просто остались в bar, что нам и требуется.
2. Роль играют только биты, которые не совпадают с foo. Рассмотрим варианты несовпадений. Если в foo был 0, а в bar 1, то 1 ^ 1 даст нам 0, то есть то, что было в foo. Если в foo был 1, а в bar 0, то 0 ^ 1 даст нам 1, то есть опять то, что было в foo.
3. Следовательно, совпадающие с foo биты останутся нетронутыми, а несовпадающие... станут совпадающими. Теперь в bar находится значение foo.

Далее ещё раз делаем foo ^= bar:

foo = 111 ^ 101 = 010

Здесь всё происходит аналогично.

1. Совпадающие биты в foo обнулены, но будут восстановлены из bar, так как 0 ^ 0 = 0, 0 ^ 1 = 1.
2. Несовпадающие заменятся: если в bar находится 1, значит наш несовпадающий это 1 ^ 1 = 0, а если 0, то наш несовпадающий это 1 ^ 0 = 1.

Красиво, не правда ли?

Решение уровня "Гуру-питонист"

В "лёгком языке для новичков" есть такой способ обмена переменных:

foo, bar = bar, foo

Действительно, элегантно и просто. Но не стоит думать, что "под капотом" там не создаётся ничего лишнего :)

Читайте дальше: