Операция XOR Intuition

Недавно я натолкнулся на этот вопрос на Leetcode и выяснил решение, которое мне нужно уточнить, с помощью

Учитывая массив целых чисел, каждый элемент появляется дважды, кроме одного. Найдите этот единственный.

Примечание: Ваш алгоритм должен иметь сложность линейного выполнения. Не могли бы вы реализовать его без использования дополнительной памяти?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(auto & c : nums) {
            result ^= c;
        }
        return result;
    }
};

Прежде всего, какие ключевые слова я должен обратить внимание, чтобы выяснить, что я должен использовать операцию XOR для этого вопроса?

Кроме того, почему XOR'ing все элементы в векторе друг с другом дают нам тот, который не повторяется?

Спасибо всем за эти ответы, вот еще информация о побитовых свойствах для кого-то другого: Более побитовая информация

Ответ 1

A ^ 0 == A
A ^ A == 0
A ^ B == B ^ A
(A ^ B) ^ C == A ^ (B ^ C)

(3) и (4) вместе означают, что порядок, в котором числа xor ed не имеет значения.

Это означает, что, например, A^B^X^C^B^A^C равно A^A ^ B^B ^ C^C ^ X.

Из-за (2), равного 0^0^0^X.

Из-за (1), равного X.

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

Ответ 2

Оператор Xor коммутативен:

1.      X ⊕ Y = Y ⊕ X                    for any integers X and Y

и ассоциативный:

2.      X ⊕ (Y ⊕ Z) = (X ⊕ Y) ⊕ Z      for any integers X, Y and Z

Отсюда следует, что результат любой последовательности операций xor полностью не зависит от порядка операндов (т.е. порядка элементов в массиве).

3.     X ⊕ X = 0                         for any integer X

4.     X ⊕ 0 = 0 ⊕ X = X                for any integer X

В задаче мы имеем выражение, где каждый элемент Ai появляется дважды, за исключением некоторого сингулярного элемента B. итоговая операция Xor эквивалентна:

     (A1 ⊕ A1) ⊕ (A2 ⊕ A2) ⊕    ...   ⊕ B
 = 
         0      ⊕      0     ⊕    ...   ⊕ B
 = 
         B

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

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

Ответ 3

Для меня ключевым интуитивным аспектом, который отличает XOR от других логических операторов, является то, что он без потерь или не потерян, что означает, что в отличие от И и ИЛИ (и более похоже на НЕ в этом отношении), он детерминированно обратим: вы можете точно восстановить одно из входных значений, учитывая остальное истории вычислений.

На следующих диаграммах показано, что И и ИЛИ имеют по крайней мере один случай, когда состояние одного из входов невосстановимо, учитывая определенное значение другого входа, Я указываю их как "потерянные" входы.

Для столбца XOR нет условия, при котором значение ввода или вывода не может быть восстановлено, учитывая остальную историю вычислений. На самом деле, существует симметрия, в которой знание любых двух значений кортежа (in0, in1, out) позволяет вам восстановить третью; в частности, какой вы выбираете в качестве третьего значения, это XOR двух других!

Эта картина предполагает, что другой способ думать о XOR - это как управляемый элемент NOT. Переключая один из входов (верхний в приведенном выше примере), вы можете контролировать, отменено ли другое (нижнее).

Еще одно эквивалентное представление состоит в том, что XOR реализует положительную логику не равно (≠) по отношению к двум его входам. И, таким образом, функция равна (=) в отрицательная логика.

В соответствии с его симметрией и сохраняющими информацию свойствами, XOR следует вспомнить о проблемах, требующих обратимости или идеального восстановления данных. Наиболее очевидным примером является то, что XOR с набором данных с постоянным ключом тривиально скрывает данные, так что знание ключа (которое может храниться "секретно" ) позволяет точно восстанавливать.

Сохранение всей доступной информации также желательно в хешировании. Поскольку вам нужны хеш-значения, которые максимально различаются среди исходных элементов, вы хотите убедиться, что как можно больше их отличительных характеристик включено, минимизируя потери в хеш-коде. Например, для хэширования 64-битного значения в 32 бита вы должны использовать язык программирования XOR ^, потому что это простой способ гарантировать, что каждый из 64 входных битов имеет возможность влияют на выход:

uint GetHashCode(ulong ul)
{
    return (uint)ul ^ (uint)(ul >> 32); 
}

Обратите внимание, что в этом примере информация теряется, даже если используется XOR. (Фактически, "потеря стратегической информации - это вся суть хэширования" ). Исходное значение ul не может быть восстановлено из хэш-кода, потому что у вас нет двух из трех 32-битных значений, которые используются во внутреннем вычислении. Из полученного хеш-кода и двух значений, которые были XOR ed, вы, возможно, сохранили результат, но обычно не сохраняете ни один из последних для использования в качестве ключевого значения для получения другого.

Как забавный вариант, XOR был уникальным образом полезен в дни бит-twiddling hacks. Мой вклад тогда был способом Условно задавать или очищать бит без разветвления в C/С++:

unsigned int v;       // the value to modify
unsigned int m;       // mask: the bits to set or clear
int f;                // condition: 0 to 'set', or 1 to 'clear'

v ^= (-f ^ v) & m;    // if (f) v |= m; else v &= ~m;

С другой стороны, факт, что XOR не является убыточным, имеет важные информационно-теоретические последствия для футуристических вычислений, из-за важной взаимосвязи между обработкой информации и Второй закон термодинамики. Как объяснено в превосходной и доступной книге Чарльза Сейфа, "Декодирование Вселенной" , оказывается, что потеря информации при вычислении имеет точная математическая связь с излучением черного тела, испускаемым системой обработки. Понятие entropyиграет центральную роль в количественном определении того, как потеря информации выражается в виде тепла. Отмечая, что современное развитие ЦП сталкивается с фундаментальными ограничениями на толерантность полупроводниковых материалов Вт/см², решение (описанное Seife) будет заключаться в создании обратимых или без потерь вычислительных систем, где XOR способность сохранять информацию и, таким образом, отключать тепло, будет играть неоценимую роль.

Ответ 4

XOR всегда определяется в терминах двоичных цифр (или некоторых эквивалентных понятий, таких как истинные или ложные утверждения). Нет специального XOR для целых чисел, отличных от XORing соответствующих битов их двоичных представлений.

Пусть A и B - две булевы переменные, а XOR - булева функция, которая принимает две булевы переменные. A⊕B = 1, если либо (A = 0 и B = 1), либо (A = 1 и B = 0) (то есть они различны),
A⊕B = 0, если либо (A = 0 и B = 0), либо (A = 1 и B = 1). (то есть они одинаковы)

Таким образом, учитывая ваш вопрос, поскольку из заданных n элементов вектора каждый элемент появляется дважды, за исключением одного элемента, идея что двоичное представление повторяющихся чисел будет таким же, поэтому результат XOR будет свести на нет друг друга как 1⊕1 = 0 и 0⊕0 = 0.

При A = 5 его двоичное представление равно 101, поэтому A⊕A = (101) ⊕ (101) = 000, которое является десятичным представлением 0.

ПОМНИТЕ, ЧТО НЕ ВМЕШАЕТ, В КОТОРЫХ ЗАКАЗЫ НОМЕРЫ ПОЯВЛЯЮТСЯ ПОСЛЕ КАЖДОГО ДРУГОГО ПОТОМА ((A⊕B) ⊕C) = (A⊕ (B⊕C)). В конце концов, что вы получаете в конце после XORING, каждое число - это число, которое происходит один раз.

Чтобы ответить на вопрос о том, когда вам нужно использовать операции XOR для решения вопроса, воспользуйтесь некоторым вопросом BIT MANIPULATION, в конце концов вы сможете выяснить. Подсказка: вопрос, который требует найти один элемент, который обладает уникальным свойством, кроме отдыха, требует манипуляции с битами.
Пример: для массива, где каждый элемент встречается три раза, кроме одного элемента, который встречается только один раз. Найдите элемент, который встречается один раз.

Ответ 5

Одной простой операцией, которая может быть выполнена в массиве, является выбор свойства P и подсчет количества элементов массива, которые удовлетворяют этому свойству. Например, если P является свойством быть делимым на 5, мы можем перебирать массив и подсчитывать количество элементов, которые делятся на 5.

Предварительное условие в массиве позволяет получить информацию об элементе singleton из такого числа. Если число элементов, удовлетворяющих условию P, нечетно, то синглтон имеет свойство P. Если число элементов, удовлетворяющих условию P, четное, то синглтон не должен иметь свойство P. Например, если мы подсчитаем 3 элемента, делящихся на 5, то синглтон должен быть делимым на 5.

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

Существует много разных коллекций свойств, которые будут работать. Однако мы можем быть эффективными. Учитывая b различные свойства, существуют (не более) 2**b разные способы тестирования, поэтому мы можем отличать только от множества возможных элементов. Итак, нам нужно по крайней мере b различные свойства, чтобы полностью указать число b -bit.

Один такой минимальный набор свойств, который легко тестировать для компьютера, представляет собой коллекцию, в которой свойство n th: "Имеет ли число 1 в n th бит?". Если мы знаем ответ на этот вопрос для каждого n, то, очевидно, мы можем восстановить число.

Другая оптимизация заключается в том, что нам не нужно отслеживать общее количество элементов, удовлетворяющих свойству; нам нужен только паритет. Если мы просто отслеживаем счетчик по модулю 2, нам нужен только один бит для отслеживания вместо целого size_t.

Поскольку мы отслеживаем b разные биты информации, каждая из которых соответствует определенному значению места n, мы можем собрать эти биты вместе в число b -bit.

Это точно решение XOR, представленное в вопросе.

Чтобы начать с, подсчитывается количество запусков каждого из них, равное 0 для каждого бита (следовательно, result инициализируется равным 0). Затем, когда мы XOR-элемент из массива, мы фактически добавляем один модуль 2 к тем битам result, где элемент имеет 1. Наконец, result не требует какого-либо декодирования, так как число с 1 битом точно где result имеет 1 бит самого result.

Ответ 6

Как я уверен, вы знакомы с, целые числа хранятся в памяти как кортежи двоичных цифр. Можно рассматривать каждую цифру как число в поле двух элементов, которое по существу является целым числом по модулю 2. Оператор ^ является компонентным xor, и с этой интерпретацией xor является просто добавлением. То есть мы добавляем двоичные цифры друг к другу.

В этом поле 1 + 1 = 0, поэтому можно сказать, что два равны нулю. Так как сложение является коммутативным и ассоциативным, мы можем одновременно объединить все числа. Все, что добавляется четным числом раз, ничего не добавит, и только число, которое добавляется за один раз, заканчивается в переменной результата.

Может быть интересно узнать, что логические операции представлены таким образом как (попробуйте!): a xor b = a + b, a и b = ab, a или b = ab + a + b, не a = a + 1.