Проверьте, установлен ли бит только один раз в серии битов

Я пытаюсь найти способ правильного подхода к достижению этого: Представьте, что у нас есть группа бит-наборов:

Я бы хотел проверить, какой из бит устанавливается только один раз во всех битах. В этом примере результатом будет:

так как четвертый бит является единственным, который появляется только один раз во всех сериях.

Каким будет лучший подход, выполнив побитовые логические операции?

Спасибо заранее.

Ответ 1

Вы можете использовать один-два раза:

для каждой коллекции
- для каждого элемента
  - если элемент находится в наборе once
    - добавьте его в набор twice
  - еще
    - добавьте его в набор once
return once - twice

Фокус в том, что он может выполняться параллельно:

для каждой коллекции C
- twice: = twice ИЛИ (once И C)
- once: = once ИЛИ C

Реализация может выглядеть так:

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;

Ответ 2

Как вы можете видеть, вы не можете сделать это, используя один набор для хранения промежуточных результатов, потому что вам нужно различать три состояния для каждого бита: никогда не устанавливать, устанавливать один раз и устанавливать более одного раза.

Итак, вам нужно как минимум 2 промежуточных результата. Например, вы можете отслеживать биты, установленные как минимум один раз, и биты, заданные более одного раза отдельно:

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

Или используя BitSet (он выглядит не очень элегантным, потому что BitSet не является неизменным):

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;

Ответ 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