10

これを達成するための正しいアプローチは何かを見つけようとしています: 次のようなビットセットのグループがあると想像してください:

00100
00101
10000
00010
10001

すべてのビットセットで一度だけ設定されるビットをテストしたいと思います。この例では、結果は次のようになります。

00010

4 番目のビットは、すべてのシリーズで 1 回だけ表示される唯一のビットであるためです。

ビットごとの論理演算を行うことによる最良のアプローチはどれですか?

前もって感謝します。

4

3 に答える 3

10

ご覧のとおり、中間結果を格納するために単一のセットを使用してそれを行うことはできません。これは、ビットごとに 3 つの状態 (決してセットしない、一度セットする、複数回セットする) を区別する必要があるためです。

したがって、少なくとも 2 つの中間結果が必要です。たとえば、少なくとも 1 回設定されたビットと複数回設定されたビットを別々に追跡できます。

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

または s を使用します (は不変ではない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;
于 2013-04-09T09:06:53.923 に答える
4

1 回 2 回のアプローチを使用できます。

  • コレクションごとに
    • 要素ごとに
      • 要素がonceセット 内にある場合
        • twiceセットに追加
      • そうしないと
        • onceセットに追加
  • 戻るonce-twice

ここでの秘訣は、並行して実行できることです。

  • コレクションごとにC
    • twice:= twiceOR ( onceAND 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;
于 2013-04-09T09:09:51.530 に答える
1 
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
于 2013-04-09T09:13:47.610 に答える