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

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), Q = XOR Н.

Ровно целое присутствует нечетное число раз, так что это будет единственное число не «исчезают» из списка , Все остальные цифры присутствуют ровно в несколько раз, поэтому все они появляются в группах по 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 терминов в оригинале.

Факт 4: XOR является ассоциативным и общительным.

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

Теперь ясно, как работает этот код. Цифры, которые появляются четным числом раз, сводятся к нулю этим кодом. Единственный номер, который появляется нечетным числом раз, сводится к этому кодом.

Answer 4

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

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

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