c - 有点在 C 中摆弄很多位

Question

我想用二进制标志来表示 C 中的数学集，其中“第 i 位已设置”表示“第 i 项在集合中”。这很方便，因为像“并集”和“交集”这样的操作实现起来很简单(“|”和“&”)。但是，我希望我的集合能够包含超过 32 个项目。此外，我希望我的代码能够在 32 位和 64 位机器上运行。

有没有简单的方法可以在 C 语言中操作多于一个字的位？有没有更好的方法来完成这项任务？

Answer 1

是的，您只需定义一个 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 类型，那可能是最安全的方法。否则，有一些已知的方法可以使用 unsigned int 使用 CHAR_BIT 和 sizeof 在运行时实际计算出使 掩码有多大 数组以及您应该使用什么值来发现数组索引和位掩码索引。

例如，我的代码库中的这个片段展示了我是如何为基于字符的位掩码做的:

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 数组)。