Efficient method using only bit-wise operations

Question

We are given n binary numbers, each of k bits. We need to find a k bit binary number in which ith bit is set only if the ith bit was set in exactly one of the n given binary numbers. For example,

should give 1001 as answer.You need to only use bit-wise operations to achieve this. Here is my solution:

unsigned int array[n];//we have our 'n' numbers here
unsigned int answer=0,rxor=0,t1,t2;
for(int i=0; i<n; ++i)
{
     t1 = answer;
     answer ^= array[i];
     t2 = (~t1) & answer;
     answer &= ~(t2 & rxor);
     rxor |= array[i];
}

The final answer will be stored in the answer variable. It uses a total of 7 bit-wise operations( 1 xor, 1 or, 2 negation, 3 and ) per iteration, making a total of 7*n operations. My question is, can the number of operations can be reduced further.

cmaster - reinstate monica · Accepted Answer · 2014-08-02 06:41:10Z

10

To derive the final answer, you need to know which bits have been used at least once, and which have been used at least twice. These two conditions can be computed very quickly:

unsigned usedOnce = 0;
unsigned usedTwice = 0;
for(int i = 0; i < n; i++) {
    usedTwice |= usedOnce & array[i];
    usedOnce |= array[i];
}
unsigned answer = usedOnce & ~usedTwice;

That's only three operations in the loop.

answered Aug 2, 2014 at 6:41

cmaster - reinstate monica

41.1k9 gold badges69 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Efficient method using only bit-wise operations

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related