c++ - C/C++ 効率的なビット配列

Question

任意の長さのビット配列を操作するための効率的でクリーンな方法をお勧めできますか?

現在、通常の int/char ビットマスクを使用していますが、配列の長さがデータ型の長さよりも大きい場合、それらはあまりきれいではありません。

std vector<bool>は利用できません。

score 50 · Accepted Answer

C だけでなく C++ についても言及されているため、C++ 指向のソリューションはboost::dynamic_bitset適用できない可能性があると想定し、代わりに低レベルの C 実装について説明します。そのようなものがboost::dynamic_bitsetうまくいく場合、または見つけることができる既存の C ライブラリがある場合は、それらを使用する方が自分で作成するよりも優れている可能性があることに注意してください。

警告: 次のコードはいずれもテストもコンパイルもされていませんが、必要なものに非常に近いはずです。

まず、固定ビットセットサイズ N があると仮定します。次に、次のようなものが機能します。

typedef uint32_t word_t;
enum { WORD_SIZE = sizeof(word_t) * 8 };

word_t data[N / 32 + 1];

inline int bindex(int b) { return b / WORD_SIZE; }
inline int boffset(int b) { return b % WORD_SIZE; }

void set_bit(int b) { 
    data[bindex(b)] |= 1 << (boffset(b)); 
}
void clear_bit(int b) { 
    data[bindex(b)] &= ~(1 << (boffset(b)));
}
int get_bit(int b) { 
    return data[bindex(b)] & (1 << (boffset(b));
}
void clear_all() { /* set all elements of data to zero */ }
void set_all() { /* set all elements of data to one */ }

書かれているように、これは固定サイズのグローバルビットセットを 1 つしか実装していないため、少し大雑把です。これらの問題に対処するには、次のようなデータ構造から始めます。

struct bitset { word_t *words; int nwords; };

次に、これらのビットセットを作成および破棄する関数を記述します。

struct bitset *bitset_alloc(int nbits) {
    struct bitset *bitset = malloc(sizeof(*bitset));
    bitset->nwords = (n / WORD_SIZE + 1);
    bitset->words = malloc(sizeof(*bitset->words) * bitset->nwords);
    bitset_clear(bitset);
    return bitset;
}

void bitset_free(struct bitset *bitset) {
    free(bitset->words);
    free(bitset);
}

struct bitset *これで、以前の関数を変更してパラメーターを取得するのは比較的簡単になりました。有効期間中にビットセットのサイズを変更する方法はまだありません。また、境界チェックもありませんが、現時点で追加するのは難しくありません。

score 21 · Accepted Answer

boost::dynamic_bitset長さが実行時にのみわかっている場合。

std::bitset長さがコンパイル時にわかっている場合（任意ですが）。

score 13 · Accepted Answer

Dale Hagglund の応答に基づいて、C でビット配列を提供する (BSD ライセンス) という実用的な実装を作成しました。

https://github.com/noporpoise/BitArray/

あなたの考えを教えてください/提案をしてください。この質問への回答を探している人に役立つことを願っています。

score 7 · Accepted Answer

この投稿はかなり古いものですが、私のALFLBライブラリのCには効率的なビット配列スイートがあります。

ハードウェア除算オペコードのない多くのマイクロコントローラーの場合、このライブラリは除算を使用しないため効率的です。代わりに、マスキングとビットシフトが使用されます。（はい、一部のコンパイラーは8による除算をシフトに変換することを知っていますが、これはコンパイラーごとに異なります。）

最大2^32-2ビット（536メガバイトに格納された約40億ビット）のアレイでテストされていますが、アプリケーションのforループで使用されていない場合は、最後の2ビットにアクセスできるはずです。

ドコからの抜粋については、以下を参照してください。Docoはhttp://alfredo4570.net/src/alflb_doco/alflb.pdfであり、ライブラリはhttp://alfredo4570.net/src/alflb.zipです。

楽しんで、
アルフ

//------------------------------------------------------------------
BM_DECLARE( arrayName, bitmax);
        Macro to instantiate an array to hold bitmax bits.
//------------------------------------------------------------------
UCHAR *BM_ALLOC( BM_SIZE_T bitmax); 
        mallocs an array (of unsigned char) to hold bitmax bits.
        Returns: NULL if memory could not be allocated.
//------------------------------------------------------------------
void BM_SET( UCHAR *bit_array, BM_SIZE_T bit_index);
        Sets a bit to 1.
//------------------------------------------------------------------
void BM_CLR( UCHAR *bit_array, BM_SIZE_T bit_index);
        Clears a bit to 0.
//------------------------------------------------------------------
int BM_TEST( UCHAR *bit_array, BM_SIZE_T bit_index); 
        Returns: TRUE (1) or FALSE (0) depending on a bit.
//------------------------------------------------------------------
int BM_ANY( UCHAR *bit_array, int value, BM_SIZE_T bitmax); 
        Returns: TRUE (1) if array contains the requested value (i.e. 0 or 1).
//------------------------------------------------------------------
UCHAR *BM_ALL( UCHAR *bit_array, int value, BM_SIZE_T bitmax);
        Sets or clears all elements of a bit array to your value. Typically used after a BM_ALLOC.  
        Returns: Copy of address of bit array
//------------------------------------------------------------------
void BM_ASSIGN( UCHAR *bit_array, int value, BM_SIZE_T bit_index);
        Sets or clears one element of your bit array to your value.
//------------------------------------------------------------------
BM_MAX_BYTES( int bit_max); 
        Utility macro to calculate the number of bytes to store bitmax bits.
        Returns: A number specifying the number of bytes required to hold bitmax bits.
//------------------------------------------------------------------

score 3 · Accepted Answer

std::bitsetを使用できます

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

score 2 · Accepted Answer

I know it's an old post but I came here to find a simple C bitset implementation and none of the answers quite matched what I was looking for, so I implemented my own based on Dale Hagglund's answer. Here it is :)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef uint32_t word_t;
enum { BITS_PER_WORD = 32 };
struct bitv { word_t *words; int nwords; int nbits; };

struct bitv* bitv_alloc(int bits) {
    struct bitv *b = malloc(sizeof(struct bitv));

    if (b == NULL) {
        fprintf(stderr, "Failed to alloc bitv\n");
        exit(1);
    }

    b->nwords = (bits >> 5) + 1;
    b->nbits  = bits;
    b->words  = malloc(sizeof(*b->words) * b->nwords);

    if (b->words == NULL) {
        fprintf(stderr, "Failed to alloc bitv->words\n");
        exit(1);
    }

    memset(b->words, 0, sizeof(*b->words) * b->nwords);

    return b;
}

static inline void check_bounds(struct bitv *b, int bit) {
    if (b->nbits < bit) {
        fprintf(stderr, "Attempted to access a bit out of range\n");
        exit(1);
    }
}

void bitv_set(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] |= 1 << (bit % BITS_PER_WORD);
}

void bitv_clear(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] &= ~(1 << (bit % BITS_PER_WORD));
}

int bitv_test(struct bitv *b, int bit) {
    check_bounds(b, bit);
    return b->words[bit >> 5] & (1 << (bit % BITS_PER_WORD));
}

void bitv_free(struct bitv *b) {
    if (b != NULL) {
        if (b->words != NULL) free(b->words);
        free(b);
    }
}

void bitv_dump(struct bitv *b) {
    if (b == NULL) return;

    for(int i = 0; i < b->nwords; i++) {
        word_t w = b->words[i];

        for (int j = 0; j < BITS_PER_WORD; j++) {
            printf("%d", w & 1);
            w >>= 1;
        }

        printf(" ");
    }

    printf("\n");
}

void test(struct bitv *b, int bit) {
    if (bitv_test(b, bit)) printf("Bit %d is set!\n", bit);
    else                   printf("Bit %d is not set!\n", bit);
}

int main(int argc, char *argv[]) {
    struct bitv *b = bitv_alloc(32);

    bitv_set(b, 1);
    bitv_set(b, 3);
    bitv_set(b, 5);
    bitv_set(b, 7);
    bitv_set(b, 9);
    bitv_set(b, 32);
    bitv_dump(b);
    bitv_free(b);

    return 0;
}

score 1 · Accepted Answer

私はこれを使用します：

//#include <bitset>
#include <iostream>
//source http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
#define BIT_SET(a,b) ((a) |= (1<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1<<(b)))
#define BIT_CHECK(a,b) ((a) & (1<<(b)))

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK(x,y) ((x) & (y))

score 1 · Accepted Answer

私は最近、この目的のためだけに BitContainer と呼ばれる小さなヘッダーのみのライブラリを実装しました。表現力とコンパイル時の能力に焦点を当てており、 https ://github.com/EddyXorb/BitContainer で見つけることができます。

これは確かに bitarray を見る古典的な方法ではありませんが、強力な型指定の目的や名前付きプロパティのメモリ効率の良い表現には便利です。

例：

constexpr Props props(Prop::isHigh(),Prop::isLow()); // intialize BitContainer of type Props with strong-type Prop

constexpr bool result1 = props.contains(Prop::isTiny()) // false
constexpr bool result2 = props.contains(Prop::isLow())  // true

c++ - C/C++ 効率的なビット配列

10 に答える 10

Related

Reference