Sprawdź, czy bit jest ustawiony tylko raz w serii bitsets

Question

Staram się znaleźć sposób, co jest prawidłowe podejście do osiągnięcia tego celu: Wyobraźmy sobie, że mamy grupę zestawów bitowych, jak następuje:

00100 
00101 
10000 
00010 
10001 

Chciałbym przetestować, który z bitów jest ustawiony tylko raz we wszystkich zestawach bitowych. W tym przykładzie wynik będzie następujący:

00010 

ponieważ czwarty bit jest jedynym, który pojawia się tylko raz we wszystkich seriach.

Jakie byłoby najlepsze podejście do wykonywania bitowych operacji logicznych?

Z góry dziękuję.

Answer 1

można użyć raz-dwa razy podejścia:

• dla każdej kolekcji
  • dla każdego elementu
    • jeśli element jest w once ustawić
      • dodać go do twice ustawić
    • inny
      • dodać go do once ustawić
• powrotu once - twice

Trick jest to, że mogą być wykonywane równolegle:

• każdej kolekcji C
  • twice: = twice OR (once I C)
  • once: = once OR C

Realizacja mogłaby wyglądać następująco:

BitSet once = new BitSet(); 
BitSet twice = new BitSet(); 
for(BitSet b : sets){ 
    BitSet mask = (BitSet) b.clone(); 
    mask.and(once); 
    twice.or(mask); 
    once.or(b); 
} 
once.andNot(twice); 
return once; 

Answer 2

Jak widać, nie można tego zrobić przy użyciu jednego zestawu do przechowywania wyników pośrednich, ponieważ trzeba rozróżnić 3 stany dla każdego bitu: nigdy nie ustawiać, ustawiać raz i ustawiać więcej niż jeden raz.

Potrzebujesz co najmniej 2 wyników pośrednich.Na przykład, można śledzić bity ustawione przynajmniej raz, a bity ustawić więcej niż jeden raz oddzielnie:

int atLeastOnce = 0; 
int moreThanOnce = 0; 
for (int current: sets) { 
    moreThanOnce |= (atLeastOnce & current); 
    atLeastOnce |= current; 
} 
int justOnce = atLeastOnce & ~moreThanOnce; 

lub używając BitSet s (to nie wygląda tak elegancko, bo BitSet nie jest niezmienna):

BitSet atLeastOnce = new BitSet(); 
BitSet moreThanOnce = new BitSet(); 
for (BitSet current: sets) { 
    BitSet moreThanOnceInCurrent = (BitSet) atLeastOnce.clone(); 
    moreThanOnceInCurrent.and(current); 
    moreThanOnce.or(moreThanOnceInCurrent); 
    atLeastOnce.or(current); 
} 
atLeastOnce.andNot(moreThanOnce); 
BitSet justOnce = atLeastOnce; 

Answer 3

int length = 5; 
int count[] = new int[length]; 
for (i = 0; i < bitset.length(); i++) { 
    int value = bitset[i]; 
    unsigned int count = 0; 

    for (int j = 0; j < length; j++) {   // until all bits are zero 
     if ((value & 1) == 1)  // check lower bit 
      count[j]++; 
     value >>= 1;    // shift bits, removing lower bit 
    } 
} 

int number = 00000; 
for (int k = 0; k < 5; k++) { 
    if (count[k] == 1) 
     number = number | 1; 
    number >>= 1; 
} 

number is desired answer