問題タブ [bitset]

複数のビットを一度に効率的に追加できる高速ビット追加機能を備えたビットセットの実装を探しています。

例えば

これまで、boost::dynamic_bitset と std::vector を試しました。どちらも遅いです。

古いポスト

boost::dynamic_bitset を使用してデータをパックしています。

通常、一度に最大 5 ビットをパックすると、次のような呼び出しになります。

しかし、これは私には非常に効率が悪いように思えます。一度にすべてのビットを追加することはできませんか?

例えば

私はそれが次のようなことをすることを期待します:

dynamic_bitset にそのような機能がないのはなぜですか? 効率的に実装できるでしょうか？

パフォーマンスを低下させない方法で、大きなビットセットと小さなビットセットを連結したいと思います。現在、私のアプリケーションは、次のコードだけでCPU時間の20％を費やしています。

解決策を提案するこの投稿を読みましたが、宛先ビットセットとソースビットセットのサイズのサイズの差が非常に大きいため、残念ながら機能しません。

何か案は？

これがboost::dynamic_bitsetで効率的に行うことができない場合、私は他の提案を受け入れています。

私のプログラムでは、2.5*10^9 のセットで既に値を生成しているかどうかを確認する必要があります。セットの約半分を生成することを期待しており、それを確認して更新するための高速な方法が必要です。ビットセットは、あまり多くのメモリを必要とせず (値ごとに 1 ビット)、高速であるため、私には良いアイデアのように思えました。

問題は、自分のクラスで自分のセットを定義するsegmentation faultと、サイズが大きすぎる (小さいサイズで動作する) ということです。

何か案が ？

ありがとうございました

PS: 可能であれば、外部ライブラリを使用したくありません。私はすでにGMPを使用していますが、大きな数に対して少し設定された実装があるとは思いません。

私はC++でフラッドフィルアルゴリズムを作成しようとしているので、2D配列を作成することを計画しました。そうすると、各アイテムはオブジェクトになり、プロパティはその周囲の壁をチェックします。

壁には次のように注意します。1=上2=右4=下8=左

つまり、13は、上/下/左の壁を意味します

しかし、私が使用するstd::bitset<sizeof(int)> bits(w);と、「期待される」が得られます。'（'トークンの前にこれを修正するにはどうすればよいですか？私は多くのことを試しましたが、うまくいきません。

私のコード：

};

}

次のコード セグメントを使用したい

3 つの要素を持つベクトルを取得するには、1101 1010 1010 のようになります

しかし、私が期待した正しい結果を得ることができません。

私たちを手伝ってくれますか？ありがとうございました！

BitSetをByte配列に変換するこの例を取り上げました。

しかし、ディスカッションフォーラムでは、計算ごとに1ビットが失われるため、この方法ではすべてのビットを取得できないことがわかりました。これは本当ですか？上記の方法を変更する必要がありますか？

私は持っている：

BitComp という名前のクラスのゲッターとセッター。次のクラスは、最初の 8 ビットすべてを 1 (byte[0]) に設定します。その後、すべてのバイトを BitSet に変換します。その後、2 番目のビットを true に設定し、両方を出力します。

出力:00000000000000000000000000000011111111 <- 0th
0th-> 01000000000000000000000000000011111111

byte[0] には最初の 8 つの要素が含まれており、BitSet 操作で 2 番目の要素を 1 に設定しています。そのため、BitSet は LHS から近づき、Byte 配列は RHS から格納されます。この問題にアプローチするには？getBitsFromByte メソッドに問題はありますか? 提案してください。ありがとう

ビット配列を構築するには、ビットセット型を定義する必要があります。これらの配列間で、and/or/xor などのビット操作を (たとえば、それらを比較するために) 実行することができ、それらが支配的な操作です。ビットセット型としてどの型を使用すればよいですか?

型は、コンパイラが処理できる最も広い NOT SIMULATED 型であるべきだと思います。つまり、コンパイラが 64 ビット型をシミュレートする場合 (マシンまたは OS がそれをサポートしていない場合など)、単純な and 間の複合操作をマスクして、代わりに 32 ビット型を使用する必要があります。それを決定する方法は？

その他の質問:

新しい c99 ヘッダーはいくつかの型 (正確な幅の整数型) を定義します。

「これらは intN_t と uintN_t の形式です。両方の型は、パディング ビットのない正確な N ビットで表す必要があります。intN_t は 2 の補数の符号付き整数としてエンコードし、uintN_t は符号なし整数としてエンコードする必要があります。実装が型をサポートしない限り、これらの型はオプションです。幅が 8、16、32、または 64 の場合、対応する N を使用して対応する型に型定義します。その他の N はオプションです。

64ビット型をチェックする実装は最初のステップだと思いますよね？

私のプロジェクトでは、#マクロを定義する SDL ライブラリを使用しています。

したがって、おそらくそのマクロに応じてビットセット型の定義を作成できます (ただし、sdl のコードを独立して記述したいので、これは最適ではありません)。

について意見を聞かせてください。

各ビットを個別に反復することなく、ビットセットからビットのCPUワードサイズの長いサブシーケンスを効率的に抽出する方法はありますか？何かのようなもの

例外をスローする代わりにビット文字列を切り捨てる場合はそうします！

私はビットセットを扱っていたので、基数 10 を基数 2 に変換する最良の方法は何かと考えていました。何らかの理由で間違った答えが得られたからです。数字 19 を与えると、 : 10011 (16-2-1)、なぜ (00011) を出力するのか