如何在C中实现bitset？
我一直在使用Java中的Bitset类，我想在C中做类似的事情。我想我必须手动完成它作为C中的大多数东西。什么是一种有效的实现方法？
byte bitset[] 也许
bool bitset[]
？
CCAN有一个可以使用的bitset实现： 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来适应它。
没有人提到C FAQ推荐的内容，这是一堆好老的宏：
#include /* 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 ）
那么，字节bitset []似乎有点误导，不是吗？
在结构中使用位字段，然后您可以维护这些类型的集合（或者在您认为合适的情况下使用它们）
struct packed_struct { unsigned int b1:1; unsigned int b2:1; unsigned int b3:1; unsigned int b4:1; /* etc. */ } packed;
我推荐我的BITSCAN C ++库 （版本1.0刚刚发布）。 BITSCAN专门用于快速位扫描操作。 我用它来实现涉及简单无向图的NP-Hard组合问题，例如最大团（参见BBMC算法，用于领先的精确求解器）。
BITSCAN与标准解决方案之间的比较STL bitset和BOOST dynamic_bitset可在此处获得： http ：//blog.biicode.com/bitscan-efficiency-at-glance/
您可以尝试使用bitsPerItem为1尝试我的PackedArray代码。
它实现了一个随机访问容器，其中项目在位级别打包。 换句话说，它就像你能够操作例如uint9_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, eg i0, i1, i2 . some items span two buffer cells, eg i3, i6
像往常一样，您需要首先确定您需要对bitset执行哪种操作。 也许是Java定义的一些子集？ 之后，您可以决定如何最好地实现它。 您当然可以在OpenJDK中查看BitSet.java的源代码。
使它成为unsigned int 64的数组。