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

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

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

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

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

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

  1. Анонимный17 марта 2010 г. в 02:12

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

    ОтветитьУдалить
  2. R-ride17 марта 2010 г. в 02:14

    wecanstoptrain, тогда разбей на три операции=)

    ОтветитьУдалить
  3. Александр17 марта 2010 г. в 02:18

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

    ОтветитьУдалить
  4. Анонимный17 марта 2010 г. в 02:20

    Вернее undefined:
    http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#351

    ОтветитьУдалить
  5. Анонимный17 марта 2010 г. в 02:26

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

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

    ОтветитьУдалить
  6. Александр17 марта 2010 г. в 02:35

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

    ОтветитьУдалить
  7. Анонимный17 марта 2010 г. в 02:47

    Первый вариант, кстати, не гарантирует выполнение операции если а = 32767

    ОтветитьУдалить
  8. Александр17 марта 2010 г. в 03:02

    xander_prowler: Первый пример чисто книжный.

    ОтветитьУдалить
  9. Unknown17 марта 2010 г. в 08:37

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

    ОтветитьУдалить
  10. [k06a]17 марта 2010 г. в 10:32

    Вот ещё интересные способы:
    http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd

    ОтветитьУдалить
  11. Александр17 марта 2010 г. в 10:38

    Отличная ссылка, спасибо.

    ОтветитьУдалить
  12. [k06a]17 марта 2010 г. в 10:41

    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 - всего лишь способ трактовки двоичного значения. А операции + и - выполняются именно для двоичных значений.

    ОтветитьУдалить
  13. [k06a]17 марта 2010 г. в 10:42

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

    ОтветитьУдалить
  14. [k06a]17 марта 2010 г. в 10:46

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

    ОтветитьУдалить
  15. Анонимный18 марта 2010 г. в 02:26

    Первый пример грозит целочисленным переполнением.

    ОтветитьУдалить
  16. Анонимный18 марта 2010 г. в 08:56

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

    ОтветитьУдалить
  17. Александр18 марта 2010 г. в 09:25

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

    ОтветитьУдалить
  18. Alex18 марта 2010 г. в 23:44

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

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

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

    ОтветитьУдалить
  19. theonewho12 апреля 2010 г. в 14:31

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

    ОтветитьУдалить
  20. theonewho12 апреля 2010 г. в 15:18

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

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

    ОтветитьУдалить
  21. Александр12 ноября 2010 г. в 23:50

    http://wmate.ru/ebooks/book237.html

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

Подписаться на: Комментарии к сообщению (Atom)