C语言 如何在 C 中实现位集？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4372515/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement a bitset in C?
提问by David Robles
I have been using the Bitsetclass in Java and I would like to do something similar in C. I suppose I would have to do it manually as most stuff in C. What would be an efficient way to implement?
我一直在 Java 中使用Bitset类，我想在 C 中做类似的事情。我想我必须像 C 中的大多数东西一样手动完成它。什么是实现的有效方法？
byte bitset[]
maybe
也许
bool bitset[]
?
?
回答by Mike Axiak
CCANhas a bitset implementation you can use: http://ccan.ozlabs.org/info/jbitset.html
CCAN有一个可以使用的 bitset 实现：http: //ccan.ozlabs.org/info/jbitset.html
But if you do end up implementing it yourself (for instance if you don't like the dependencies on that package), you should use an array of ints and use the native size of the computer architecture:
但是，如果您最终自己实现它（例如，如果您不喜欢该包的依赖项），则应该使用整数数组并使用计算机体系结构的本机大小：
#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));
}
Don't use a specific size (e.g. with uint64 or uint32), let the computer use what it wants to use and adapt to that using sizeof.
不要使用特定的大小（例如使用 uint64 或 uint32），让计算机使用它想要使用的并使用 sizeof 适应它。
回答by Mike Axiak
Nobody mentioned what the C FAQ recommends, which is a bunch of good-old-macros:
没有人提到 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)
回答by Ed S.
Well, byte bitset[] seems a little misleading, no?
好吧，字节 bitset[] 似乎有点误导，不是吗？
Use bit fields in a struct and then you can maintain a collection of these types (or use them otherwise as you see fit)
在结构中使用位字段，然后您可以维护这些类型的集合（或者在您认为合适的情况下以其他方式使用它们）
struct packed_struct {
unsigned int b1:1;
unsigned int b2:1;
unsigned int b3:1;
unsigned int b4:1;
/* etc. */
} packed;
回答by chesslover
I recommend my BITSCAN C++ library(version 1.0 has just been released). BITSCAN is specifically oriented for fast bitscan operations. I have used it to implement NP-Hard combinatorial problems involving simple undirected graphs, such as maximum clique (see BBMCalgorithm, for a leading exact solver).
我推荐我的BITSCAN C++ 库（1.0 版刚刚发布）。BITSCAN 专门针对快速位扫描操作。我已经用它来实现涉及简单无向图的 NP-Hard 组合问题，例如最大集团（请参阅BBMC算法，以获得领先的精确求解器）。
A comparison between BITSCAN and standard solutions STL bitsetand BOOST dynamic_bitsetis available here: http://blog.biicode.com/bitscan-efficiency-at-glance/
BITSCAN 与标准解决方案 STL bitset和 BOOST dynamic_bitset 之间的比较可在此处获得：http: //blog.biicode.com/bitscan-efficiency-at-glance/
回答by Gregory Pakosz
You can give my PackedArraycode a try with a bitsPerItemof 1.
你可以给我PackedArray码与一试bitsPerItem的1。
It implements a random access container where items are packed at the bit-level. In other words, it acts as if you were able to manipulate a e.g. uint9_tor uint17_tarray:
它实现了一个随机访问容器，其中项目在位级别打包。换句话说，它就像您能够操作 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
回答by President James K. Polk
As usual you need to first decide what sort of operations you need to perform on your bitset. Perhaps some subset of what Java defines? After that you can decide how best to implement it. You can certainly look at the source for BitSet.java in OpenJDK for ideas.
像往常一样，您需要首先决定需要对位集执行哪种操作。也许Java定义的某些子集？之后，您可以决定如何最好地实施它。您当然可以查看 OpenJDK 中 BitSet.java 的源代码以获取想法。
回答by EvilTeach
Make it an array of unsigned int 64.
使它成为一个 unsigned int 64 的数组。
