c - Cでビットセットを実装するには?

Question

私は Java でBitsetクラスを使用してきましたが、C でも同様のことをしたいと考えています。C のほとんどのものと同じように手動で行う必要があると思います。効率的な実装方法は何でしょうか?

byte bitset[]

多分

bool bitset[]

?

Answer 1

CCANには、使用できるビットセットの実装があります: http://ccan.ozlabs.org/info/jbitset.html

ただし、自分で実装することになった場合 (たとえば、そのパッケージへの依存関係が気に入らない場合)、int の配列を使用し、コンピューター アーキテクチャのネイティブ サイズを使用する必要があります。

#define WORD_BITS (8 * sizeof(unsigned int))

unsigned int * bitarray = (int *)calloc(size / 8 + 1, sizeof(unsigned int));

static inline void setIndex(unsigned int * bitarray, size_t idx) {
    bitarray[idx / WORD_BITS] |= (1 << (idx % WORD_BITS));
}

特定のサイズ (uint64 や uint32 など) を使用しないでください。コンピューターが使用したいものを使用し、sizeof を使用してそれに適応させます。

Answer 2

古き良きマクロの束である C FAQ が推奨するものについては誰も言及していません。

#include <limits.h>     /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

( http://c-faq.com/misc/bitsets.html経由)

Answer 3

ええと、byte bitset[] は少し誤解を招くようですね。

構造体でビット フィールドを使用すると、これらの型のコレクションを維持できます (または、必要に応じて別の方法で使用できます)。

struct packed_struct {
  unsigned int b1:1;
  unsigned int b2:1;
  unsigned int b3:1;
  unsigned int b4:1;
  /* etc. */
} packed;

Answer 4

私のPackedArrayコードをbitsPerItemof で試すことができます1。

アイテムがビットレベルでパックされるランダム アクセス コンテナーを実装します。つまり、eguint9_tまたはuint17_t配列を操作できたかのように動作します。

PackedArray principle:
  . compact storage of <= 32 bits items
  . items are tightly packed into a buffer of uint32_t integers

PackedArray requirements:
  . you must know in advance how many bits are needed to hold a single item
  . you must know in advance how many items you want to store
  . when packing, behavior is undefined if items have more than bitsPerItem bits

PackedArray general in memory representation:
  |-------------------------------------------------- - - -
  |       b0       |       b1       |       b2       |
  |-------------------------------------------------- - - -
  | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
  |-------------------------------------------------- - - -

  . items are tightly packed together
  . several items end up inside the same buffer cell, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6

Answer 5

いつものように、最初にビットセットで実行する必要がある操作の種類を決定する必要があります。おそらくJavaが定義するもののサブセットでしょうか？その後、最適な実装方法を決定できます。アイデアについては、OpenJDK の BitSet.java のソースを見ることができます。

Answer 6

unsigned int 64 の配列にします。