Можно ли отменить серию XOR?

Я провел несколько тестов на бумаге, но, кажется, нигде не могу найти подтверждения.

Скажем, у меня есть несколько уникальных 8-битных чисел, и я XOR их вместе и хранить где-то Если я потом, потом, xor тех же номеров вместе с этим сохраненным номером, я всегда получу 0?

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

Так что-то вроде

sanity_check = C1 ^ C3 ^ C5
...
//Condition one is met
sanity_check ^= C1
...
//Condition 3 is met
sanity_check ^= C3
...
//Condition 5 is met
sanity_check ^= C5
...
if( sanity_check == 0 )
 Do operation

Я знаю, что это не безупречно, потому что с правильными условиями я мог бы где-то получить промежуточное состояние 0. Но это больше для моего личного использования в качестве защиты от случайного перемещения одного из этих условий под действие в будущем.

Источник

3 ответа

Решение

Да, XOR является коммутативным и ассоциативным, и x ^ x == 0Таким образом, вы можете отменить последовательность XOR, выполнив ту же самую последовательность снова.

Источник

Было бы лучше использовать битовое поле, где каждый бит представляет условие:

C1 = 1;  // 1 << 0
C2 = 2;  // 1 << 1
C3 = 4;  // 1 << 2
C4 = 8;  // 1 << 3
C5 = 16; // 1 << 4

// Condition one is met
sanity_check |= C1;

....

// If Conditions 1 2 and 4 passed
if((sanity_check & (C1 | C2 | C4)) == (C1 | C2 | C4))

// If Conditions 1 and 2 passed and 3 failed
if((sanity_check & (C1 | C2 | C3)) == (C1 | C2))

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

Источник

Да. Ответ Даниэля дает хорошую основу для интуитивного понимания того, почему XOR абсолютно обратимы. Я чувствую, что вы хотите быть уверены, что это всегда так. Пора спускаться по кроличьей норе!

Двоичные числа ints а все остальное сводится к тому) ^ оператор формирует то, что называется группой. Это означает, что для intsa, b а также c,

  1. a ^ b всегда также int,
  2. a ^ b ^ c всегда одинаково, независимо от того, какую пару вы рассчитываете в первую очередь. Это то, что Даниил имел в виду под "ассоциативным".
  3. Есть int (0) для которого 0 ^ a = a ^ 0 = a, Это тождество, в этом XORing 0 с int не меняет это.
  4. Для любого a вы выбираете, всегда, всегда, всегда b чтобы a ^ b = b ^ a = 0, В такой ситуации b называется обратным a в том, что он нейтрализует a дать личность. Вы также можете доказать, что для каждого числа существует только одна такая инверсия, но я не собираюсь этого делать.

Теперь конкретная пара ints а также ^ имеет еще два свойства, которые делают то, что вы говорите, возможно.

  1. a ^ b == b ^ a для любого a & b, Это то, что Даниил имел в виду под "коммутативностью".
  2. a ^ a = 0, что означает, что int это собственный обратный по отношению к ^,

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

C1 ^ C3 ^ C5 ^ C1 ^ C3 ^ C5

Теперь, поскольку у нас есть коммутативность, мы можем переключать их и объединять в пару, чтобы получить:

C1 ^ C1 ^ C3 ^ C3 ^ C5 ^ C5

И из-за ассоциативности и самообращения мы получаем:

(C1 ^ C1) ^ (C3 ^ C3) ^ (C5 ^ C5) = 0 ^ 0 ^ 0 = 0

Вы можете использовать ту же логику, чтобы успокоить себя с любым выражением. Это всегда будет правдой. То, что вы получаете промежуточный 0, не имеет значения. На самом деле не имеет значения, что является каким-либо из значений. Матем тебя покроют.

Источник
Другие вопросы по тегам