Логическое доказательство ассоциативного свойства для XOR

Question

Логическое доказательство ассоциативного свойства для XOR

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

{2,3,5,2,5,5,3}

Решением будет целое число 5, так как оно встречается в списке 3 раза, в то время как другие целые числа встречаются четное число раз.

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

Тем не менее, я обнаружил, что более эффективное решение существует, просто выполняя XOR для каждого элемента-вам даже не нужен сортированный массив! То есть:

2^3^5^2^5^5^3 = 5

Я вспоминаю, что из класса дискретных структур я взял, что ассоциативное свойство применимо к операции XOR, и поэтому это решение работает:

a^a = 0

И:

a^a^a = a

Хотя Я помните, что ассоциативное свойство работает для XOR, у меня возникли проблемы с поиском логического доказательства этого свойства, специфичного для XOR (большинство логических доказательств в Интернете, кажется, больше сосредоточены на операциях и и или). Кто-нибудь знает, почему ассоциативное свойство применяется к операции XOR?

Я подозреваю, что это включает в себя XOR-идентичность, содержащую И И/ИЛИ ИЛИ.

2 11

boolean-logic proof discrete-mathematics

2 ответа:

Пока a ^ b == ~a & b | a & ~b, Вы можете доказать, что:
(a ^ b) ^ c = ~((~a & b) | (a & ~b)) & c | ((~a & b) | (a & ~b)) & ~c
И
a ^ (b ^ c) = a & ~((~b & c) | (b & ~c)) | ~a & ((~b & c) | (b & ~c))
Равны.

1

Eric Postpischil · Accepted Answer · 2012-11-07 16:11:04

Ассоциативное свойство говорит, что (a^b)^c = a^(b^c). Поскольку XOR является побитовым (биты в числах обрабатываются параллельно), нам просто нужно рассмотреть XOR для одного бита. Тогда доказательство может быть сделано путем изучения всех возможностей:
abc (a^b) (a^b)^c (b^c) a^(b^c)
000   0      0      0      0
001   0      1      1      1
010   1      1      1      1
011   1      0      0      0
100   1      1      0      1
101   1      0      1      0
110   0      0      1      0
111   0      1      0      1
Поскольку третий столбец, (a^b)^c, идентичен пятому столбцу, a^(b^c), ассоциативное свойство сохраняется.