Другой способ показать это — использовать алгебру XOR; вам не нужно ничего знать об отдельных битах.
Для любых чисел x, y, z:
XOR является коммутативным: x ^ y == y ^ x
XOR является ассоциативным: x ^ (y ^ z) == (x ^ y) ^ z
Идентификатор 0: x ^ 0 == x
Каждый элемент является своим обратным: x ^ x == 0
Учитывая это, несложно доказать сформулированный результат. Рассмотрим последовательность:
a ^ b ^ c ^ d ...
Поскольку XOR является коммутативным и ассоциативным, порядок не имеет значения. Итак, рассортируйте элементы.
Теперь любые соседние одинаковые элементы x ^ x можно заменить на 0 (свойство самоинверсии). И любой 0 можно убрать (потому что это тождество).
Повторяйте как можно дольше. Любое число, встречающееся четное число раз, имеет целое число пар, поэтому все они становятся равными 0 и исчезают.
В конце концов у вас останется только один элемент, который появляется нечетное количество раз. Каждый раз, когда он появляется дважды, эти два исчезают. В конце концов вы останетесь с одним случаем.
[Обновить]
Обратите внимание, что это доказательство требует только определенных предположений об операции. В частности, предположим, что множество S с оператором . имеет следующие свойства:
Ассоциативность: x . (y . z) = (x . y) . z для любых x, y и z в S.
Идентичность: существует единственный элемент e, такой что e . x = x . e = x для всех x в S.
Закрытие: для любых x и y в S x . y также находится в S.
Самоинверсия: для любого x в S x . x = e
Как оказалось, нам не нужно предполагать коммутативность; мы можем это доказать:
(x . y) . (x . y) = e (by self-inverse)
x . (y . x) . y = e (by associativity)
x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right)
y . x = x . y (because x . x = y . y = e and the e's go away)
Теперь я сказал, что «вам не нужно ничего знать об отдельных битах». Я думал, что любой группы, удовлетворяющей этим свойствам, будет достаточно, и что такая группа не обязательно должна быть изоморфна целым числам по XOR.
Но @Steve Jessup доказал, что я ошибаюсь в комментариях. Если вы определяете скалярное умножение на {0,1} как:
0 * x = 0
1 * x = x
...тогда эта структура удовлетворяет всем аксиомам векторного пространства по модулю целых чисел 2.
Таким образом, любая такая структура изоморфна набору векторов битов при покомпонентном XOR.
person
Nemo
schedule
18.06.2011
