*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 17 марта 2010 г.

Обмен двух переменных через XOR

Чтобы поменять местами значения двух целочисленных переменных кроме как через использование дополнительной переменной, можно сделать так:
a += b;
b = a - b;
a -= b;
Интересно разве что с академической точки зрения. Но есть способ интереснее:
a ^= b ^= a ^= b;
который также меняет местами значения этих переменных.

Update: В комментариях подсказали грамотную ссылку по трюкам с битовой арифметикой.

21 комментарий:

  1. Уточнил бы язык. Может, на каком-то C# это и прокатит, но на C/C++ - это unspecified behavior

    ОтветитьУдалить
  2. wecanstoptrain, тогда разбей на три операции=)

    ОтветитьУдалить
  3. wecanstoptrain: Язык С/C++. А почему unspecified behavior? Операции присваивания выполняются справа налево. Точно также, как бы они были записаны в три строки.

    ОтветитьУдалить
  4. Вернее undefined:
    http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#351

    ОтветитьУдалить
  5. Александр: Да, операции выполняются справа налево, но стандарт не определяет, что будет лежать в переменной "a" после выполнения данного выражения.

    здесь все разжевано:
    http://alenacpp.blogspot.com/2005/11/sequence-points.html

    ОтветитьУдалить
  6. Да, похоже лучше в одну строчку не писать. Спасибо за совет.

    ОтветитьУдалить
  7. Первый вариант, кстати, не гарантирует выполнение операции если а = 32767

    ОтветитьУдалить
  8. xander_prowler: Первый пример чисто книжный.

    ОтветитьУдалить
  9. Попался мне этот вопрос на интервью. Только формулировка была другой: "Как поменять содержимое двух ячеек, не используя третьей?" Индус с гордостью показал мне арифметическое решение, после чего я доказал что на самом деле эти операции задействуют больше двух ячеек (дебаг на ассемблере все объясняет).

    ОтветитьУдалить
  10. Вот ещё интересные способы:
    http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd

    ОтветитьУдалить
  11. xander_prowler, никакой разницы нет вроде. С этим проблемы могут быть только в джаве имхо . . . Ведь переменные "зациклены" так сказать.

    char a = 127, b = 28;
    a = a + b; // станет a = -101, b = 28
    b = a - b; // станет a = -101, b = 127
    a = a - b; // станет a = 28, b = 128

    Ведь signed/unsigned - всего лишь способ трактовки двоичного значения. А операции + и - выполняются именно для двоичных значений.

    ОтветитьУдалить
  12. Александр, время от времени почитываю там некоторые бит-хаки)) Работают мгновенно.

    ОтветитьУдалить
  13. xander_prowler, кстати считал в calc.exe в Win7))
    Там теперь есть режим "Программист".
    Пруфпик: http://yfrog.com/jw123rmp

    ОтветитьУдалить
  14. Первый пример грозит целочисленным переполнением.

    ОтветитьУдалить
  15. Если a и b -- это ссылки на одну и ту же переменную, то приведённый код (я о втором варианте) обнулит её. В общем, я бы дважды подумал перед тем, как использовать такое на практике.

    ОтветитьУдалить
  16. i1ey: Да, проверить на то, что а и b разные переменные не мешает, но это критично для любой функции обмена. В большинстве случаев разумно проверить, чтобы не гонять данные впустую.

    ОтветитьУдалить
  17. Прикольно, конечно, но зачем ?
    Напомнило "изврат" с определением минимального из двух чисел:

    min (a, b) ::= (a + b - ABS (a - b))/2

    Конечно, if не используется, но каково придется тому, кто такое будет потом читать :)

    ОтветитьУдалить
  18. Но, видали. А как думаете (а может кто опыт ставил) по производительности какой из трёх вариантов победит? (третий с дополнительной переменной)

    ОтветитьУдалить
  19. на питоне получилось так (меньше — быстрее):
    с использованием разницы/суммы - 74 у.е.
    с использованием третьей переменной - 47 у.е.
    с использованием xor - 81 у.е.

    Может, конечно, особенности питона. Надо попробовать на сях.

    ОтветитьУдалить