c++ - C/C++中的按位运算 : ORing all XOR'd pairs in O(N)

Question

我需要对每个 possible pair of elements 进行异或运算在一个数组中，然后将这些结果放在一起。是否可以在 O(N) 中执行此操作？

例子:-

如果列表包含三个数字10,15 & 17，那么一共有3对:

d1=10^15=5;

d2=10^17=27;

d3=17^15=30;

k= d1 | d2 | d3 ;

K=31

Answer 1

实际上，它比 Tanmay 建议的还要容易。

事实证明，大多数对都是冗余的:(A^B)|(A^C)|(B^C) == (A^B)|(A^C) 和(A^B)|(A^C)|(A^D)|(B^C)|(B^D)|(C^D) == (A^B)|(A^C )|(A^D) 等。因此，您可以将每个元素与第一个元素进行异或运算，然后对结果进行或运算:

result = 0;
for (i=1; i<N;i++){
   result|=data[0]^data[i];
}