2

私たちのOS教授は、プロセスIDを新しいプロセスに割り当てるために、カーネルはプロセスの最大数（デフォルトでは〜32,768）に相当するサイズの配列の最初のゼロビットを段階的に検索すると述べました。ここで、割り当てられたプロセスIDは1です。その中に保存されます。

私の知る限り、Cにはビットデータ型はありません。明らかに、ここで欠けているものがあります。

ビット配列を構築できるような特別な構造はありますか？これは正確にどのように行われますか？

さらに重要なことに、そのようなアレイで実行できる操作は何ですか？

4

4 に答える 4

4

ビット配列は、ビット単位の演算子を使用して個々のビットを読み取る単純なバイト配列です。

1バイトのchar変数があるとします。これには8ビットが含まれています。値1を使用してビット単位のAND演算を実行することにより、最下位ビットが真であるかどうかをテストできます。

 char a = /*something*/;
 if (a & 1) {
    /* lowest bit is true */
 }

これは1アンパサンドであることに注意してください。論理積演算子とは完全に異なり&&ます。これが機能a & 1するのは、最初のビットを除くすべてのビットが「マスクアウト」a & 1されるため、の最下位ビットが1の場合に限り、ゼロ以外になりaます。同様に、2番目に下位のビットが2とAND演算されることで、真であるかどうかを確認できます。 3番目は、2の累乗を継続するために、4などとAND演算します。

したがって、32,768要素のビット配列は4096要素のバイト配列として表されます。最初のバイトはビット0〜7を保持し、2番目のバイトはビット8〜15を保持します。チェックを実行するために、コードはバイトを選択します。チェックしたいビットを含む配列から、ビット単位の操作を使用してバイトからビット値を読み取ります。

他のデータ型と同様に、操作が何であるかに関しては、値の読み取りと書き込みを行うことができます。上記の値の読み方と以下の値の書き方を説明しましたが、ビット演算の理解に本当に興味がある場合は、最初の文で提供したリンクを読んでください。

ビットの書き込み方法は、0と1のどちらを書き込むかによって異なります。1ビットをバイトに書き込むにaは、AND演算の逆を実行します。たとえば、OR演算です。

 char a = /*something*/;
 a = a | 1; /* or a |= 1 */

aこの後、前に設定されたかどうかに関係なく、の最下位ビットが1に設定されます。繰り返しますが、1を2に置き換えるか、3番目を4に置き換えることで、これを2番目の位置に書き込むことができ、2の累乗の場合も同様です。

最後に、ゼロビットを書き込むには、書き込みたい位置の逆とANDを使用します。

 char a = /*something*/;
 a = a & ~1; /* or a &= ~1 */

これで、以前の値に関係なく、の最下位ビットがa0に設定されます。これが機能するのは、最下位以外~1のすべてのビットが1に設定され、最下位がゼロに設定されるためです。これにより、最下位ビットがゼロに「マスクアウト」され、残りのビットはそのままになります。a

于 2010-09-24T18:52:00.580 に答える
3

Astructはメンバーにビットサイズを割り当てることができますが、それは「C」の「ビットタイプ」の範囲です。

struct int_sized_struct {
   int foo:4;
   int bar:4;
   int baz:24;
};

残りはビット演算で行われます。例えば。そのPIDビットマップの検索は次の方法で実行できます。

extern uint32_t *process_bitmap;
uint32_t *p = process_bitmap;
uint32_t bit_offset = 0;
uint32_t bit_test;

/* Scan pid bitmap 32 entries per cycle. */
while ((*p & 0xffffffff) == 0xffffffff) {
  p++;
}

/* Scan the 32-bit int block that has an open slot for the open PID */
bit_test = 0x80000000;
while ((*p & bit_test) == bit_test) {
   bit_test >>= 1;
   bit_offset++;
}
pid = (p - process_bitmap)*8 + bit_offset;

これは、PIDごとに1バイトのアレイを単純なforループスキャンするよりも約32倍高速です。（実際には、より多くのビットマップがCPUキャッシュに残るため、32倍を超えます。）

于 2010-09-24T19:03:49.430 に答える
1

http://graphics.stanford.edu/~seander/bithacks.htmlを参照してください

于 2010-09-24T19:02:03.803 に答える
0

Cにはビット型はありませんが、ビット操作はかなり簡単です。一部のプロセッサにはビット固有の命令があり、それがなくても、以下のコードが適切に最適化されます。バイトの代わりに32ビットワードの配列を使用すると、高速になる場合とそうでない場合があります。関数の代わりにインライン化することもパフォーマンスに役立ちます。

書き込むメモリがある場合は、1バイト全体を使用して1ビット（または32ビット数全体など）を格納するだけで、使用するメモリを犠牲にしてパフォーマンスが大幅に向上します。

unsigned char data [SIZE];

unsigned char get_bit（unsigned int offset）
{{
    // TODO：チェックオフセットを制限する
    if（data [offset >> 3]＆（1 <<（offset＆7）））return（1）;
    それ以外の場合はreturn（0）;
}
void set_bit（unsigned int offset、unsigned char bit）
{{
    // TODO：チェックオフセットを制限する
    if（bit）data [offset >> 3] | = 1 <<（offset＆7）;
    else data [offset >> 3]＆=〜（1 <<（offset＆7））;
}
于 2010-09-24T19:22:50.773 に答える