C++

Forum

 
Bitwise operations: get non-repeating bits

mdonati (14)
Hi to everyone.

I'm really stuck with it.
I have an array of 9 ints (9 bits each). One, and only one, of these will always include 1 or 2 bits that the other variables don't have set. I need to achieve the following:

1. What is the index of the variable having these non-repeating bits?
2. What is the number formed by these bits?

For example, let's say I have an array with 3 ints (the rest of the elements are all 0):

010 000 110 at index 2
101 000 100 at index 4
010 000 010 at index 6

In the int at index 4 I have that bits 1 and 3 are set only in this variable.
So, I need to perform an operation to let me know that it's the variable at index 4 and the number is 101000000.
It may sound like a homework, but it's really not.
I tried many bitwise operations and combinations of them, but I really can't get the result.

Thanks for reading this.



jsmith (5804)
I can give you an O(n) c=2 answer trivially. But first, what is this for?
mdonati (14)
It's for a sudoku bitsolver to find a finned fish strategy.
jsmith (5804)
This deals with only 8 bit numbers and runs in O(n) with c = 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>

int a[9] = { 192, 68, 146, 54, 57, 132, 52, 80, 4 };

/*
1100 0000
0100 0100
1001 0010
0011 0110
0011 1001
1000 0100
0011 0100
0101 0000
0000 0100
*/

int main() {
    int one_user = 0;
    int two_users = 0;
    int idx = 0;

    for( size_t i = 0; i < 9; ++i )
    {
        two_users |= one_user & a[i];
        one_user |= a[i];
        one_user &= ( ~two_users & 0xFF );
        if( a[i] & one_user )
            idx = i;
    }

    std::cout << std::hex << one_user << ' ' << idx << std::endl;
}


EDIT: there might be bugs. I only tested with the data set hard coded.
Last edited on
Topic archived. No new replies allowed.