問題タブ [bitvector]

AppleはCFBitを UInt32 として文書化していますが、私はその理由について混乱しています。各ビットが32ビットで定義されている場合、ビットベクトルを使用する目的に反しませんか? 何か不足していますか？

私は演習として Bit Vector クラスを実装している最中ですが、Rust を 1 週間も知らずにしか知りませんでした。次のコードで問題が発生しました。

アイデアはS、たとえばu8、u16、u32のいずれかu64にすることができ、 in にusize設定すると、すべてゼロで構成される のビット値が作成されるようにすることです。0with_capacityS

私が得るエラーは次のとおりです。

lib.rs:27:10: 27:50 エラー: 二項演算はタイプ[E0369]!=に適用できません lib.rs:27 (self.data[data_index] & (1 << 残り)) != 0 ^~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lib.rs:27:10: 27:50 ヘルプ: 実行詳細な説明を見るには lib.rs:27:10: 27:50 注: lib.rs:27 の実装が欠落している可能性があります (self.data[data_index] & (1 << 残り)) != 0 ^~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: aborting due to previous error error: Could not compile .<S as std::ops::BitAnd<usize>>::Output


rustc --explain E0369
std::cmp::PartialEq<S as std::ops::BitAnd<usize>>::Output


bit-vector

私は行列削減アルゴリズムを実装しています。私は数学の学生です。明らかに、私はインターネットを検索して読みましたが、探していたものを正確に見つけることはできませんでした (見つけたものと読んだ論文を最後にリストします)。

問題の簡単な概要:

• ビットベクトル b は FIXED LENGTH N です。

• b はすべてのステップで変化します (ほとんどの場合、2、3 のインデックスでのみ、またはかなり多くのインデックス (1/10 から 1/3) で、これは 10% までのケースでのみ)。

• 私はすでにスパース実装を持っています。ビットベクトルのスマートな実装を使用してコーディングしたいと思います。

  /li>

私が必要とするのは：

• b[i]=1 または =0 (おそらく O(1)) をすばやく設定します。
• 各ステップで一連のインデックスをすばやく取得しますI(間違いなく O(logN) 以下、理想的には O(1))
• それを可能にする C++ ライブラリ
• 論文/ドキュメンテーション

あるといいもの：

• 「最低のもの」を取得する高速な方法 (両方の操作が高速 (O(1)) の場合、最後のインデックスを 1 に設定、つまり select(rank(b)))

私が必要としないのは：

• スペースを節約
• データを圧縮する

Simon Gog らのライブラリ Sdsl 2.0 を使用しています。( https://github.com/simongog/sdsl-lite ) しかし、選択構造

初期化には O(n) のコストがかかり、すべてのクエリに対して O(1) がかかりますが、b の変更に「従わない」(そうですか?? 私はそれについて非常に具体的なものを見つけていません)。変更後のすべてのステップ。

私が読んだ論文は次のとおりです。「ビットマップの高速、小型、単純なランク/選択」(G. Navarro および E. プロビデル) および「実用的なエントロピー圧縮ランク/選択辞書」(D. 岡野原 K. 定兼) および私C ++での堅実な実装へのリンクをいただければ幸いです（構造が私の要件を満たしている場合）

役に立たなかった同様のトピックについて、stackexchange で見つけたもの:

• C/C++ の動的ビット ベクトル

• ビット ベクトルとビットセット

長い質問で申し訳ありませんが、必要なものとそれを見つける決意を説明していただければ幸いです。ビットベクトルに関連するさまざまなことについて、私はまだ非常に混乱しています。それは間違いなく私の専門分野ではないため、明確化していただければ幸いです。

前もって感謝します。

ビット インデックスの配列を OptionSet に準拠するクラスに変換するヘルパー関数を作成しようとしています。

これはコンパイルに失敗します:

RawValue も使用してみました:

これもうまくいきません:

これはできますか？T に制約を追加する必要がありますか?

この関数を書き直して具象型を使用できることはわかっていますが、可能であれば汎用のままにしたいと考えています。

これは単純なビット ベクトルの問題です。

Python がエラー コード 139 でクラッシュします。注意してください、これは私の本当の問題ではないので、私のプロジェクトではビット ベクトル タクティクスを使用する必要がありsmtますが、タクティックまたはタクティックに問題はありませんqfbv。

文字のビット値 (ユーザー指定) に従って、文字列を対応するビットベクトルに変換したいと考えています。A、G、C、T の 4 文字しかないゲノム文字列を扱っています。Javaで次のビット値でそれらを表現したい

文字列「AGGT」が与えられた場合、対応するビット値は01111100になるはずです。次のようにしてみました：

私は何を間違っていますか？正しい方法でそれを行う方法.?

私は Z3 バージョン 4.0 の Ocaml API を 1 年ほど使用しており、主にビットベクトル理論を使用しています。Z3.solver_check を実行した後、unsat コアを抽出する必要がありますが、残念ながらバージョン 4 にはこの機能がありません。仮定を使用して数式内の各ビットベクトル方程式を表し、unsat コアを取得するように書き直すことができますが、これはコードの重要な部分であるため、全体的なパフォーマンスに影響を与える可能性があります。

バージョン 4 の想定を行わずにコアを取得する方法はありますか? もちろん、長期的な解決策は最新バージョンに移行することですが、混乱の少ない解決策があればそれでよいでしょう。たとえば、unsat の証明 (Z3.solver_get_proof によって返される) から unsat コアを抽出する方法はありますか?

ありがとう！

暗号スキームでの操作にはビットを使用する必要がありますが、変数と関数を BitVector(bitstring/int/textstrings="") に変換すると、結果は非常に長いビットベクトルになり、数千単位の長さになります。さて、これにより、これらの BitVectors に対する暗号化と操作が大幅に遅くなります。どうすればこれを克服できますか？:(

私が BitVector を使用している方法の例:

Edit1: たとえば、self.bc.encrypt(msgxored, key)わずか 300 ビットですが、encr1 = BitVector.BitVector(textstring = self.bc.encrypt(msgxored, key))3000 ビットです!

BitVector のモジュラスとは何ですか? それが何をするのかを説明するものはオンラインで見つかりませんでした。GF $2^256$ での計算を台無しにしないように、より大きな数値に設定しようとしました

ドキュメントでは、モジュラスは

10 進数のビット文字列は 286 です。