Трюк с XOR для собеседований и не только

Автор оригинала: Florian Hartmann
  • Перевод


Есть целая куча популярных задач для собеседований, которые можно решить одним из двух способов: или логичным применением стандартных структур данных и алгоритмов, или использованием некоторых свойств XOR сложным для понимания способом.

Хоть и непривычно ожидать решения с XOR на собеседованиях, довольно забавно разбираться, как они работают. Оказывается, все они основаны на одном фундаментальном трюке, который я постепенно раскрою в этом посте. Далее мы рассмотрим множество способов применения этого трюка с XOR, например, при решении популярной задачи с собеседований:

Дан массив из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются только один раз, за исключением одного числа, которого нет. Найдите отсутствующее число.

Разумеется, существует множество прямолинейных способов решения этой задачи, однако есть и довольно неожиданный, в котором применяется XOR.

XOR


XOR — это логический оператор, работающий с битами. Давайте обозначим его ^. Если два получаемых им на входе бита одинаковы, то результат будет равен 0, в противном случае 1.

При этом применяется операция исключающего ИЛИ — чтобы результат был равен 1, только один аргумент должен быть равен 1. Можно показать это с помощью таблицы истинности:

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

В большинстве языков программирования ^ реализован как побитовый оператор, то есть XOR по отдельности применяется к каждому биту в строке битов (например, в байте).

Пример:

0011 ^ 0101 = 0110

так как

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Благодаря этому мы можем применять XOR к чему угодно, а не только к булевым значениям.

Выявляем полезные свойства


Из представленного выше определения можно вывести несколько свойств. Давайте разберём их по порядку, а затем скомбинируем их для решения задач с собеседований.

XOR и 0: x ^ 0 = x


Если одним из аргументов XOR является 0, то второй аргумент является результатом. Это непосредственно следует из таблицы истинности, достаточно посмотреть на строки, где y = 0 (первая и третья строка).

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

XOR с одинаковыми аргументами: x ^ x = 0


Если два аргумента одинаковы, то результат всегда равен 0. Мы можем убедиться в этом, снова взглянув на таблицу истинности. На этот раз нужно посмотреть на строки, где x = y (первая и последняя).

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

Это означает, что применив XOR к одинаковым аргументам, мы их взаимно уничтожим.

Коммутативность: x ^ y = y ^ x


Операция XOR коммутативна, то есть мы можем менять порядок применения XOR. Чтобы доказать это, можно взглянуть на таблицу истинности x ^ y и y ^ x:

x y x ^ y y ^ x
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0

Как мы видим, x ^ y и y ^ x всегда дают одинаковые значения.

Последовательности операций XOR


Скомбинировав всё это, мы можем вывести главную мысль, стоящую в основе всего дальнейшего:

Трюк с XOR: если у нас есть последовательность операций XOR a ^ b ^ c ^ ..., то из неё можно убрать все пары повторяющихся значений, и это не повлияет на результат.

Коммутативность позволяет нам изменить порядок применения XOR, чтобы повторяющиеся элементы находились рядом друг с другом. Так как x ^ x = 0 и a ^ 0 = a, каждая пара повторяющихся значений не будет влиять на результат.

Давайте разберём пример:

  a ^ b ^ c ^ a ^ b     # Commutativity
= a ^ a ^ b ^ b ^ c     # Using x ^ x = 0
= 0 ^ 0 ^ c             # Using x ^ 0 = x (and commutativity)
= c

Так как ^ — побитовый оператор, это будет работать вне зависимости от типа значений a, b и c. Эта идея лежит в основе многих применений XOR, которые могут показаться магическими.

Способ применения 1: перемена значений местами


Прежде чем приступать к задаче поиска отсутствующего числа, давайте начнём с более простой задачи:

Поменяйте местами два значения x и y без использования вспомогательных переменных.

Оказывается, эту задачу можно легко решить при помощи трёх команд XOR:

x ^= y
y ^= x
x ^= y

Это кажется довольно загадочным. Почему при этом x и y поменяются местами?

Чтобы понять, как это происходит, давайте разберёмся пошагово. В комментарии после каждой команды указаны текущие значения (x, y):

x ^= y # =>                      (x ^ y, y)
y ^= x # => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y # => (x ^ y ^ x, x)     = (y, x)

Воспользовавшись выведенными ранее свойствами, мы видим, что это на самом деле так.

Фундаментальным открытием здесь является то, что при наличии x ^ y в одном регистре и x в другом мы можем совершенно точно воссоздать y. После сохранения x ^ y (команда 1) мы можем просто поместить x в другой регистр (команда 2), а затем использовать его для замены x ^ y на y (команда 3).

Способ применения 2: поиск отсутствующего числа


Давайте наконец решим задачу, представленную в начале поста:

Дан массив A из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются в нём ровно один раз, за исключением одного отсутствующего числа. Найти это отсутствующее число.

Разумеется, есть множество прямолинейных решений этой задачи, но мы решили использовать XOR.

Из трюка с XOR мы знаем, что имея последовательность операторов XOR, можно убрать из неё все повторяющиеся аргументы. Однако если мы просто применим XOR ко всем значениям массива, то не сможем воспользоваться этим трюком, потому что в нём нет одинаковых значений:

A[0] ^ A[1] ^ ... ^ A[n - 2]

Обратите внимание, что A[n - 2] — последний индекс списка из n - 1 элементов.
Дополнительно мы можем выполнить XOR для всех значений от 1 до n:

1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2]

Так мы получим последовательность операторов XOR, в которой элементы встречаются следующим образом:

  • Все значения из исходного массива теперь встречаются дважды:
    • один раз из-за взятия всех значений от 1 до n
    • один раз, потому что они были в исходном массиве

  • Отсутствующее значение встречается только один раз:
    • из-за взятия всех значений от 1 до n

Применив ко всему этому XOR, мы, по сути, уберём все встречающиеся дважды значения благодаря трюку с XOR. Это значит, что останется только отсутствующее значение, то есть именно то, которое мы и искали.

В коде это будет выглядеть примерно так:

def find_missing(A, n):
  result = 0

  # XOR of all the values from 1 to n
  for value in range(1, n + 1):
    result ^= value

  # XOR of all values in the given array
  for value in A:
    result ^= value

  return result

С первого взгляда на код алгоритм понять сложно. Однако если знать, как работает трюк с XOR, то он становится довольно тривиальным. По-моему, именно поэтому не стоит ждать такого решения на собеседованиях: оно требует знания очень специфичного трюка, но почти никакого алгоритмического мышления.

Прежде чем мы перейдём к следующему способу применения, я сделаю пару замечаний.

Использование этого трюка не только для целых чисел


Хоть мы пока работали только с целыми числами от 1 до n, это необязательно. На самом деле, предыдущий алгоритм работает в любой ситуации, где есть (1) некоторое множество потенциальных элементов и (2) множество действительно встречающихся элементов. Эти множества могут отличаться только одним отсутствующим элементом. Это замечательно сработало для целых чисел, потому что множество потенциальных элементов соответствует элементам от 1 до n.

Можно придумать способы применения, где элементы не являются целыми числами от 1 до n:

  • Множество потенциальных элементов — это объекты Person и нам нужно найти Person, отсутствующего в списке значений
  • Множество потенциальных элементов — все узлы графа, и мы ищем отсутствующий узел
  • Множество потенциальных элементов — просто целые числа (необязательно с 1 до n) и нам нужно найти отсутствующее целое число

Арифметические операции вместо XOR


Если алгоритм по-прежнему кажется вам непостижимым и магическим (надеюсь, это не так), то может быть полезным подумать, как достичь того же результата при помощи арифметических операторов. На самом деле всё довольно просто:

def find_missing(A, n):
  result = 0

  # Add all the values from 1 to n
  for value in range(1, n + 1):
    result += value

  # Subtract all values in the given array
  for value in A:
    result -= value

  return result

Мы складываем все потенциальные целые числа, а затем вычитаем те, которые встречаются на самом деле. Это решение не такое красивое, потому что придётся обрабатывать переполнения, а также потому что тип элементов должен поддерживать +, - с определёнными свойствами. Однако здесь используется та же логика взаимного уничтожения элементов, потому что они встречаются определённое количество раз (один раз как положительное, другой — как отрицательное).

Способ применения 3: поиск повторяющегося числа


И вот здесь всё становится интереснее: мы можем применить точно такое же решение к похожей задаче с собеседования:

Дан массив A из n + 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением одного числа, которое повторяется. Найти это повторяющееся число.

Давайте подумаем, что произойдёт, если мы просто применим алгоритм из предыдущего решения. Мы получим последовательность операторов XOR, в которой элементы встречаются следующим образом:

  • Повторяющееся значение встречается три раза:
    • один раз из-за взятия всех значений от 1 до n
    • дважды, потому что оно повторяется в исходном массиве

  • Все остальные значения встречаются дважды:
    • один раз из-за взятия всех значений от 1 до n
    • один раз, потому что они были уникальными в исходном массиве

Как и ранее, все повторяющиеся элементы взаимно уничтожаются. Это означает, что у нас осталось именно то, что мы ищем: элемент, повторяющийся в исходном массиве. Встречающийся три раза элемент в сочетании с XOR сводится к этому самому элементу:

  x ^ x ^ x
= x ^ 0
= x

Все остальные элементы взаимно уничтожаются, потому что встречаются ровно два раза.

Способ применения 4: поиск двух отсутствующих/повторяющихся чисел


Оказывается, мы можем расширить возможности алгоритма. Рассмотрим чуть более сложную задачу:

Дан массив A из n — 2 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением двух отсутствующих чисел. Найти эти два отсутствующих числа.

Как и ранее, задача полностью эквивалентна поиску двух повторяющихся чисел.

Как вы наверно догадались, мы будем придерживаться того, что сработало раньше, и начнём точно так же: рассмотрим, что произойдёт, если использовать предыдущий алгоритм с XOR. Если мы его применим, то получим последовательность операторов XOR, в которой все элементы взаимно уничтожают друг друга, за исключением тех, которые мы ищем.

Обозначим эти элементы как u и v, просто потому, что раньше эти буквы не использовали. После применения предыдущего алгоритма у нас останется u ^ v. Что можно сделать с этим значением? Нам каким-то образом нужно извлечь из него значения u и v, но не совсем понятно, как это сделать.

Разделение при помощи изучения u ^ v


К счастью, мы можем понять, что делать, воспользовавшись изложенным выше. Давайте подумаем:

Если два входных бита XOR одинаковы, то результат равен 0, в противном случае 1.

Если проанализировать отдельные биты в u ^ v, то каждый 0 будет означать, что бит имеет одинаковое значение в u и v. Каждая 1 означает, что биты различаются.

Благодаря этому мы найдём первую 1 в u ^ v, т.е. первую позицию i, в которой u и v должны различаться. Затем мы разделим A, а также числа от 1 до n в соответствии с этим битом. В результате мы получим два сегмента, каждый из которых содержит два множества:

  1. Сегмент 0
    1. Множество всех значений от 1 до n, в которых i-тый бит равен 0
    2. Множество всех значений из A, в которых i-тый бит равен 0

  2. Сегмент 1
    1. Множество всех значений от 1 до n, в которых i-тый бит равен 1
    2. Множество всех значений из A, в которых i-тый бит равен 1

Так как u и v различаются в позиции i, то мы знаем, что они должны быть в разных сегментах.

Упрощаем задачу


Далее мы можем использовать ещё одно сделанное ранее открытие:

Хоть пока мы работали только с целыми числами от 1 до n, это необязательно. На самом деле, предыдущий алгоритм работает в любой ситуации, где есть (1) некоторое множество потенциальных элементов и (2) множество действительно встречающихся элементов. Эти множества могут отличаться только одним отсутствующим (или повторяющимся) элементом.

Эти два множества точно соответствуют множествам, находящимся в каждом из сегментов. Следовательно, мы можем выполнить поиск u, применив этот принцип к одному из сегментов и найдя отсутствующий элемент, а затем найти v, применив его к другому сегменту.

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

Достигнуть предела


Можно попробовать пойти ещё дальше и попытаться решить задачу с тремя и более отсутствующими значениями. Я не особо это обдумывал, но считаю, что на этом наши успехи с XOR закончатся. Если отсутствует (или повторяется) больше двух элементов, то анализ отдельных битов выполнить не удастся, поскольку существует множество сочетаний для результатов в виде 0 и 1.

Следовательно, задача требует более сложных решений, больше не использующих XOR.

Заключительные мысли


Как говорилось выше, наверно, не стоит давать такие задачи на собеседованиях. Для их решения нужно знать не сразу понятный трюк, но если он известен, то решать больше практически нечего (возможно, за исключением способа применения 4). Едва ли таким образом кандидат продемонстрирует алгоритмическое мышление (кроме навыков упрощения) и здесь не особо получится использовать структуры данных.

Однако здорово было выяснить, как этот трюк работает. Похоже, XOR обладает идеально подходящими для этой задачи свойствами. Кроме того, есть некая красота в том, что нечто столь фундаментальное, как XOR, можно использовать для создания описанных в статье алгоритмов.



На правах рекламы


VDSina предлагает виртуальные серверы на Linux и Windows — выбирайте одну из предустановленных ОС, либо устанавливайте из своего образа.

VDSina.ru
Серверы в Москве и Амстердаме

Комментарии 102

    +13
    У xor-а есть куда более практичное применение — коды Грея

    image
      0
      И код Хэмминга. Хотя в википедии в алгоритмах кодирования/декодирования что-то с матрицами наворочено, на самом деле идея простая — xor номеров единичных битов.
        0
        Да это проще Рида-Соломона, но более расточительно. Вот пример кодирования 8бит в 12бит способное восстановить один ошибочный бит.
        /*
        Hamming encode/decode
                                 MP3 0  0  0  0  0  0  0  1  1  1  1  0
                                 MP2 0  0  0  1  1  1  1  0  0  0  0  1
                                 MP1 0  1  1  0  0  1  1  0  0  1  1  0
                                 MP0 1  0  1  0  1  0  1  0  1  0  1  0
        D0 D1 D2 D3 D4 D5 D6 D7      C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB
        B0 B1 B2 B3 B4 B5 B6 B7 <==> P0 P1 B0 P2 B1 B2 B3 P3 B4 B5 B6 B7 
                                           **    ** ** **    ** ** ** **
        data_byte                    hamming_code (L=C0..C7, H=C8..CB)
        
        P0=C0 xor C2 xor C4 xor C6 xor C8 xor C10
        P1=(C1 xor C2) xor (C5 xor C6) xor (C9 xor C10)
        P2=(C3 xor C4 xor C5 xor C6) xor (CB)
        P3=(C7 xor C8 xor C9 xor CA)
        
        P3_0 -> 0-no_error, 1..12 invalid bit number
        
        Hamming encode D7_0  ==> C11_0
        Hamming decode C11_0 ==> D7_0
        */
        int hamming_parity(int x) {
          int i,p;
          for(p=0, i=1;i<=12;++i) { if (x&1) p^=i; x>>=1; }
          return p;
        }
        
        int hamming_encode(int x) {
          int p,r;
          r=((x<<4)&0x0F00)|((x<<3)&0x0070); if (x&1) r|=4; // encode
          p=hamming_parity(r); r|=p&3; if (p&4) r|=0x0008; if (p&8) r|=0x0080; // set parity
          return r;
        }
        
        int hamming_decode(int x) {
          int p,r;
          p=hamming_parity(x); if (p) x^=1<<(p-1); // correcting error
          r=((x>>4)&0xF0)|((x>>3)&0x0E); if (x&4) r|=1; // decode
          return r;
        }
        
      +1
      Использовать XOR для перемены значений местами на практике не стоит: минус — код работает в 3-4 раза медленнее чем с использованием доп.переменной, минус — трудности с читабельностью кода, минус — работает только базовыми числовыми типами, минус — доп. память все-таки используется, правда неявно — регистры или стек
        +5
        Медленнее? Да ладно.

        xor eax, ebx
        xor ebx, eax
        xor eax, ebx

        vs
        mov ecx, eax
        mov eax, ebx
        mov ebx, ecx

          +9
          А там какого-нибудь XCHG разве нет?
            0
            блин.
            я и забыл про него.
            вот что значит долгое отсутствие практики :(
            но мне по старой памяти всё равно кажется, что арифметика на х86 в разы шустрее передачи значений. могу и ошибаться.
              +8
              Как по мне, такие трюки нужно применять только в очень специальных ситуациях, когда ресурсы ну совсем кончились. Типа бутлоадера в микроконтроллере, когда каждый байт на вес золота. А в нормальной жизни за такое нужно бить по голове на кодревью.
              Ну и вообще, я бы данный пост назвал «питонисты познают то, что очевидно для сишников» )
                +4
                А я так тихо пробурчу в тапок, что если человека бьют по голове
                за то, что он считает каждый байт на вес золота (и каждый такт заодно),
                то человек должен тихо уйти оттуда — и пусть они там поубивают
                друг друга.
                  +4
                  Время программиста уже давно дороже, чем время процессора.
                    +3
                    Зависит от процессора. Есть такие, где иначе не будет работать.
                      +4

                      Это справедливо если код будет выполнятся немного и у себя. А если это миллиарды повторений на всех компьютерах мира?

                        +1
                        Сколько компаний пишут такой код, который выполняется «на всех компьютерах мира»?
                        Подход к разработке, целесообразный в этих немногих компаниях, нецелесообразен во всех остальных.
                          0

                          Valve? Microsoft (в плане — Github и т.п)
                          Intel?

                        0
                        А если программа выполняется на клиенте, то процессорное время и вовсе получается «бесплатным», платит пользователь.
                        Хотя есть, конечно, и своя выгода в оптимизации — например, охват аудитории, которая сможет пользоваться программой с комфортом на своём железе.
                        +3
                        Я специально написал что есть ситуации, когда это можно и нужно делать. И про бутлоадер не зря написал, потому что это буквально из моего опыта. Бутлоадер ограничен 8К, а первый билд получился 13К. После чего я примерно месяц делал так чтоб оно влезло, используя все возможные трюки, некоторые из них ещё на Спектруме использовал.
                        p.s. Поставить другой контроллер было уже не вариантом, так что пришлось корячиться.
                        p.p.s. И я там написал много комментариев на тему почему это сделано так и сколько это экономит байт, хоть вроде и не очевидно что экономит.
                          0
                          Вспомнился баянистый рассказ про этот самый последний недостающий байт: habr.com/ru/post/27055
                        0
                        За такие трюки однозначно можно бить по голове только в том случае, если они подробно не расписаны тут же в комментариях.
                        Я регулярно пользуюсь XOR — например, для проверки, не изменилось ли отслеживаемое значение. Такой вот волшебник XOR, несущий свет XOR в массы :)
                          0
                          В качестве оператора «не равно»?
                            0
                            Да.
                        +4
                        передачи может и на случиться. «ок, положим, что регистр R21 теперь называется не EAX, а ECX» — переименование регистров. Более того, может произойти такой фокус, как «ок, положим, что переменная _I0001 до 112й строки называется 'x', а начиная со 113 — 'y'», еще на этапе компиляции.

                        Оптимизировать руками это можно после того, как удалось доказать, что результат оптимизации положительный и больше погрешности измерений.
                        0
                        If a memory operand is referenced, the processor’s locking protocol is automatically implemented for the duration of the exchange operation, regardless of the presence or absence of the LOCK prefix or of the value of the IOPL.

                        Может выйти и медленнее, чем через промежуточный регистр.
                          0
                          При этом надо иметь в виду, что xchg reg,mem работает очень медленно.
                            0
                            А я и не предлагаю его использовать. Напишу через обмен через переменную. Пусть компилятор пусть сам думает что из этого сделать, у него голова большая.
                            Вот эта вот штука с обменом через XOR имеет настолько узкоспециальное применение, что я вот даже не помню использовал ли это хоть где-нибудь за 30 лет написания программ. Очень может быть что использовал в 90-х в демо на Спекки, когда нужно было считать каждый такт и каждый регистр процессора был на вес золота.
                              0
                              Для x86_64 код
                              x ^= y;
                              y ^= x;
                              x ^= y;


                              компилируется в
                                      mov     eax, DWORD PTR [rbp-8]
                                      xor     DWORD PTR [rbp-4], eax
                                      mov     eax, DWORD PTR [rbp-4]
                                      xor     DWORD PTR [rbp-8], eax
                                      mov     eax, DWORD PTR [rbp-8]
                                      xor     DWORD PTR [rbp-4], eax


                              А код
                                  z=x;
                                  x=y;
                                  y=z;


                              соответственно в
                                      mov     eax, DWORD PTR [rbp-4]
                                      mov     DWORD PTR [rbp-12], eax
                                      mov     eax, DWORD PTR [rbp-8]
                                      mov     DWORD PTR [rbp-4], eax
                                      mov     eax, DWORD PTR [rbp-12]
                                      mov     DWORD PTR [rbp-8], eax


                              Выигрыш от этой конструкции на языках высокого уровня только моральный (экономия 1 переменной).
                                +2
                                x ^= y;
                                y ^= x;
                                x ^= y;

                                компилируется в
                                mov eax, DWORD PTR [rbp-8]
                                xor DWORD PTR [rbp-4], eax
                                ....
                                Извините, вы, кажется, '-O2' уронили… Вот, держите: https://godbolt.org/z/rPb4dh
                                  +1
                                  Точно, забыл ;) С оптимизацией оба варианта (с xor и с временной переменной) компилируются в один xchg.
                                  ЗЫ: лучше использовать std::swap — это коротко, понятно, и результат тот же.
                          +3
                          В общем случае медленнее, потому что при этом отключается возможность переупорядочивания последних двух команд — компилятором и/или процессором. Это важное свойство, дающая свои проценты производительности.
                        +3

                        Можно же без XOR и без доп переменных:
                        a=a+b;//a+b
                        b=a-b;//a+b-b=a
                        a=a-b;//a+b-a=b

                          +4
                          А если a или b равно какому-нибудь MaxLongint?
                            0
                            Да, у любого метода своя область применения, там область применения a,b=<Max_переменной/2, а у метода с XOR нет.В этом случае он реально лучше… но метод с плюсом/минусом интуитивнее, и главное может быть обобщен для объектов классов гораздо проще чем XOR
                              –1
                              область применения a,b=<Max_переменной/2, а у метода с XOR нет

                              Нет. Границы применимости у методов абсолютно одинаковые.

                                0
                                Нет, при возможности signed overflow компилятор C / C++ может выбрасывать код: lwn.net/Articles/511259
                                  +1

                                  Если можете что-то ксорить, то вы можете работать с этими [наборами бит] как с беззнаковыми целыми. С беззнаковыми целыми signed overflow никак не возникнет.

                              +1
                              То что? Для беззнаковых целых даже UB нет.
                                +5

                                И что? Пока сами a и b влазят в машинное слово (а иначе задача лишена физического смысла) все работает, независимо от переполнений, возникших при промежуточных вычислениях.
                                Смотрите: пусть, для простоты понимания кожаными мешками, машинное слово — два десятичных разряда.


                                a=98
                                b=99


                                a = a+b = 98+99 = 197 97 // переполнение при сложении
                                b = a-b = 97-99 = -2 98 // переполнение при вычитании
                                a = a-b = 97-98 = -1 99 // переполнение при вычитании


                                У нас во всех трех операциях возникало переполнение, и тем не менее мы получили правильный результат. Модульная арифметика она такая

                                  0
                                  Переполнения, в большинстве случаев, лучше избегать. На мой взгляд, такой фокус допустим в случаях типа лишнего байта.
                                    0
                                    Чем лучше?
                                      –1
                                      Тем, что между моим кодом и физическим процессором есть N слоёв прочего программного обеспечения (включая операционную систему). Соответственно, я не хочу гадать, как будет выполняться мой код, я хочу знать это наверняка. А вдруг на каком-то из слоёв переполнение будет трактоваться, как ошибка?
                                        0
                                        Каким образом на результат арифметического действия может повлиять ОС или любой другой слой ПО, кроме непосредственно используемого компилятора/интерпретатора?
                                  –1
                                  Я этот пример объясняю так. Допустим, у нас есть по сумке в каждой руке и мы хотим их поменять. Дополнительная переменная — это если мы ставим сумку на пол. Если мы хотим перехватить сумки прямо в руках, не опуская на пол, то, в определённый момент, у нас окажется две сумки в одной руке. Значит, мы ограничены грузоподъёмностью одной руки, обе сумки в сумме не должны её превышать. Если мы ставим сумку на пол, то этого ограничения нет.
                                  0
                                  Как один из вариантов, мне понравился вариант ваш с арифметикой.
                                  +14
                                  Мне больше нравится такое свойство:
                                  crc32( a ) ^ crc32( b ) ^ crc32( c ) = crc32(a ^ b ^ c)
                                    0
                                    Это свойство позволяет создавать файлы с наперёд заданной контрольной суммой добавлением всего 4х байт к данным
                                      0
                                      Можете посоветовать, где подробнее про подобные интересные свойства CRC и их полиномов почитать можно?
                                        0
                                        Тут. Но можете и поэкспериментировать ideone.com/yQHn2c
                                        пример
                                        #include <stdio.h>
                                        #include <stdlib.h>
                                        #include <time.h>
                                        
                                        typedef unsigned uint;
                                        uint crc32(const char* data,int size,uint crc=0) {
                                        	crc=~crc;
                                        	for(int i=0;i<size;i++) { 
                                        		crc^=data[i]&255;
                                        		for(int j=0;j<8;j++) crc=crc>>1^0xEDB88320&-(crc&1); 
                                        	}
                                        	return ~crc;
                                        }
                                        
                                        int main(int argc, char const *argv[]) {
                                        	enum { n=10 };
                                        	char payload[n+4];
                                        	srandom(time(0)); for(int i=0;i<n;i++) payload[i]=random();
                                        	
                                        	uint payload_crc=crc32(payload,n);
                                        	printf("crc(payload)=%08X\n",payload_crc);
                                        
                                        	uint x=0xBEDA; 
                                        	char xd[4]={x,x>>8,x>>16,x>>24};
                                        	uint xd_crc=crc32(xd,4);
                                        	uint suffix=payload_crc^x;
                                        	payload[n  ]=suffix;
                                        	payload[n+1]=suffix>>8;
                                        	payload[n+2]=suffix>>16;
                                        	payload[n+3]=suffix>>24;
                                        	uint crc=crc32(payload,n+4);
                                        	printf("crc(data   )=%08X\n",crc);
                                        	printf("crc(x      )=%08X\n",xd_crc);
                                        
                                        	return 0;
                                        }

                                        crc(payload)=116441E8
                                        crc(data   )=A76D55FB
                                        crc(x      )=A76D55FB
                                          0
                                          Благодарю.
                                    0
                                    Это представляет академический интерес. В коммерческой разработке я бы не стал так делать. Эти сэкономленные такты и биты явно не стоят времени, которое новый человек в проекте потратит на понимание, что делает это кусок кода.
                                      0

                                      Это другой человек, увидев такое краткое, быстрое и при этом непонятное ему решение, почувствует свою неполноценность. А это ведь это и есть высшая цель программиста-автора. %))

                                        0
                                        В чём разница между джуниором и сениором?
                                        Джуниор пишет код, который способен понять только сениор.
                                        Сениор пишет код, который способен понять даже джуниор.
                                        0
                                        Есть проекты, где сэкономленные такты имеют значение. Взять тот же крипто майнинг или какое-нибудь потоковое шифрование/кодирование.
                                        Но если есть возможность писать с первого взгляда понятный код — надо именно так и делать.
                                          +1
                                          Ну криптографические алгоритмы, в основном, и разрабатываются в академической среде. Там новому человеку в проекте не нужно рассказывать про бинарную логику — он ей думает)
                                        +1

                                        Ещё одно замечательное свойство — проверка существования выигрышной стратегии и решение игры "ним" (а также всех эквивалентных ей): https://e-maxx.ru/algo/sprague_grundy

                                          0
                                          Мы складываем все потенциальные целые числа, а затем вычитаем те, которые встречаются на самом деле. Это решение не такое красивое, потому что придётся обрабатывать переполнения, а также потому что тип элементов должен поддерживать +, — с определёнными свойствами.

                                          Для указанных в условии задачи целых чисел такой тип элементов называется int.
                                          И нет, как ни странно, обрабатывать переполнения никакой необходимости нет.

                                            +2
                                            А мне больше понравилась реализацыя Switch...Case на xor`ах, в каком-то С-компиляторе (не х86) код подглядел. Примерно так, если на «высоком» уровне:
                                            Switch eax
                                            Case A:

                                            Case B:

                                            Case C:
                                            ....

                                            То получится следующее:
                                            xor eax, A
                                            jz A_label
                                            xor eax, A^B
                                            jz B_label
                                            xor eax, B^C
                                            jz C_label
                                            xor eax, C^D
                                            jz D_label
                                            jmp Default_Label

                                              +1
                                              Многие компиляторы для x86 делают похожий каскад из sub
                                                0
                                                А если А, В и С не по порядку, а произвольные константы?
                                                  0
                                                  То переупорядочивают: Duff's device встречается на много порядков реже, чем switch, в котором каждый case завершается break, return или throw.
                                                0

                                                Так приходится делать в кривеньких dsp, с убогой системой команд

                                                +1

                                                VLIW позволяет сделать rA=rB; rB=rA в одном пакете и не париться с промежуточным регистром

                                                  +2
                                                  Дан массив A из n — 2 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением двух отсутствующих чисел. Найти эти два отсутствующих числа.

                                                  После применения предыдущего алгоритма у нас останется u ^ v. Что можно сделать с этим значением? Нам каким-то образом нужно извлечь из него значения u и v, но не совсем понятно, как это сделать.

                                                  А можно по рабоче-крестьянски пояснить, на пальцах:


                                                  n = 5
                                                  u^v = 1


                                                  какие именно два числа из исходного набора 1,2,3,4,5 были пропущены ?

                                                    +1
                                                    Был массив A, размером n-2, с возможными числами от 1 до n. И массив потенциальных значений N с числами от 1 до n
                                                    Нашли z = u ^ v
                                                    Теперь z смотрим побитово, например он (0,0,0,0,1,0,1,0)
                                                    Понимаем что в числах u и v есть отличие в пятом бите и в седьмом, берем только первое отличие в пятом бите.

                                                    Теперь исходные массивы A и N делим на 2 части, в массивы A1,N1 заносим все числа из A и N в которых пятый бит равен 0, в массивы A2 и N2 заносим все числа из A и N в которых пятый бит равен 1.

                                                    Теперь мы точно знаем что u и v находятся/отсутствуют в разных массивах, которые мы создали. Остается прогнать алгоритм для нахождения одного пропущенного/избыточного числа для A1,N1 и A2,N2 по отдельности, и мы найдем u и v.
                                                      0

                                                      Ну так найдите. Пример-то простой.

                                                        0
                                                        Информации не достаточно, после разбиения будет 2 массива, как ниже написал xi-tauw
                                                        [1, 3, 5], [2, 4]
                                                        И нужно ещё 2 результата xor после применения алгоритма на них, тогда найдётся точная пара чисел.
                                                      0
                                                      На основании u^v=1 строится два множества, отличающиеся тем самым битом. В одном: числа 1,3 и 5, в другом: 2 и 4 (кроме пропущенных). Причем, не умаляя общности, можно считать, что среди 1, 3 и 5 отсутствует u, а среди 2 и 4 отсутствует v.
                                                      Задача, фактически, сведена к предыдущей — есть множество известных элементов, из которого один отсутствует. Снова xor'им, чтобы найти u (или v), далее оставшееся.
                                                        +2
                                                        N = 1, 2, 3, 4, 5
                                                        A = 2, 3, 4, 1, 2, 5, 3
                                                        XOR(A,N) = 3 ^ 2 = 1 (1 0 0 0 0 0 0 0), отличие в первом бите
                                                        Делим
                                                        N1 = 2, 4
                                                        A1 = 2, 4, 2

                                                        N2 = 1, 3, 5
                                                        A2 = 3, 1, 5, 3

                                                        Считаем
                                                        XOR (N1, A1) = 2
                                                        XOR (N2, A2) = 3

                                                        Нашли искомое
                                                          0

                                                          Это все, конечно здорово. Но загадал я 4 и 5 :)

                                                            +2
                                                            Для повторов 4 и 5 всё то же самое:

                                                            N = 1, 2, 3, 4, 5
                                                            A = 2, 5, 4, 1, 4, 5, 3
                                                            XOR(A,N) = 4 ^ 5 = 1 (1 0 0 0 0 0 0 0), отличие в первом бите
                                                            Делим
                                                            N1 = 2, 4
                                                            A1 = 2, 4, 4

                                                            N2 = 1, 3, 5
                                                            A2 = 5, 1, 5, 3

                                                            Считаем
                                                            XOR (N1, A1) = 4
                                                            XOR (N2, A2) = 5
                                                              +2
                                                              Возможно вы неправильно поняли постановку задачи. Требуется найти в уже существующем массиве, а не найти массив в для которого u ^ v дадут какое то число.
                                                              Проекция u ^ v необратима однозначно, и даст одинаковое значение для бесконечного числа пар различных u и v.
                                                          0
                                                          del
                                                            0

                                                            Не в первый раз вижу комменты с текстом «del». Что это означает на сленге хабра?

                                                              +2
                                                              «Ждём не дождёмся, когда ТМ реализуют возможность удалять комментарии, запощенные по ошибке.»
                                                                +2
                                                                Промазал местом ответа, и чтобы не было дубля и замусоривания отредактировал с указанием что текст был удален.
                                                              +1

                                                              Поиск 2 недостающих чисел с помощью xor уже слишком искусственный и вряд ли имеет смысл. Он требует 2 N доп. памяти и O(N) операций xor и сравнений. Имея столько памяти за столько сравнений, можно более эффективный алгоритм поискать. Навскидку.


                                                              N = new int[n];
                                                              for (int a: A) N[a]++;

                                                              Получили в массиве N количество вхождений каждого элемента множества.

                                                                +1
                                                                Нет, дополнительной памяти там по-прежнему O(log N).
                                                                  0

                                                                  Каким образом можно создать 4 множества из 2N элементов, не потратив память?

                                                                    +2
                                                                    Так нам не нужны сами множества.

                                                                    Алгоритм такой:
                                                                    1. Посчитайте u^v (как xor всего множества A xor range).
                                                                    2. Выберите бит, в котором есть расхождение между u и v (пусть это бит i).
                                                                    3. Посчитайте xor {x \in A, x_i = 1} xor {x \in range, x_i = 1} — это u
                                                                    4. Посчитайте xor {x \in A, x_i = 0} xor {x \in range, x_i = 0} — это v
                                                                      0

                                                                      Понял, спасибо

                                                                      –1

                                                                      Пройтись по числам 1..n и по массиву A[n] и у каждого элемента проверять включен-ли i-й бит. Если да, то сделать ^ c переменной агрегатором. В конце процедуры в переменной будет содержаться u. Сделав ^ c u^v, найдем v. Никакой дополнительной памяти, множества строятся "на лету" — просто проверяется входит-ли в него данный элемент.

                                                                  +10
                                                                  Дан массив A из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются в нём ровно один раз, за исключением одного отсутствующего числа. Найти это отсутствующее число.


                                                                  Сумма ряда от 1 до N считается моментально. Сумма чисел в массиве — за 1 проход. Разница == пропущенное число. И никакой магии, кроме школьной математики ;)
                                                                    0
                                                                    Это если в размерность уместитесь, иначе здравствуй, длинная арифметика. Плюс xor'а как раз в том, что все операции гарантированно не приведут к переполнению.
                                                                      +2
                                                                      Не нужно длинной арифметики: для сложений и умножений достаточно модульной, т.е. просто игнорировать переполнения, и результат получится верный.
                                                                    +1
                                                                    Помню, давным давно тесты 1С: Профессионал были такими: Всем выдавали Excel файлы, в которых были листы с заданиями, а на последней странице зашифрованные правильные ответы. Шифр — номер вопроса 5 раз и правильный ответ 5 раз, например, первый ответ в шестом вопросе давал число 11111^66666 = 77581
                                                                    Некоторые хорошо готовились к тесту, а именно: заранее находили подобные файлы, вскрывали пароль на макросы и смотрели алгоритм. Далее дело техники: XOR числа нужной колонки с пятикратным номером вопроса давал правильный ответ. Делалось с помощью виндового калькулятора даже без перехода в режим Программист горячей клавишей.
                                                                    Потом прикрыли лавочку, стали собирать файлы с ответами и отправлять их в 1С.
                                                                    Сейчас всё онлайн, конечно.
                                                                      +2
                                                                      Хороший код — это код, не содержащий трюков.
                                                                        +1

                                                                        Хороший код, это понятный и быстрый.
                                                                        Если элементарные операции вам не понятны, значит вы не туда свернули)

                                                                          0
                                                                          А если трюк не особо очевидный, и не самый быстрый (требуется два цикла, хотя достаточно и одного)?
                                                                            0

                                                                            Это повод написать или прочитать длинный комментарий

                                                                          0

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

                                                                          0
                                                                          С поиском пропущенного числа лучше сумма справится с учётом того, что сумма арифметической прогрессии 1+2+...+n = n(n+1)/2. Притом алгоритм будет толерантен и к переполнениям.
                                                                            0

                                                                            Хз почему минусуют но именно такое решение приходит в голову первым делом.

                                                                              0

                                                                              Минусуют видимо те, у кого есть более элегантное решение

                                                                                +1
                                                                                Либо те, кто заметили, что это решение уже было запощено на две страницы выше.
                                                                            +2

                                                                            Ещё можно заметить, что 2n^(2n+1)=1
                                                                            Это поможет упростить первый цикл. Если n четное, то result после него будет 0, если нечётное, то n+1
                                                                            Пните, если ошибся

                                                                              0
                                                                              1^2^3^4^5 = 1
                                                                              Тут не 0 и не n+1
                                                                                +1
                                                                                Идея в первом комментарии совершенно правильная, надо просто немного хитрее делать.

                                                                                Для нечётного n последовательность 0...n разбивается на парные блоки вида [2x, 2x+1], где x — целое и неотрицательное. Число таких блоков составляет (n + 1) / 2.
                                                                                Каждый блок сокращается в 1 при взятии операции xor внутри блока. Соответственно вся последовательность операций xor сокращается в xor от (n + 1) / 2 единиц. Если (n + 1) / 2 — чётное, то конечный результат 0, в противном случае 1.

                                                                                Для чётного n можно просто посчитать результат xor последовательности для n-1, и сделать xor с n. Получится либо n (при xor с 0), либо n + 1 (при xor с 1).
                                                                              0
                                                                              > Если алгоритм по-прежнему кажется вам непостижимым и магическим (надеюсь, это не так), то может быть полезным подумать, как достичь того же результата при помощи арифметических операторов. На самом деле всё довольно просто
                                                                              Это не только просто, но и быстрее, потому что первый цикл («сложить все числа диапазона») можно сократить до одной строчки — вычисление суммы арифметической прогрессии.
                                                                                0
                                                                                Как заметили чуть выше, с XOR тоже можно сократить первый цикл до одной строчки.
                                                                                0
                                                                                Придумался еще один вариант решения с XOR. Потенциально меньше XOR-ов, но добавляются сравнения.
                                                                                Применяем XOR ко всем элементам, запоминаем результат:
                                                                                P = A[0] ^ A[1] ^… ^ A[n — 1]
                                                                                После этого, поочередно выполняя XOR со всеми числами от 1 до n, находим такое значение, что XOR этого значения с P даст результат, отличный от P. Это и будет искомое число.
                                                                                  0
                                                                                  Единственное значение, XOR которого с P не даст результат, отличный от P — это 0.
                                                                                  Просто по определению XOR.
                                                                                    0
                                                                                    Да, это я глупость какую-то придумал.
                                                                                  0
                                                                                  Помню, в Фидо в RU.HACKER смеялись над, кажется, разработчиками ключей HASP для LPT порта, которыми была защищена 1С бухгалтерия. Разработчики коммерческого продукта для шифрования не знали этого трюка с xor, шифровали A xor B xor C xor… и считали, что множество xor сильно запутывает и это трудно будет расшифровать. А хакеры знали этот трюк. :-)
                                                                                    0

                                                                                    Еще если сделать XOR и затем посчитать единичные биты(popcount) можно найти расстояние Хэмминга.

                                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                    Самое читаемое