Or of all pairs formed by taking xor of all the numbers in a list.
eg : 10,15,17
ans = (10^15)|(15^17)|(10^17) = 31 . i have made an o(n*k) algo but need something better than that(n is number of entries and k is no. of bits in each number) .
It may be easiest to think in negatives here.
XOR is basically "not equal to"--i.e., it produces a result of 1 if and only if the two input bits are not equal to each other.
Since you're ORing all those results together, it means you get a 1 bit in the result anywhere there are at least two inputs that have different values at that bit position.
Inverting that, it means that we get a zero in the result only where every input has the same value at that bit position.
To compute that we can accumulate two intermediate values. For one, we AND together all the inputs. This will give us the positions at which every input had a one. For the other, we invert every input, and AND together all those results. This will tell us every position at which all the inputs had the value 0.
OR those together, and we have a value with a 1 where every input was equal, and a zero otherwise.
Invert that, and we get the desired result: 0 where all inputs were equal, and 1 where any was different.
This lets us compute the result with linear complexity (assuming each input value fits into a single word).