9

我一直在使用 Java 中的Bitset类，我想在 C 中做类似的事情。我想我必须像 C 中的大多数东西一样手动完成。什么是一种有效的实现方式？

byte bitset[]

也许

bool bitset[]

?

4

7 回答 7

16

CCAN有一个可以使用的位集实现：http: //ccan.ozlabs.org/info/jbitset.html

但是，如果您最终自己实现它（例如，如果您不喜欢该包的依赖项），则应该使用整数数组并使用计算机体系结构的本机大小：

#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 来适应它。

于 2010-12-07T01:09:17.800 回答
13

没有人提到 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）

于 2014-01-08T16:48:37.830 回答
3

好吧， byte bitset[] 似乎有点误导，不是吗？

在结构中使用位字段，然后您可以维护这些类型的集合（或者在您认为合适的情况下使用它们）

struct packed_struct {
  unsigned int b1:1;
  unsigned int b2:1;
  unsigned int b3:1;
  unsigned int b4:1;
  /* etc. */
} packed;
于 2010-12-07T01:09:38.197 回答
2

我推荐我的BITSCAN C++ 库（1.0 版刚刚发布）。BITSCAN 专门针对快速位扫描操作。我已经用它来实现涉及简单无向图的 NP-Hard 组合问题，例如最大团（参见BBMC算法，了解领先的精确求解器）。

BITSCAN 和标准解决方案 STL bitset和 BOOST dynamic_bitset之间的比较可在此处获得：http: //blog.biicode.com/bitscan-efficiency-at-glance/

于 2014-07-22T16:20:30.397 回答
1

你可以试试我的PackedArray代码。bitsPerItem1

它实现了一个随机访问容器，其中项目以位级别打包。换句话说，它的作用就像您能够操作 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
于 2014-05-08T13:04:50.227 回答
0

像往常一样，你需要首先决定你需要在你的 bitset 上执行什么样的操作。也许是 Java 定义的一些子集？之后，您可以决定如何最好地实施它。您当然可以查看 OpenJDK 中 BitSet.java 的源代码以获取想法。

于 2010-12-07T01:18:02.523 回答
-2

使其成为 unsigned int 64 的数组。

于 2010-12-07T01:11:55.433 回答