Что означает побитовое XOR (исключительное ИЛИ)?

Ответ 1

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

Затем вы можете применить таблицу прав для своего конкретного оператора. Он действует на каждую пару бит, имеющих одну и ту же позицию в двух операндах (одно и то же значение места). Таким образом, самый левый бит (MSB) A объединяется с MSB B для получения MSB результата.

Пример: 2^10:

    0010 2
XOR 1010 8 + 2
    ----
    1    xor(0, 1)
     0   xor(0, 0)
      0  xor(1, 1)
       0 xor(0, 0)
    ----
 =  1000 8

И результат 8.

Ответ 2

Я знаю, что это довольно старый пост, но я хотел упростить ответ, так как я наткнулся на него, ища что-то еще.
XOR (eXclusive OR/or or) можно перевести просто как включить/выключить.
Это будет либо исключать, либо включать указанные биты.

Используя 4 бита (1111), получаем 16 возможных результатов от 0-15:

 0: 0000
 1: 0001
 2: 0010
 3: 0011 (1+2)
 4: 0100
 5: 0101 (1+4)
 6: 0110 (2+4) 
 7: 0111 (1+2+4)
 8: 1000
 9: 1001 (1+8)
10: 1010 (2+8)
11: 1011 (1+2+8)
12: 1100 (4+8)
13: 1101 (1+4+8)
14: 1110 (2+4+8)
15: 1111 (1+2+4+8)

Что касается того, что происходит с логикой XOR, вот несколько примеров
Из исходного сообщения

2 ^ 3= 1

• 2 является членом 1 + 2 (3) удалить 2 = 1

2 ^ 5= 7

• 2 не является членом 1 + 4 (5) добавить 2 = 1 + 2 + 4 (7)

2 ^ 10= 8

• 2 является членом 2 + 8 (10) удалить 2 = 8

Другие примеры

1 ^ 3= 2

• 1 является членом 1 + 2 (3) удалить 1 = 2

4 ^ 5= 1

• 4 является членом 1 + 4 (5) удалить 4 = 1

4 ^ 4= 0

• 4 - это сам элемент remove 4 = 0

1 ^ 2 ^ 3= 0
Логика: ((1 ^ 2) ^ (1 + 2))

• (1 ^ 2) 1 не является членом 2 add 2 = 1 + 2 (3)
• (3 ^ 3) 1 и 2 являются членами 1 + 2 (3) удаляют 1 + 2 (3) = 0

1 ^ 1 ^ 0 ^ 1= 1
Логика: (((1 ^ 1) ^ 0) ^ 1)

• (1 ^ 1) 1 является членом 1 remove 1 = 0
• (0 ^ 0) 0 является членом 0 удалять 0 = 0
• (0 ^ 1) 0 не является членом 1 add 1 = 1

1 ^ 8 ^ 4= 13
Логика: ((1 ^ 8) ^ 4)

• (1 ^ 8) 1 не является членом 8 add 1 = 1 + 8 (9)
• (9 ^ 4) 1 и 8 не являются членами 4 add 1 + 8= 1 + 4 + 8 (13)

4 ^ 13 ^ 10= 3
Логика: ((4 ^ (1 + 4 + 8)) ^ (2 + 8))

• (4 ^ 13) 4 является членом 1 + 4 + 8 (13) remove 4 = 1 + 8 (9)
• (9 ^ 10) 8 является членом 2 + 8 (10) удалять 8 = 2
  • 1 не является членом 2 +8 (10) добавить 1 = 1 + 2 (3)

4 ^ 10 ^ 13= 3
Логика: ((4 ^ (2 + 8)) ^ (1 + 4 + 8))

• (4 ^ 10) 4 не является членом 2 + 8 (10) добавить 4 = 2 + 4 + 8 (14)
• (14 ^ 13) 4 и 8 являются членами 1 + 4 + 8 (13) удалять 4 + 8= 1
  • 2 не является членом 1 + 4 + 8 (13) добавить 2 = 1 + 2 (3)

Ответ 3

Другой способ показать это - использовать алгебру XOR; вам не нужно ничего знать о отдельных битах.

Для любых чисел x, y, z:

XOR является коммутативным: x ^ y == y ^ x

XOR ассоциативен: x ^ (y ^ z) == (x ^ y) ^ z

Тождество равно 0: x ^ 0 == x

Каждый элемент является собственным инверсным: x ^ x == 0

Учитывая это, легко доказать указанный результат. Рассмотрим последовательность:

a ^ b ^ c ^ d ...

Так как XOR является коммутативным и ассоциативным, порядок не имеет значения. Поэтому соберите элементы.

Теперь любые смежные идентичные элементы x ^ x можно заменить на 0 (self-inverse property). И любой 0 можно удалить (потому что это тождество).

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

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

[обновление]

Заметим, что это доказательство требует только определенных предположений об операции. В частности, предположим, что множество S с оператором . обладает следующими свойствами:

Ассоциативность: x . (y . z) = (x . y) . z для любых x, y и z в S.

Идентичность: существует единственный элемент e такой, что e . x = x . e = x для всех x в S.

Закрытие: для любых x и y в S, x . y также находится в S.

Self-inverse: для любого x в S, x . x = e

Как оказалось, нам не нужно предполагать коммутативность; мы можем это доказать:

(x . y) . (x . y) = e  (by self-inverse)
x . (y . x) . y = e (by associativity)
x . x . (y . x) . y . y = x . e . y  (multiply both sides by x on the left and y on the right)
y . x = x . y  (because x . x = y . y = e and the e go away)

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

Но @Steve Jessup доказал, что я ошибаюсь в комментариях. Если вы определяете скалярное умножение на {0,1} следующим образом:

0 * x = 0
1 * x = x

... тогда эта структура удовлетворяет всем аксиомам векторного пространства над целыми числами mod 2.

Таким образом, любая такая структура изоморфна множеству векторов бит по компонентному XOR.

Ответ 4

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

• для каждого бита в первом значении, переключите бит, если соответствующий бит во втором значении установлен

Чистый эффект заключается в том, что один бит начинается с false, и если общее число "переключений" равно, оно все равно будет false в конце. Если общее число "переключений" нечетное, оно будет true в конце.

Просто подумайте "крошечный массив логических значений", и он начнет иметь смысл.

Ответ 5

Определение оператора XOR (исключающее ИЛИ) над битами заключается в следующем:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Один из способов представить это - это сказать, что "1" с правой стороны изменяет бит с левой стороны, а 0 с правой стороны не изменяет бит слева. Однако XOR коммутативен, поэтому то же самое верно, если стороны обращены. Поскольку любое число может быть представлено в двоичной форме, любые два числа могут быть XOR-ed вместе.

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

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

0 XOR 0 = 0
1 XOR 1 = 0

Итак, если вы XOR число на себя, вы всегда получаете 0 (верьте или нет, но это свойство XOR было использовано компиляторами, когда 0 необходимо загрузить в регистр CPU. бит, чем явно вставлять 0 в регистр. Компилятор просто выводит код сборки для XOR для регистрации на себя).

Теперь, если X XOR X равно 0, а XOR ассоциативно, и вам нужно выяснить, какое число не повторилось в последовательности чисел, где все остальные числа были повторены два (или любое другое нечетное число раз). Если бы у нас были повторяющиеся числа вместе, они будут XOR равными 0. Все, что XOR-ed с 0, останется само собой. Таким образом, из XOR-ing такой последовательности вам будет оставлено число, которое не повторяется (или повторяет четное число раз).

Ответ 6

В этом есть много примеров различных функций, выполненных бит-биткой. Некоторые из них могут быть довольно сложными, поэтому будьте осторожны.

Что вам нужно для понимания бит-операций, по крайней мере, это:

• входные данные в двоичной форме
• таблица истинности, которая сообщает вам, как "смешивать" входы для формирования результата.

Для XOR таблица истинности проста:

1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

Чтобы получить бит n, в результате вы применяете правило к битам n в первом и втором входах.

Если вы попытаетесь вычислить 1^1^0^1 или любую другую комбинацию, вы обнаружите, что результат равен 1, если в противном случае есть нечетное число 1 и 0. Вы также обнаружите, что любое число XOR'ed с самим собой равно 0, и это не имеет значения, в каком порядке вы выполняете вычисления, например. 1^1^(0^1) = 1^(1^0)^1.

Это означает, что когда вы XOR все числа в вашем списке, те, которые являются дубликатами (или представляют четное количество раз), будут XOR равными 0, и вы останетесь с тем, которое присутствует нечетным числом раз.