An efficient method using only bit operations
We are assigned binary numbers n
, each of the bits k
. We need to find a binary number of bits k
in which the i
th bit is set only if the i
th bit was set to exactly one of the binary numbers n
. For example,
0010 0011 0100 1110
must give 1001
as an answer. You only need to use bit measures for 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 a variable answer
. It uses a total of 7
bitwise operations (1 xor
, 1 or
, 2 negation
, 3 and
) per iteration, doing a total of operations 7*n
. My question is whether the number of operations can be further reduced.
source to share
To get a definitive 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 calculated 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;
These are just three operations in a loop.
source to share