Логическое доказательство ассоциативного свойства для 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 (большинство логических доказательств в Интернете, похоже, больше сосредоточены на операциях AND и OR). Кто-нибудь знает, почему ассоциативное свойство применяется к операции XOR?

Я подозреваю, что он включает идентификатор XOR, содержащий AND и/или OR.

Ответы

Ответ 1

Ассоциативное свойство говорит, что (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), имеет место ассоциативное свойство.

Ответ 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))

Является равным.