我想用二进制标志来表示C中的数学集,其中“Bit i set”表示“item i in the Set”。 这很方便,因为像“union”和“intersection”这样的操作实现起来很简单(“|”和“&”)。 但是,我希望我的设置能够包含超过32个项目。 此外,我希望我的代码可以在32位和64位机器上运行。
有没有简单的方法可以在C中操作多个单词的位? 有没有更好的方法来完成这项任务?
是的,您只需定义一个32位整数数组。 然后你操纵数组的特定元素。
给定0到255之间的位ID(例如),这将是一个数组:
unsigned int bits[8];
为了找到要操作的元素:
unsigned int index = bitId >> 5; // turns 0..255 into 0..31
获取给定位ID的掩码:
unsigned int masks[] = { 0x0001, 0x0002, 0x0004, 0x0008, 0x0001, 0x0020, 0x0040, 0x0080, 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000 }; unsigned int mask = masks[bitId & 0x1f];
如果您的实现中有uint32_t
类型,那么这可能是最安全的方法。 否则,有一些已知的方法可以使用CHAR_BIT
和sizeof
来使用unsigned int
,以便在运行时实际计算出masks
数组的大小以及用于发现数组索引和位掩码索引的值。
例如,我的代码库中的这个片段显示了我是如何为基于字符的位掩码做的:
static unsigned char bitmask[CHAR_BIT]; void bitsetInit (void) { unsigned char mask = 1; int i = 0; while (i < CHAR_BIT) { bitmask[i++] = mask; mask <<= 1; } }
和使用:
bsp->bits[bitnum/CHAR_BIT] &= ~bitmask[bitnum%CHAR_BIT]; bsp->bits[bitnum/CHAR_BIT] |= bitmask[bitnum%CHAR_BIT];
用于分别清除和设置位。
如果你想使用unsigned int
而不是unsigned char
你只需要计算它的位数:
unsigned int UINT_BIT = CHAR_BIT * sizeof (unsigned int);
并在我上面使用CHAR_BIT
地方使用它(如果需要,可以在运行时动态分配mask
数组)。
Gnu多精度库提供整数实现,对任意精度的整数进行非常好的优化,并且还具有最有用的位特征function。 (链接)
根据您实际需要执行的具体操作,可能会有一些奇特的数据结构可以更好地完成工作。 例如,有一个非常聪明的Disjoint Sets结构,用于建模一组不相交的集合,它在它支持的3个操作中具有真正惊人的渐近性能。
您可以使用uint64_t
。 除此之外,我担心你&
和|
运气不好 我们担心,并且应该寻找不同的设计(例如具有适当function的结构来处理它们,或者第三方库)。
paxdiablo似乎已经给你正确的方法来解决这个问题,就像你说你要解决它一样。
有没有更好的方法来完成这项任务?
除非您有特定的性能或硬件原因要在逐位进行工作,否则可能有更好的方法来表示集合。 例如,链接列表或二叉树,其值是该集合的成员。 这两种结构都可以(有效地)具有无限大小,并且易于迭代。
仅仅因为使用布尔逻辑很容易实现某些集合操作并不意味着所有操作都是如此。 如果您有一个set-type接口而不是一个boolean logic(only)接口,那么依赖于你的set操作的附加代码可能会更清楚。
无论您提出什么解决方案,我建议您将其隐藏在界面后面,以便将来更改您的存储解决方案。 您可以通过定义将结构传递给的函数来执行此操作,并仅通过这些函数对结构进行操作。
如果你真的对32位和64位类型感到满意,在现代C(又名C99)中,typedef uint_least32_t
和uint_least64_t
保证存在于"stdint.h"
。 与精确宽度类型uint32_t
和uint64_t
(可选)相反,它们可以对应于宽度比数字宽度宽的基本类型。
如果速度很重要,您也可以使用uint_fast32_t
和uint_fast64_t
,它们也必须存在。 它们以大小交易速度,并且应该使用在目标机器上具有“最快”支持的相应基本类型。 然而,对数据的爆炸可能是巨大的。 例如,在我的64位ubuntu上,所有这些“快速”类型都是64位类型。
如果您使用gcc,您还可以在64位计算机上使用__uint128_t
作为额外服务。
以上就是c/c++开发分享比特在C中捏造了很多比特相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559933.html