1

免責事項：私は割り当てに関連してこれらの質問をしています。割り当て自体は、ビットマップを実装し、それを使用していくつかの操作を実行することを要求しますが、それは私が求めていることではありません。自分で実装を試すことができるように、概念を理解したいだけです。

ビットマップ/ビット配列とビット単位の演算を理解するのに助けが必要です。バイナリの基本と左右シフトの仕組みは理解していますが、その使用がどのように役立つのか正確にはわかりません。

基本的に、（エラトステネスの）プライムシーブの結果を保存するためにビットマップを実装する必要があります。これは、さまざまなIPCメソッドに焦点を当てた大きな割り当てのごく一部ですが、その部分に到達するには、最初にシーブを完成させる必要があります。 。私はビット演算を使用する必要がなかったし、ビットマップについても学んだことがないので、これを学ぶのは私自身のようなものです。

私の知る限り、ビットマップは特定のサイズのビットの配列ですよね？つまり、8ビット配列または32ビット配列を使用できます（私の場合、32ビットのunsigned intの素数を見つける必要があるため、32ビット配列が必要です）。これがビットの配列であり、そのうち32個が具体的である場合、基本的に32個の1と0の文字列について話します。これはどのように素数のリストに変換されますか？1つの方法で2進数を評価し、それを10進数として新しい配列に保存するため、すべての10進数の素数が1つの配列に存在しますが、使用しているデータが多すぎるようです。

ビットマップの要点はありますか？それとも私が欠けているものがありますか？私はインターネットでこれについて読んでみましたが、私にとって十分に明確な情報源を見つけることができません...

4

3 に答える 3

3

素数のリストがあるとします：{3、5、7}。これらの数値は文字配列として格納できchar c[] = {3, 5, 7}ます。これには3バイトが必要です。

代わりに、各セットビットがその番号がセット内にあることを示すように1バイトを使用しましょう。たとえば、01010100です。必要なバイトを設定して後でテストできる場合は、これを使用して同じ情報を1バイトに格納できます。設定するには：

char b = 0;
// want to set `3` so shift 1 twice to the left
b = b | (1 << 2); 
// also set `5`
b = b | (1 << 4);
// and 7
b = b | (1 << 6);

そして、これらの数値をテストするには：

// is 3 in the map:
if (b & (1 << 2)) {
  // it is in...
于 2013-03-15T23:57:31.840 に答える
1

ビットマップを使用すると、関心のある数値の範囲で大きな述語関数を作成できます。8ビット文字が1つしかない場合は、8つの値のそれぞれにブール値を格納できます。2文字ある場合は、範囲が2倍になります。

したがって、この情報がすでに保存されているビットマップがある場合、テスト関数は次のようになります。

bool num_in_bitmap (int num, char *bitmap, size_t sz) {
    if (num/8 >= sz) return 0;
    return (bitmap[num/8] >> (num%8)) & 1;
}
于 2013-03-15T23:50:57.807 に答える
1

32ビット以上が必要になります。

最大2^32の数字のふるいが必要なので、それぞれに少しずつ必要になります。各ビットは1つの数値を表し、数値が素数の場合は0、合成数の場合は1になります。（1は素数でも合成でもないため、最初のビットは2でなければならないことに注意して、1ビットを節約できます。その1ビットを無駄にする方が簡単です。）

2 ^ 32 = 4,294,967,296

8で割る

536,870,912バイト、または1/2GB。

したがって、2 ^ 29バイト、2 ^ 27 4バイトワード、またはあなたが最適と判断したものの配列と、配列内の文字（int）に格納されている個々のビットを操作する方法が必要になります。

最終的には、この共有メモリで複数のスレッドまたはプロセスが動作するようになります。すべてのメモリを自分に割り当てることができない場合は、すべてをファイルに保存する必要があります。

xのビットを見つけたいとしましょう。次に、a = x/8およびb=x --8*aとします。次に、ビットはarr [a]＆（1 << b）にあります。（可能な限り、剰余演算子％は避けてください。）

//mark composite
a = x / 8;
b = x - 8 * a;
arr[a] |= 1 << b;

これは楽しい課題のように聞こえます！

于 2013-03-16T01:15:12.660 に答える