"BitVector" (データ構造)

"BitVector"

ビット配列から構築した集合のブール値あるいはブールメンバのベクトルを表す．

詳細

  • "BitVector"は，ブールデータ等の2つの値だけを取ることができる，非常にコンパクトなデータ表現であり，集合を効率的に表すこともできる．
  • ビットの番号はBitSet等，他のビット演算と一致しているので，0は最初のビットを指す．
  • CreateDataStructure[ "BitVector",length]指定された length の新しい"BitVector"を作成する
    CreateDataStructure["BitVector",blist]TrueとFalseの要素を含むブールリスト blist から新しい"BitVector"を作成する
    Typed[x,"BitVector"]x に"BitVector"の型を与える
  • "BitVector"型のデータ構造には，以下の演算が使える．
  • ds["BitAnd",dsi]ビット単位のAndを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["BitClear",k]ds の k 番目のビットを0に設定するtime: O(1)
    ds["BitClearAll"]ds のすべてのビットを0に設定するtime: O(n)
    ds["BitCount"]ds 内の1に設定されたビットの数を返すtime: O(n)
    ds["BitGet",k]ds の k 番目のビットを得るtime: O(1)
    ds["BitInvert",k]ds の k 番目の値を反転させるtime: O(1)
    ds["BitList"]ds 内の1に設定されたビットのリストを返すtime: O(n)
    ds["BitNand",dsi]ビット単位のNandを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["BitNor",dsi]ビット単位のNorを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["BitNot",dsi]ds のビットを切り換えるtime: O(n/8)
    ds["BitOr",dsi]ビット単位のOrを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["BitSet",k]ds の k 番目のビットを1に設定するtime: O(1)
    ds["BitTest",k]ds の k 番目のビットが1に設定されている場合にはTrue，それ以外の場合にはFalseを返すtime: O(1)
    ds["BitXnor",dsi]ビット単位のXnorを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["BitXor",dsi]ビット単位のXorを使って，ds と dsi のビットを組み合せるtime: O(n/8)
    ds["Boole"]ds の設定されたビットには1の数値配列を返し，それ以外には0の数値配列を返すtime: O(n)
    ds["Capacity"]ds に保存できるビット数を返すtime: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Length"]ds に保存できるビット数を返すtime: O(1)
    ds["OffBitList"]ds の範囲内にないビットのリストを返すtime: O(n/8)
    ds["OffBitList",dsi]ds と dsi の両方で範囲内にないビットのリストを返すtime: O(n/8)
    ds["OnBitList",dsi]ds と dsi の両方で範囲内にあるビットのリストを返すtime: O(n/8)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (3)

新しい"BitVector"は，CreateDataStructureを使って作成できる：

20番目のビットを1に設定する：

ビットが設定されているかどうかを検証することは可能である：

ビットを抽出する：

ビットを反転させる：

設定されたビットのリストを得る：

式バージョンの ds を返す：

通常のリストを使って新しい"BitVector"を作成することができる：

2つが等しいことを確かめる：

データ構造の可視化を生成することができる：

共通のビットについて調べる：

両方にあるビット：

両方にないビット：

組み合せる：

"BitVector"は，両方にあるビットだけを含む：

スコープ  (1)

情報  (1)

新しい"BitVector"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

特性と関係  (3)

"BitVector"におけるビットの番号は，PowerおよびBitSet等のビット演算と一貫している：

ビットベクトルを2つ作成する：

どちらのビットベクトルもゼロで初期化される：

等価性はSameQを使って検証できる：

ビットを設定して，ビットベクトルの1つを変更する：

2つのビットベクトルはもはや等しくはない：

不等性はUnsameQを使って検証できる：

ビットベクトルを作成する：

ビットに対応する0と1の値の配列を得る：

ビットが設定されている場合には，配列の値は1であり，それ以外の場合は0である：

これは，ブールリストにブールを適用することに等しい：