CODEWITHSUNDEEP
c++cbit-manipulation
user3443612
user3443612

Reputation: 35

Bitwise Operation in C/C++: ORing all XOR'd pairs in O(N)

I need to XOR each possible pair of elements in an array, and then OR those results together. Is it possible to do this in O(N)?

Example:-

If list contain three numbers 10,15 & 17, Then there will be a total of 3 pairs:

d1=10^15=5;

d2=10^17=27;

d3=17^15=30;

k= d1 | d2 | d3 ;

K=31

Upvotes: 3

Views: 710

Answers (4)

AShelly
AShelly

Reputation: 35600

Acutually, it's even easier than Tanmay suggests.

It turns out that most of the pairs are redundant: (A^B)|(A^C)|(B^C) == (A^B)|(A^C) and (A^B)|(A^C)|(A^D)|(B^C)|(B^D)|(C^D) == (A^B)|(A^C)|(A^D), etc. So you can just XOR each element with the first, and OR the results:

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

Upvotes: 10

G&#225;bor Buella
G&#225;bor Buella

Reputation: 1920

You can just do what is straightforward: loop over all the pairs, 'xor' them, and 'or' the sub results. Here is a function that expects a pointer to the start of the array, and the size of the array. I typed it here without trying it, but even if it is not correct, I hope you get the idea.

unsigned int compute(const unsigned int *p, size_t size)
{
    assert(size >= 2);

    size_t counter = size - 1;
    unsigned int value = 0;

    while (counter != 0) {
        value |= *p ^ *(p + 1);
        ++p;
        --counter;
    }
    return value;
}

Upvotes: 1

Tanmay Patil
Tanmay Patil

Reputation: 7057

OR everything, NAND everything, AND both results

Finding all combinations in O(1) is obviously impossible. So the solution had to be something ad-hoc reformulation of the problem. This is a complete intuition. (I don't have proof, but it works).

I am not sure how to solve it mathematically using boolean algebra since it involves finding all combination pairs, but I'll try to explain it using Venn diagram.

Venn diagram for n = 3

The required area is exactly identical to Venn diagram of OR except for the area of AND. Therefore they have to be subtracted. If you try it with n > 3, the picture would be even clearer.

Venn diagram for n = 4

The best way to test this method would be to simulate it with algorithms which don't have to be O(1). Anyways, you can try finding a direct proof. If you find it, please kindly share it with us too. :)

As far as your question goes, I'm sure you can implement it in O(1) yourself easily.

Good luck.

Upvotes: 2

francis
francis

Reputation: 9817

Bitwise means that you only care about 1 or 0...

  • The OR phase is true if at least one "pair XOR" is true.
  • There exists only two series for which all "pair XOR" are false : 1,1,1,1,1,1,1,1 and 0,0,0,0,0,0.

The solution is therefore a for loop to test if all items are 1 or 0.

And this is O(n) !

Bye,

Upvotes: 1

Related Questions