Объясните с помощью xor, чтобы найти два не дублируемых целых числа в массиве

Учитывая [1,1,4,5,5,6] мы можем найти 4 и 6 как неповторяющиеся целые числа.

Существует решение, использующее XOR.

Вот алгоритм, предложенный автором:

#include <stdio.h>
#include <stdlib.h>

/* This finction sets the values of *x and *y to nonr-epeating
 elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  *x = 0;
  *y = 0;

  /* Get the xor of all elements */
  for(i = 1; i < n; i++)
   xor ^= arr[i];

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < n; i++)
  {
    if(arr[i] & set_bit_no)
     *x = *x ^ arr[i]; /*XOR of first set */
    else
     *y = *y ^ arr[i]; /*XOR of second set*/
  }
}

Я смущен относительно того, что следует после 4^6. Я смущен, как работает set_bit_no (включая мотивацию) и что-то в этом set_bit_no.

Может кто-нибудь попытаться объяснить это более простым английским языком? Благодарю.

Ответ 1

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

a xor a = 0
[a, b, c, b, d, a]
a xor b xor c xor b xor d xor a = c xor d

Теперь в c xor d единственными установленными битами являются биты, которые различаются по c и d. Пусть говорят, что 3-й бит установлен в c xor d. Это означает, что если бит 3 равен 0 в c, это будет 1 в d или наоборот.

Итак, если мы разделим все числа в 2-х группах, то один, который содержит все числа с битом 3, равен 0, а другой, в котором бит 3 равен 1, c и d, определенно перейдут в разные группы. И все пары одинаковых чисел будут одинаковыми. (Бит 3 равен либо 1, либо для a, либо для 0 в обоих случаях: a)

Пусть говорят, что группы

[a c a] and [b d b]
xoring them
a xor c xor a = c (The first number)
b xor d xor b = d (The second number)

Другие возможности групп

[c] and [a b d b a]
xoring them
c = c (The first number)
a xor b xor d xor b xor a = d (The second number)

а также

[a b c b a] and [d]
xoring them
a xor b xor c xor b xor a= c (The first number)
d = d (The second number)

Около

set_bit_no = xor & ~(xor-1);

Если входной массив состоял из натуральных чисел, xor был бы положительным xor & ~ xor равен нулю (определение, поскольку все биты инвертированы). При вычитании 1 из xor,

Если правый бит был равен нулю, он будет установлен в 1 и выйдет
Сбросьте правый бит до нуля и попытайтесь добавить 1 к следующему бит (шаг 1)

Короче говоря, все самые правые биты, которые были равны 1, станут нулевыми (инвертированными назад, аналогичными xor), а первый (самый правый) нулевой бит станет 1 (такой же, как xor). Теперь, когда все биты, оставшиеся от этого нового набора 1 бит, различаются в xor и ~ (xor-1), поэтому они будут генерировать 0, все биты прямо к этому новому набору 1 бит равны нулю как в xor, так и в ~ (xor- 1), поэтому они будут генерировать 0. Только бит в битной позиции, где 1 был вновь установлен в ~ (xor-1), равен 1 в обоих случаях, поэтому только этот бит будет установлен в выражении xor & ~ (xor-1)

Ответ 2

Простым объяснением здесь является то, что когда вы делаете a^b тогда устанавливаются только эти разрядные позиции, которые имеют разные значения в от b. Поэтому, если вы группируете элементы в массиве с таким значением в определенном бите набора в a^b то a и b будут в отдельных группах как xor, группа будет отменять другие, результатом двух групп будет a и b.

Пример :-

a = 4 
b = 6 
a^b = 2

Set_bit_pos = 1

Arr = [1,1,4,5,5,6]

Grouping according to bit no 1 

x = [6] where bit1 is 1 

y = [4,1,1,5,5] where bit1 is 0

Xoring 

x = 6 

y = 4^1^1^5^5 = 4

Ответ 3

Этот алгоритм будет работать только тогда и только тогда, когда

1) elements are non-zero
2) contains no more than 2 non-repeating integers. If only 1
   non-repeating, one of the result (x or y) will be 0.
3) the repeated numbers occurs in pairs (ie. 2,4,6....)

Если 0 - возможное число, то вы не можете различать найденный ответ или отсутствие ответа.

Путем XORing всех элементов это дает разницу между двумя неповторяющимися целыми числами (т.е. 4 ^ 6 в вашем примере). Это связано с тем, что все остальные элементы повторяются (т.е. Даже количество раз) и в XOR, они отменяют себя. Важно отметить, что XOR является коммутативным (т.е. Порядок не имеет значения a ^ b = b ^ a)

Теперь set_bit_no. Это просто сохраняет правильный бит бит или xor. Почему именно право? Потому что это легко получить, я думаю. Но любой набор бит будет делать. Установленные биты в переменной xor содержат биты, где они различаются между 4 и 6.

100 ^ 110 = 010

Второй бит равен 1, потому что единственный бит отличается от 4 до 6. Аналогично, разница между 3 и 8

0011 ^ 1000 = 1011

который показывает 4, 2 и 1 бит, различаются между 3 и 8.

Причина получения набора бит и использование его в if состоит в том, чтобы убедиться, что ответы (4 и 6) записаны в другую переменную (x или y). Почему это работает? Поскольку set bit гарантирует, что два ответа будут содержать разные значения в этой позиции бита.

if(arr[i] & set_bit_no)

Ответ 4

Когда вы xor два равных значения, они отменяют. Это позволяет выявить неповторяющуюся пару.

XOR(aabbccddeeffgh) = XOR(gh) = ...1...

Зная любой бит, по которому g и h отличаются, позволяют установить g и h сторону двух подмножеств:

...0... => XOR(aabbcceeg) = g

...1... => XOR(ddffh) = h