C/C++中的按位运算:对O(N)中的所有XOR对进行OR运算

Question

我需要对数组中每个可能的元素对进行异或,然后将这些结果一起进行OR运算.是否可以在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)等,所以你可以使用XOR第一的每个元素,并且或结果:

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