OR of pairwise XOR

Question

Can anyone suggest me a O(n) algorithm for OR the result of pairwise XOR operations on N numbers for example let N=3 and numbers be 5,7 and 9

5 ^ 7 = 2,  7 ^ 9 = 14,  9 ^ 5 = 12
2|14|12 = 14

^ for XOR operation and | for OR operation

Answer 1

If A[i] differs from A[j] in k-th bit then:
either A[i] differs from A[1] in k-th bit
or A[j] differs from A[1] in k-th bit
So, N operations are enough:

// A[i] = array of source numbers, i=1..N
Result = 0
for i = 2 to N
    Result = Result OR (A[i] XOR A[1])
print(Result)

Answer 2

The bits are independent, so you can compute the result for each bit separately.

So given a sequence of bits, we want to now the OR of all pairswise XORs. The OR is 1 iif at least one of the bitwise XORs is 1. This is the case iif you have at least one 0 and at least one 1 in your input sequence. It is very easy to check whether this is the case.

Total time: O(wN) where w is the maximum bit length of any of your input numbers.

Assuming that w is smaller than the word size, we can also solve it in O(N): Just solve all bits in parallel:

have_one = 0
have_zero = 0
for x in input:
    have_one |= x
    have_zero |= ~x
return have_one & have_zero

have_one has a bit set exactly at those positions where we have a 1 somewhere in the input. have_zero has a bit set exactly at those positions where we have a 0 somewhere in the input. The result is 1 for those positions where both is the case.