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

Question

Я пытаюсь понять бинарные операторы в C # или вообще, в частности ^ - эксклюзив или .

Например:

Задан массив натуральных чисел. Все числа встречаются четное число раз, кроме одного числа, которое встречается нечетное количество раз. Найти число в O (n) времени и постоянном пространстве.

Это можно сделать с помощью ^ следующим образом: Сделайте битовое XOR для всех элементов. Наконец, мы получаем число, которое имеет странные вхождения.

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

Когда я делаю:

int res = 2 ^ 3;  
res = 1;  
int res = 2 ^ 5;  
res = 7;  
int res = 2 ^ 10;  
res = 8;  

Что на самом деле происходит? Каковы другие немного магии? Любую ссылку я могу посмотреть и узнать о них больше?

Answer 1

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

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

 decimal | binary | expanded
       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 и других побитовых операциях.

Например: 0011 - биты 1 и 2 включены, а биты 4 и 8 выключены. Который представлен как десятичное значение 3 для обозначения включенных битов и отображается в развернутом виде как 1+2.

---

Что касается логики XOR, вот несколько примеров.
Из оригинального поста

2 ^ 3 = 1

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

2 ^ 5 = 7

• 2 не является членом 1 + 4 (5) add 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 является членом самого себя удалить 4 = 0

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

• (1 ^ 2) 1 не является членом 2 добавить 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 удалить 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 добавить 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) удалить 4 = 1 + 8 (9 )
• (9 ^ 10) 8 является членом 2 + 8 (10) удалить 8 = 2
  • 1 не является членом 2 + 8 (10) add 1 = 1 + 2 (3 )

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

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

Answer 2

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

Затем вы можете применить таблицу истинности для вашего конкретного оператора.,Он действует на каждую пару битов, имеющих одинаковую позицию в двух операндах (одинаковое значение места).Таким образом, самый левый бит (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.

Answer 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 (свойство самообращения).И любой 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.

Самообращенный: Для любого 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's go away)

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

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

0 * x = 0
1 * x = x

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

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

Answer 4

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

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

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

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

Answer 5

Это основано на простом факте, что XOR числа с самим собой приводит к нулю.

, а XOR числа с 0 приводит к получению самого числа.

Итак, если мы имееммассив = {5,8,12,5,12}.

5 встречается 2 раза.8 встречается 1 раз.12 встречается 2 раза.

Мы должны найти число, встречающееся нечетное количество раз.Ясно, что 8 - это число.

Мы начинаем с res = 0 и XOR со всеми элементами массива.

int res=0; for(int i:array) res = res ^ i;

    1st Iteration: res = 0^5 = 5
    2nd Iteration: res = 5^8 
    3rd Iteration: res = 5^8^12
    4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12
    5th Iteration: res = 8^12^12 = 8^0 = 8

Answer 6

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

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

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

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

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

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

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

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

Answer 7

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

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

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

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

Теперь, когда мы доказали вышеизложенное, давайте посмотрим, что произойдет, если мы 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-последовательности вы получите число, которое не повторяется (или повторяется четное число раз).