5

BitSetsを使用してJavaでプログラムを実装していますが、次の操作でスタックしています。

N個のビットセットが与えられた場合、すべてのビットセットに1つ以上ある場合は0のビットセットを返し、それ以外の場合は1を返します。

例として、次の3つのセットがあるとします。

  • 10010
  • 01011

  • 00111

  • 11100期待される結果

次のセットの場合：

  • 10010
  • 01011
  • 00111
  • 10100

  • 00101

  • 01000期待される結果

私はこれをビット単位の演算で排他的にしようとしていますが、必要なのは文字通り排他的またはすべてのセット間であることに気づきましたが、反復的な方法ではないため、何をすべきか非常に困惑しています。これも可能ですか？

各セットの各ビットをチェックし、各位置にカウンターを保持するというコストのかかる解決策を避けたかったのです...

助けてくれてありがとう

編集：一部の人が尋ねたように、これは私が取り組んでいるプロジェクトの一部です。私はタイムテーブルジェネレータを構築していますが、基本的にソフトな制約の1つは、1日に1つのクラスしかないということです。したがって、これらのセットは1時間に出席する生徒を表し、クラスが1つしかない生徒をフィルタリングしたいと思います。 。

4

2 に答える 2

4

2つの値でやりたいことができます。1つはビットが少なくとも1回設定され、もう1つはビットが複数回設定されています。この組み合わせを使用して、これらのセットを1回だけ決定できます。

int[] ints = {0b10010, 0b01011, 0b00111, 0b10100, 0b00101};
int setOnce = 0, setMore = 0;
for (int i : ints) {
    setMore |= setOnce & i;
    setOnce |= i;
}
int result = setOnce & ~setMore;
System.out.println(String.format("%5s", Integer.toBinaryString(result)).replace(' ', '0'));

プリント

01000
于 2012-04-30T18:42:30.427 に答える
1

まず第一に、各セットのすべてのビットをチェックせずにこれを行うことはできません。任意のビットをチェックせずにこの質問を解決できる場合、それは2つの解決策が存在することを意味します（つまり、そのビットが存在する可能性のある2つの値のそれぞれに対して2つの異なる解決策があります）。

複数のビットセットのXORをより効率的に計算する方法が必要な場合は、個々のビットのセットではなく、整数としてセットを表すことを検討します。次に、整数をXORして、答えを見つけます。そうでなければ、各ビットを反復処理し、その値を確認し、（質問で説明したように）自分で解を計算する必要があるように思われます。

于 2012-04-30T18:05:32.010 に答える