Почему XOR возвращает отсутствующее значение в этих двух списках?

Question

Я смотрел видео на youtube относительно интервью по кодированию, и один из вопросов состоял в том, чтобы найти недостающее значение между двумя списками.Это один из подходов, которые он выбрал, но я не понимаю, как именно «а» оказывается отсутствующим значением.

def function(nums,num2):
    a = 0
    for num in nums:
        a ^= num
        print(a)
    for num in num2:
        a ^= num
        print(a,"\n")
    return a

function([1,2,3,4],[3,1,2])

Answer 1

Думайте об этом так: вы возвращаетесь (1 ^ 2 ^ 3 ^ 4) ^ (3 ^ 1 ^ 2). Ну, XOR коммутативен и ассоциативен, так что это равно (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ 4. Но x ^ x равно 0, так что это равно 4. Другими словами, пары совпадающих значений отменяются, оставляя вас с одним непревзойденным значением.

Answer 2

Когда вы XOR целое число с самим собой, вы получаете 0.

То есть, если у вас есть список [1,2,3,4] и другой список [3,1,2].Теперь вы XOR все вместе, одни и те же элементы отменяются, оставляя отличающийся один элемент.

[1,2,3,4] xor [3,1,2] = [4]

Кстати, это предполагает, что списки отличаются только одним элементом.Если нет, вы получите XOR всех различных элементов.

Answer 3

Вы должны были бы углубиться в основы того, как работает XoR на основе цифрового проектирования схем.Поэтому, если вы дадите один и тот же вход, XoR всегда будет возвращать 0, если вы соедините его с тем же входом, что и в структуре цифрового дизайна.Так, как отметил Том Карзес, другие значения обнуляются, оставляя вас с оставшимися.Есть и другие проблемы, которые можно решить с помощью XoR, такие как поиск уникального элемента в массиве, заполненном копией каждого элемента

Эта вики даст вам хорошее описание того, как работает вентиль XOR.

Answer 4

В приведенном выше решении мы берем xor всех элементов в списке.

Когда вы берете XOR двух одинаковых элементов, вы получаете 0

>>> 1^1
0

Следовательно, когда вы берете XOR всех элементов в списке, элементы, которые являются одинаковыми, аннулируются, поскольку XOR является коммутативным и ассоциативным, а элемент, который не является парным, остается.

>>> 1^2^3^4^3^1^2
4
>>> 1^1^2^2^3^3^4
4