正文 

当前位置： 首页 > 源码 >

如何在 C 中实现位集？

     2023-02-18     139

关键词：

【中文标题】如何在 C 中实现位集？【英文标题】：How to implement a bitset in C? 【发布时间】：2011-05-21 07:50:34 【问题描述】：

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

byte bitset[]

也许

bool bitset[]

?

【问题讨论】：

内存或CPU效率高吗？ @robert：我想首先是在内存方面。这是因为可能的处理开销很小，但在缓存未命中的情况下开销很大。 @robert：有区别吗？如果有大量位，性能将受到缓存未命中的限制，因此尽可能紧密地打包位将提供最佳性能。只有当比特很少时，每比特使用一个完整字节（或更多）可能更有效。 【参考方案1】：

CCAN 有一个可以使用的 bitset 实现：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 来适应它。

【讨论】：

可能，但也可能您想要可以有效操作的最大尺寸。如果您正在扫描位，那么这可能是有效的。再说一次，一些 CPU 从内存中加载缓存的方式与您选择的大小无关。但另一方面……也许你只需要试验和测量。 当然是实验，但根据我的经验，使用单词大小进行拆分通常是最快的。我不确定我是否理解您的第一点？ sizeof 以字节为单位，而不是位。您需要乘以 8（或者在某些表达式中更一般地说是 CHAR_BIT。 calloc的第一个参数不是错了吗？我认为应该是(size + WORD_BITS - 1) / WORD_BITS，因为这是所需的无符号整数的数量。 也可以将(idx % WORD_BITS) 简化为(idx &amp; (WORD_BITS - 1))，但一个好的编译器可能会自动进行优化。【参考方案2】：

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

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

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

【讨论】：

这对于一小部分标志来说不是一个坏主意，但是如果你使用一个位集，你通常希望它可以被一个整数索引。例如，参见 Java bitset 类。 是的，我后来想了想，然后注意到迈克发布了一些类似的内容。 在变量名中使用位域和索引会适得其反。【参考方案3】：

将其设为 unsigned int 64 数组。

【讨论】：

【参考方案4】：

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

【讨论】：

【参考方案5】：

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

【讨论】：

但这并不总能防止宏观副作用，例如尝试：int i = 0, bits; BITSET(bits, i++) @LukeSmith 你说得有道理，但它看起来相当广泛使用。似乎实现宏的正确方法是让调用者理解它是一个宏，从而将责任推给调用者。 （任何不喜欢的人，可以将它包装在一个内联函数中）【参考方案6】：

您可以使用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, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6

【讨论】：

【参考方案7】：

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

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

【讨论】：

C ++枚举标志与位集

】C++枚举标志与位集【英文标题】：C++enumflagsvsbitset【发布时间】：2018-01-1410:56:24【问题描述】：使用位集优于枚举标志的优点/缺点是什么？namespaceFlagenumStateRead=1<<0,Write=1<<1,Binary=1<<2,;namespacePlainenumStateRead,Write,Binary... 查看详情

在 C++ 中将字符或字符串转换为位集

...字符串转换，更不用说将字符转换为位集了。谁能告诉我如何在C++中将单个字符转换为位集？【问题讨论】：std::bitset接受用于构造的字符串。你考虑过使用它吗？评论应该被接受。【参考方案1】：以下内容：charc 查看详情

可变大小的位集[重复]

...素并为此定义位集。但问题是bitset需要一个常量值，所以如何克服这个问题，下面是我的一些问题：a)我可以用可变大小定义位集吗？b)如果不是，那么使用vector&lt;boo 查看详情

如何将结构从 C++ 迁移到 C#

】如何将结构从C++迁移到C#【英文标题】：HowtoMigratestructsformC++toC#【发布时间】：2012-06-2114:26:12【问题描述】：我正在编写一个接收复杂数据结构的UDP客户端。我确实有C++中的结构，但我的程序是C#Bitfiels和联合有很多不同的结构... 查看详情

如何在 C 中实现回调函数？

】如何在C中实现回调函数？【英文标题】：HowdoIimplementcallbackfunctionsinC?【发布时间】：2010-05-0814:59:11【问题描述】：gcc4.4.3c89我正在创建一个客户端服务器应用程序，我需要实现一些回调函数。但是，我在回调方面没有太多经验... 查看详情

如何在 C 中实现多分支树结构

】如何在C中实现多分支树结构【英文标题】：HowtoimplementamultibranchtreestructureinC【发布时间】：2011-08-2713:14:14【问题描述】：我很久没有用C写代码了。我正在尝试做一棵多叶树。我正在尝试将C#trie实现转换为C，以便使用CUDA在GPU... 查看详情

如何在 C 中实现链表？

】如何在C中实现链表？【英文标题】：HowtoimplementalinkedlistinC?【发布时间】：2010-11-0205:09:47【问题描述】：我正在创建一个linkedlist，就像我问的上一个问题一样。我发现开发链表的最佳方法是将头部和尾部置于另一种结构中。... 查看详情

如何在 C#/Silverlight 中实现带通滤波器

】如何在C#/Silverlight中实现带通滤波器【英文标题】：Howtoimplementaband-passfilterinc#/Silverlight【发布时间】：2009-11-0314:37:56【问题描述】：如何在C#中实现带通滤波器？我在Silverlight中使用自定义MediaStreamSource并使用加法合成来产生声... 查看详情

如何在 C 中实现无锁共享标志？

】如何在C中实现无锁共享标志？【英文标题】：Howtoimplementalock-freesharedflaginC?【发布时间】：2012-10-0819:45:50【问题描述】：我有一个生产者一消费者模型，我需要生产者在数据可用时设置一个标志。我怀疑我可以在没有锁定共享... 查看详情

在初始化时定义位集大小？

】在初始化时定义位集大小？【英文标题】：Definebitsetsizeatinitialization?【发布时间】：2011-03-0906:17:50【问题描述】：我想用C++做一个bitset。我做了一些研究。我发现的所有示例都是这样的：bitset<6>myBitset;//dosomethingwithit但是... 查看详情

在 SSE 中使用位集的实现和性能

】在SSE中使用位集的实现和性能【英文标题】：ImplementationandperformanceofusingbitsetswithSSE【发布时间】：2012-05-2915:28:07【问题描述】：我正在尝试使用SSE（在VisualStudio上）加快我的方法。我是该地区的新手。我在我的方法中使用的... 查看详情

如何在 C++ 中实现这个结果？指向数组的数组

】如何在C++中实现这个结果？指向数组的数组【英文标题】：HowcanIachievethisresultinc++?Arrayspointingtoarrays【发布时间】：2015-02-0810:14:31【问题描述】：我正在尝试使用c/c++执行以下操作。为了解释代码应该如何工作，我编写了这个示... 查看详情

如何在没有中间副本的情况下在标准 C 中实现 memmove？

】如何在没有中间副本的情况下在标准C中实现memmove？【英文标题】：HowtoimplementmemmoveinstandardCwithoutanintermediatecopy?【发布时间】：2011-04-3017:09:00【问题描述】：来自我系统上的手册页：void*memmove(void*dst,constvoid*src,size_tlen);描述memm... 查看详情

如何在选择案例语句中实现枚举

】如何在选择案例语句中实现枚举【英文标题】：HowtoimplementEnuminselectcasestatement【发布时间】：2014-01-0718:33:32【问题描述】：我有一个包含许多项目的枚举，我想在VB.NET的selectcase语句中实现这些项目，就像我们在c#.net中所做的... 查看详情

如何在 Qt/C++/QML 中实现类似 WPF 的 MVVM？

】如何在Qt/C++/QML中实现类似WPF的MVVM？【英文标题】：HowtoimplementWPF-likeMVVMinQt/C++/QML?【发布时间】：2013-09-0601:00:21【问题描述】：我正在编写一个概念验证应用程序，这非常简单。基本上它由一个UI组成，其中在QMLListView中显示“... 查看详情

在 C 中实现 HashMap [关闭]

...hMapinC[closed]【发布时间】：2010-10-2417:11:08【问题描述】：如何像C++STL中那样从头开始在C中创建Hashmap？将考虑哪些参数以及如何测试哈希图？例如，在您可以说您的哈希图已完成之前，您将运行的基准测试用例是什么？【问题讨... 查看详情

如何在 C++11 中实现 make_unique 函数？ [复制]

】如何在C++11中实现make_unique函数？[复制]【英文标题】：Howtoimplementmake_uniquefunctioninC++11?[duplicate]【发布时间】：2013-07-2723:11:13【问题描述】：我的编译器不支持make_unique。一个怎么写？template<classT,class...Args>unique_ptr<T>mak... 查看详情

如何在 GUI 中实现我的 while 循环以使用 Visual Studio 在 C/C++ 中保持按键

】如何在GUI中实现我的while循环以使用VisualStudio在C/C++中保持按键【英文标题】：HowtoimplementmywhileloopintoaGUItokeeppressingakeyinC/C++usingvisualstudios【发布时间】：2020-02-1417:39:37【问题描述】：我有在CMD上工作的代码，我可以在其中键入1... 查看详情