Базовый алгоритм XOR

Опубликовано: 27 Февраля, 2023

Операцию XOR между двумя числами P и Q можно рассматривать иначе, как побитовую сумму по модулю 2 битов P и Q. Рассмотрим P = 10010 и Q = 00110 .

Начиная с крайнего левого, мы проверяем приведенное выше утверждение:

  • (1 + 0) % 2 = 1
  • (0 + 0) % 2 = 0
  • (0 + 1) % 2 = 1
  • (1 + 1) % 2 = 0
  • (0 + 0) % 2 = 0

Двоичное число имеет форму вектора ℤ 2 d , где d — количество битов в двоичном числе, а 2 — допустимые целые значения в векторе, а именно {0, 1}. Итак, результатом операции XOR между двумя числами P и Q является сложение векторов по модулю 2 двух ℤ 2 d векторов P и Q .

П + Q = П ⊕ Q

Для вычитания Q, XOR с Q на RHS, чтобы получить P на RHS,

П = П ⊕ Q ⊕ Q

П = П

Теперь, имея массив A из N неотрицательных целых чисел, нам нужно найти базис B для элементов массива, представленных в виде ℤ 2 d векторов в виде битовой маски.

Некоторые моменты, на которые следует обратить внимание –

  • Размер базиса B для d-мерного векторного пространства не может превышать d.
  • Базисные векторы независимы, т. е. ни один из них не может быть выражен как линейная комбинация подмножества базисных векторов (кроме самого вектора).

Алгоритм выглядит следующим образом:

  • Assume we have the basis for all the vectors till index ‘i‘ (i < N) and we need to check if A[i + 1] can be represented as a linear combination of current basis vectors.
  • If not so, then add A[i + 1] to our basis, otherwise increment the index. We can effectively check this if we have all our basis vectors differ by the first set bit index (from left), let’s denote it by msb(B[j]).
  • Start checking from the left bits, if index ‘s’ is set in current value of A[i + 1] and there is no basis vector with msb(B[j]) = s, then no linear combination of the existing basis vectors can represent current value of A[i + 1]. 
    • So, insert current value of A[i + 1] in the basis. 
    • Otherwise, subtract B[j] with msb = s from A[i + 1] by XORing with B[j] and continue with other bits. 
    • If at end A[i + 1] is a null vector, then it can be represented as linear combination of the current basis vectors, otherwise not and has to be inserted in the basis.

Примеры:

Input: N = 5, A = {2, 5, 11, 9, 20}
Output: {5, 2, 12, 24}
Explanation: Given input = 2(00010), 5(00101), 11(01011), 9(01001), 20(10100) 
and basis = {0, 0, 0, 0, 0}, considering d = 5(for simplicity)
For i = 0, A[i] = 2(00010), first set bit is 1st bit,  basis[1] = 0,  
So basis becomes {0, 2, 0, 0, 0}
For i = 1, A[i] = 5(00101), first set bit is 0th bit,  basis[0] = 0,  
So basis becomes {5, 2, 0, 0, 0}
For i = 2, A[i] = 11(01011), first set bit is 0th bit, basis[0] = 5,  
So A[i] = 11 ^ 5 = 14(01110)
Now A[i] = 14(01110), first set bit is 1st bit, basis[1] = 2,  
So A[i] = 14 ^ 2 = 12(01100)
Now A[i] = 12(01100), first set bit is 2nd, basis[2] = 0,  
So basis becomes {5, 2, 12, 0, 0}
For i = 3, A[i] = 9(01001), first set bit is 0th bit, basis[0] = 5,  
So A[i] = 9 ^ 5 = 12(01100)
Now A[i] = 12(01100), first set bit is 2nd bit, basis[2] = 12,  
So A[i] = 12 ^ 12 = 0(00000)
For i = 4, A[i] = 20(10100), first set bit is 2nd bit, basis[2] = 12,  
So A[i] = 20 ^ 12 = 24(11000)
Now A[i] = 24(11000), first set bit is 3rd, basis[3] = 0,  
So basis becomes {5, 2, 12, 24, 0}
So XOR Basis is {5, 2, 12, 24}

Input: N = 7, A = {5, 16, 7, 18, 34, 24, 9}
Output: {5, 2, 12, 24, 16, 32}

Ниже приведена реализация вышеуказанного подхода

Временная сложность: O(N * d)
Вспомогательное пространство: O(d)

РЕКОМЕНДУЕМЫЕ СТАТЬИ