Реализация Decimal XOR

Question

Достаточно легко преобразовать пару десятичных чисел в двоичный код и выполнить двоичный XOR, но можно ли реализовать XOR в мире base-10?

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

Он должен сохранить свойства XOR: 1. (ор) б -> х, а (ор) х -> Ь, Ь (ор) х -> а 2. а (ор) б == b (op) a

Я также думаю, что распределение ответов должно быть четным. (10 нулей, 10 и т. Д.)

Пожалуйста, не отвечай, чтобы превратить десятичный в двоичный. Я специально хочу помочь либо строить эту таблицу или придумывая арифметического решения (в DXOR б)

Я думаю Dand и DOR «истина» таблицы должны быть построены и быть логически совместимы с DXOR а :-)

Answer 1

Если вам нужна ассоциативность, это невозможно. Вы не указали его, но если вам нужна ассоциативность ((A DXOR B) DXOR C == A DXOR (B DXOR C)), то вы ищете абелеву группу порядка 10, где каждый элемент, но идентификатор имеет порядок 2. Однако Cauchy's theorem требует, чтобы любая группа порядка 10 имела элемент порядка 5.

Если вы не хотите ассоциативности, это выполнимо, но результат теряет много хороших свойств XOR. В этом случае вы ищете абсолютно симметричную квазигруппу порядка 10. Я не знаком с квазигруппами, но с советом Марка Дикинсона я построил один с желаемыми свойствами. Вот «умножение» таблица:

x 0 1 2 3 4 5 6 7 8 9 
    ------------------- 
0|2 4 0 3 1 7 9 5 8 6 
1|4 1 3 2 0 9 6 8 7 5 
2|0 3 4 1 2 5 8 9 6 7 
3|3 2 1 0 4 8 7 6 5 9 
4|1 0 2 4 3 6 5 7 9 8 
5|7 9 5 8 6 2 4 0 3 1 
6|9 6 8 7 5 4 1 3 2 0 
7|5 8 9 6 7 0 3 4 1 2 
8|8 7 6 5 9 3 2 1 0 4 
9|6 5 7 9 8 1 0 2 4 3 

я построил совершенно симметричный квазигруппу 5-го порядка методом проб и ошибок, а затем взял прямое произведение с циклической группой порядка 2 для получения этого. Правильность была проверена в Python. Поскольку я мало знаю о квазигруппах, я не знаю, есть ли более естественный выбор квазигруппы.

Answer 2

Возвращаясь к корням XOR как «дополнение по модулю 2», вы можете реализовать четность в десятичной форме, используя дополнение по модулю 10. Это ассоциативно и коммутативно, как XOR. Кроме того, модульное умножение распределяется по модульному добавлению, подобно тому, как И распределяется по XOR.

Это видит, что в реальности используется, например, check digits of credit cards use this scheme.

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

Answer 3

Я реализовал то, что можно было бы назвать «десятичным XOR» для целочисленной маскирующей функции. Я начал с математического представления двоичного XOR. Для двух двоичных значений A и B, A XOR B = (2 * B-A)% 2. Продолжайте и убедитесь, что работает.

Теперь, если я изменю% 2 на% 10, я могу использовать десятичные значения от 0 до 9. Для двух десятичных значений A и B, A XOR B = (2 * B-A)% 10.

Проблема в том, как модуль реализуется для отрицательных значений. Обычная реализация заключается в слепо преобразовании A% B в | A |% | B |. Итак, -1% 10 = 1% 10 = 1. Я не хочу этой реализации. Я хочу, чтобы реализация такая A% B, сколько целых шагов A выше следующего младшего кратного B. Для -1% 10 это будет -1 - -10, потому что -10 является следующим самым низким кратным 10.Результат: 9.

Поскольку результат (2 * B-A) не может быть меньше -9, все, что мне нужно сделать, это проверить: if (R < 0) R + = 10; Я следую этому: если (R> 9) R = 10; для обработки случаев, когда результат был больше 9 (самое высокое - 18).

Теперь, когда теория покрыта, вы можете реализовать его и видеть, что если А XOR B = C, используя эту десятичную версию XOR, то C XOR B = A. Я реализовал это в нескольких различных языках http://shaunwagner.com/projects/mask.html