как работает этот код?

Question

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

Решение:

Целое число с нечетным числом вхождений будет иметь 0 или более пар и одно число. Итак, если бы мы могли как-то избавиться от всех пар, то все, что у нас осталось бы - это одно число Теперь, что избавляется от пар? Подсказка: подумайте об операторе.

XOR сделает свое дело. Это дает вам решение O (n) без дополнительной памяти.

int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];

for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}

Answer 1

Это работает, потому что (N xor Q) xor Q = N.

Ровно одно целое число присутствует нечетное количество раз, поэтому оно будет единственным числом, которое не «исчезнет» из списка. Все остальные числа присутствуют четное количество раз, поэтому все они появляются группами по 2 (возможно), поэтому все они «исчезают». Кроме того, «расстояние» между XOR не имеет значения: (((N xor Z) xor Q) xor Z) xor Q = N. Z и Q «отменяются», даже если между парами существуют промежуточные XOR .

Answer 2

Оператор XOR имеет свойство (a ^ a) == 0 и (по расширению), что (a ^ b ^ a) == b.Следовательно, любое значение, которое встречается четное число раз, будет «отменено» до нуля в «накоплении» XOR, оставляя только нечетное значение.

Answer 3

Факт первый: x XOR x - ноль.

Это следует из того факта, что 0 XOR 0 - ноль, а 1 XOR 1 - ноль.

Факт два: x XOR x XOR x ... x - ноль, где x - четное число раз.

Это следует из первого факта по индукции.

Факт третий: x XOR x XOR x ... x - это x, где x - нечетное число, если раз.

Это следует из факта два, записав выражение как

(x XOR x XOR x ... x) XOR x = 0 XOR x = x

где в скобках есть 2n терминов, если в оригинале было 2n + 1 терминов.

Факт четвертый: XOR ассоциативен и коммутативен.

Это тривиально дляпроверь.

Теперь понятно, как работает этот код.Числа, которые появляются четное число раз, уменьшаются до нуля этим кодом.Единственное число, которое появляется нечетное количество раз, сокращается до этого кода.

Answer 4

^ является exclusive or operator. Оба операнда для оператора побитового исключающего ИЛИ должны иметь целочисленные типы. Оператор побитового исключающего ИЛИ сравнивает каждый бит своего первого операнда с соответствующим битом своего второго операнда. Если один бит равен 0, а другой бит равен 1, соответствующий бит результата устанавливается на 1. В противном случае соответствующий бит результата устанавливается на 0.

Если оба значения являются высокими или низкими, выходной сигнал равен 0, а во всех остальных случаях выходной сигнал равен 1.

Пример: a ^ b ^ a ^ a ^ b ^ c ^ c => (c ^ c = 0; b ^ b = 0; a ^ a = 0; Наконец, осталось с 0 ^ 0 ^ 0 ^ а = а). Таким образом, число, которое нечетное число раз повторяется среди четных повторений в последовательности, является выходным. Вы можете работать с тем же примером, взяв элементы массива.