c - C で特定のビット数を割り当てることはできますか?

Question

実行時に決定される大量のブール情報を保存しようとしています。最善の方法は何だろうと考えていました。

私は現在、以下を使用してメモリを割り当てようとしています:

pStatus = malloc((<number of data points>/8) + 1);

これで作業するのに十分なビットが得られると考えています。次に、配列表記のポインターを使用して、各ブール値を参照できます。

pStatus[element]

残念ながら、これはうまく機能していないようです。まず、メモリを整数値に初期化するのに苦労しています0。これを使用して行うことができますmemset()か? それでも、アクセスしようとするとクラッシュする理由に影響しているとは思いませんpStatus[element]。

また、このアプローチが使用するのに最適であると完全に確信しているわけではありません。私が本当に欲しいのは、本質的にブール値のステータスを反映する巨大なビットマスクです。私は何かを逃しましたか？

score 30 · Accepted Answer

pStatus = malloc((<number of data points>/8) + 1);

これにより、ビットに十分なバイトが割り当てられます。でも、

pStatus[element]

これは、ビットではなく要素のバイトにアクセスします。したがって、要素が総ビット数の 8 分の 1 を超える場合は、割り当てられた配列の最後にアクセスしています。

いくつかのヘルパー関数を定義します

int get_bit(int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    return ((pStatus[byte_index] & bit_mask) != 0);
}

void set_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] |= bit_mask);
}

void clear_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] &= ~bit_mask;
}

(わかりやすくするために省略されている要素の範囲のエラーチェック。このマクロを作成することもできます)

score 8 · Accepted Answer

...これで作業するのに十分なビットが得られると思います。次に、配列表記のポインターを使用して、各ブール値を参照できます。

pStatus[element]

要素はビットではなくバイトをアドレス指定しています。次のようなものが必要です。

pStatus[element/8] & (1 << (element % 8))

score 5 · Accepted Answer

小さなポイント：Nビットを格納するのに十分なメモリを取得するには、（N / 8）+ 1バイトは不正確です（1バイトが多すぎる可能性があります）。

ただし、（N + 7）/8は常に最小数です。

score 4 · Accepted Answer

最も簡単な答えは、malloc の代わりに calloc を使用することです。

割り当てるメモリをゼロに初期化するように定義されており、多くの場合、ページマッピングのトリックを使用してこれを行うことができます。

これにより、メモリの初期化の問題が解決されます。ここにある他の 10 の投稿は、インデックス作成の問題と、時折余分なバイトを割り当てるという事実 (恐ろしい!) に適切に対処しているように見えるので、ここでは内容を繰り返さない。

score 2 · Accepted Answer

pStatus[element] は、そのアドレスのバイト全体を提供します。

特定の要素を設定するには、次のようにします。

pStatus[element >> 3] |= 1 << (element & 7);

要素をリセットするには:

pStatus[element >> 3] &= ~1 << (element & 7);

要素をテストするには:

if (pStatus[element >> 3] & (1 << (element & 7)) != 0)

初期割り当ては

pstatus = malloc((<number of data points> + 7) / 8)

あなたが持っていたものは機能しますが、時々バイトを無駄にします

score 2 · Accepted Answer

ここでの C のすべての回答は、1 バイトが 8 ビットであると想定しているように見えることに気が付かずにはいられません。これは C では必ずしも当てはまりません (ただし、ほとんどの主流のハードウェアではもちろん当てはまります)。そのため、コードでこの仮定を行うのはかなり悪い形式です。

アーキテクチャに中立なコードを記述する適切な方法は、次のとおりです。

#include <limits.h>

次に、「CHAR_BIT内のビット数」が必要な場所でマクロを使用しますchar。

score 1 · Accepted Answer

自分を幸せにして、タイプとそのタイプを操作するための関数を定義します。そうすれば、ビットアクセスが遅すぎることがわかった場合、ブール値あたりのメモリの単位をバイト/ワード/ロングに変更するか、メモリが本当に問題になる場合（つまり、セットがほとんどゼロの場合）にスパース/動的データ構造を採用できます。、1の座標のリストを保持することができます。

ビットベクトルの実装の変更に完全に影響されないようにコードを記述できます。

score 0 · Accepted Answer

ラッパーを書かなくてもよい場合は、C++ の STL の bit_set または bit_vector を使用することもできます。これら (特に後者) には、必要なものが正確に含まれており、コード化、テスト、パッケージ化されているようです (さらに多くの機能が備わっています)。）。

C アプリケーションで C++ コードを使用する簡単な方法がないのは本当に残念です (いいえ、ラッパーを作成することは私にとって簡単ではなく、楽しくもありません。長期的にはより多くの作業を意味します)。

score 0 · Accepted Answer

 pStatus = malloc((<number of data points>/8) + 1);

その部分は大丈夫です。

 pStatus[element]

ここであなたが困っているところです。ビットをアドレス指定する場合は、バイトをアドレス指定します。

 pStatus[element / 8 ]

配列内の正しいバイトを取得します。

score 0 · Accepted Answer

バイトを割り当てる必要がありc = malloc((N+7)/8)、n番目を次のように設定できます

 c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));

でクリア

 c[n/8] &= ~(0x80 >> (n%8));

そしてテスト

 if(c[n/8] & (0x80 >> (n%8))) blah();

score 0 · Accepted Answer

ここで CHAR_BIT に言及している回答が 1 つしかないことに驚きました。多くの場合、1 バイトは 8 ビットですが、常にそうとは限りません。

score 0 · Accepted Answer

pStatus[element] はビットをアドレス指定しません。取得する正確なバイトは pStatus のタイプに依存します-私は char* または同等のものを想定しています-したがって、 pStatus[element] は要素の 1 番目のバイトを取得します。

はい、memsetを0に設定できます。

score 0 · Accepted Answer

0

何が間違っているstd::vector<bool>でしょうか？

于 2008-11-20T22:46:57.893 に答える

score -1 · Accepted Answer

割り当てコードは正しいです。ブール値にアクセスするには、この回答set_bit()にある関数とget_bit()関数を参照してください。

score -1 · Accepted Answer

ブール値はCでは「決して」個別の値ではありません。したがって、構造体はあなたを動かすためにあるかもしれません。

メモリ領域を初期化しないのは事実なので、個別に行う必要があります。

これは、ユニオン構造体と列挙型を使用してそれを行う方法の簡単な例です

typedef unsigned char           BYTE;
typedef unsigned short          WORD;
typedef unsigned long int       DWORD;
typedef unsigned long long int  DDWORD;
enum STATUS
{
    status0 = 0x01,
    status1 = 0x02,
    status2 = 0x04,
    status3 = 0x08,
    status4 = 0x10,
    status5 = 0x20,
    status6 = 0x40,
    status7 = 0x80,
status_group = status0 + status1 +status4
};
#define GET_STATUS( S ) ( ((status.DDBuf&(DDWORD)S)==(DDWORD)S) ? 1 : 0  )
#define SET_STATUS( S ) (  (status.DDBuf|=  (DDWORD)S) )
#define CLR_STATUS( S ) (  (status.DDBuf&= ~(DDWORD)S) )
static union {
 BYTE   BBuf[8];
 WORD   WWBuf[4];
 DWORD  DWBuf[2];
 DDWORD DDBuf;
}status;

int main(void)
{
    // Reset status bits
    status.BBuf[0] = 0;
    printf( "%d \n", GET_STATUS( status0 ) );

    SET_STATUS( status0 );
    printf( "%d \n", GET_STATUS( status0 ) );

    CLR_STATUS(status0);
    printf( "%d \n", GET_STATUS( status0 ) );
    SET_STATUS( status_group );
    printf( "%d \n", GET_STATUS( status0 ) );
    system( "pause" );
    return 0;
}

お役に立てれば。この例では、最大 64 個のステータスブール値を処理でき、簡単に拡張できます。

この例は、Char = 8 ビット int = 16 ビット long int = 32 ビットおよび long long int = 64 ビットに基づいています。

ステータスグループのサポートも追加しました。

score -1 · Accepted Answer

ほんの数ビットに制限されている場合は、eaanon01 ソリューションの代わりに、ビットフィールドの c 組み込み機能も使用できます (それらを使用できる機会はほとんどありませんが、これは 1 つです)。

このちょっとした衝撃的なものについては、私がお勧めします: Herny Warrens "Hacker Delight"

c - C で特定のビット数を割り当てることはできますか?

16 に答える 16

Related

Reference