1

O(1) 時間で動作する Bitvector32 のビット演算子があるかどうかを知りたかったのです。私は現在、大きなサイズの BitArray を使用しており、O(bitarray のサイズ) で動作する Bitwise And、Or、および Not を使用しています。

これについてインターネットで検索しましたが、答えが見つかりませんでした。ここの人々が助けてくれることを願っています！

4

2 に答える 2

3

a が常に正確に 32 ビットであることを考えると、BitVector32さまざまなサイズについて説明する必要はありません。では、どのような操作をデータのサイズで表すことができるのでしょうか?

個人的には、これほどBitVector32快適な型を見つけたことはありません。UInt32通常は、32 ビットを表す a に固執し、通常の&, |etc 演算子を使用します。

BitArrayyourを一連の値に置き換えることを考えている場合BitVector32でも、各操作を O(n) にすることになります。基本的に、元の値と操作を実際に保存し、操作の実際の適用を延期しない限り、これを回避することは困難です。これははるかに複雑になり、結果のごく一部にしかアクセスしない場合にのみ、結果が改善されます。

于 2012-05-24T05:53:16.957 に答える
3
  • BitVector32 を int に変換するのは O(1) 操作です。（参考）
  • int を BitVector32 に変換するのは O(1) 操作です。（参考）
  • int に対してビット演算を実行することは、O(1) 演算です。

したがって、

var vectorAnd = new BitVector32(vector1.Data & vector2.Data);
var vectorOr = new BitVector32(vector1.Data | vector2.Data);
var vectorNot = new BitVector32(~vector1.Data);

すべて O(1) 操作です。

于 2012-05-24T05:55:18.473 に答える