c - 我可以在 C 中分配特定数量的位吗？

Question

我正在尝试存储大量在运行时确定的布尔信息。我想知道最好的方法可能是什么。

我目前一直在尝试使用以下方法分配内存：

pStatus = malloc((<number of data points>/8) + 1);

认为这会给我足够的工作。然后我可以使用数组表示法中的指针引用每个布尔值：

pStatus[element]

不幸的是，这似乎效果不佳。首先，我很难将内存初始化为整数值0。这可以使用memset()吗？不过，我认为这不会影响我在尝试访问时崩溃的原因pStatus[element]。

我也不完全相信这种方法是最好的方法。我真正想要的本质上是一个反映布尔值状态的巨大位掩码。我错过了什么吗？

score 30 · Accepted Answer

pStatus = malloc((<number of data points>/8) + 1);

这确实为您的位分配了足够的字节。然而，

pStatus[element]

这将访问元素的第字节，而不是位。因此，当元素超过总位数的八分之一时，您将访问分配的数组的末尾。

我会定义一些辅助函数

int get_bit(int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    return ((pStatus[byte_index] & bit_mask) != 0);
}

void set_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] |= bit_mask);
}

void clear_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] &= ~bit_mask;
}

（为了清楚起见，对元素范围的错误检查。你也可以制作这个宏）

score 8 · Accepted Answer

...认为这会给我足够的工作。然后我可以使用数组表示法中的指针引用每个布尔值：

pStatus[element]

元素是寻址字节，而不是位。你想要这样的东西：

pStatus[element/8] & (1 << (element % 8))

score 5 · Accepted Answer

小点：要获得足够的内存来存储 N 位，(N/8) + 1 字节是不精确的（可以是一个太多）。

但是，(N+7)/8 始终是最小数字。

score 4 · Accepted Answer

好吧，最简单的答案是使用 calloc 而不是 malloc。

它被定义为将它分配的内存初始化为零，并且通常可以通过使用页面映射技巧来做到这一点。

这将解决您的内存初始化问题。这里的其他十几个帖子似乎充分解决了索引问题以及您偶尔分配一个额外字节的事实（哦，太可怕了！），所以我不会在这里重复他们的内容。

score 2 · Accepted Answer

pStatus[element] 将为您提供该地址的整个字节。

要设置特定元素，您可以执行以下操作：

pStatus[element >> 3] |= 1 << (element & 7);

要重置元素：

pStatus[element >> 3] &= ~1 << (element & 7);

并测试一个元素：

if (pStatus[element >> 3] & (1 << (element & 7)) != 0)

初始分配应该是

pstatus = malloc((<number of data points> + 7) / 8)

您所拥有的将起作用，但偶尔会浪费一个字节

score 2 · Accepted Answer

我不禁注意到，这里的 C 语言中的所有回复似乎都假设一个字节是 8 位。这在 C 语言中不一定是正确的（尽管在大多数主流硬件上当然是正确的），所以在代码中做出这种假设是相当糟糕的形式。

编写架构中立代码的正确方法是

#include <limits.h>

然后CHAR_BIT在需要“a 中的位数”的任何地方使用宏char。

score 1 · Accepted Answer

让自己更快乐，并定义一个类型和函数来对该类型进行操作。这样，如果您发现位访问太慢，您可以将每个布尔值的内存单位更改为字节/字/长，或者如果内存确实是一个问题（即，如果您的集合大多为零），则可以采用稀疏/动态数据结构，您可以只保留一个包含 1 坐标的列表。

您可以编写代码以完全不受位向量实现更改的影响。

score 0 · Accepted Answer

pStatus[element] 不寻址该位。它得到的确切字节取决于 pStatus 的类型——我假设是 char* 或等效的——所以 pStatus[element] 为你提供了第元素字节。

您可以将 memset 设置为 0，是的。

score 0 · Accepted Answer

 pStatus = malloc((<number of data points>/8) + 1);

那部分没问题。

 pStatus[element]

这就是你遇到麻烦的地方。当您想要寻址位时，您是地址字节。

 pStatus[element / 8 ]

将为您提供数组中的正确字节。

score 0 · Accepted Answer

您需要分配c = malloc((N+7)/8)字节，您可以使用

 c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));

清除

 c[n/8] &= ~(0x80 >> (n%8));

并测试

 if(c[n/8] & (0x80 >> (n%8))) blah();

score 0 · Accepted Answer

如果您不介意编写包装器，您也可以使用 C++ 的 STL 中的 bit_set 或 bit_vector，看起来它们（尤其是后者）正是您需要的，已经编码、测试和打包（以及大量的花里胡哨）。

很遗憾，我们缺乏在 C 应用程序中使用 C++ 代码的直接方式（不，创建包装器对我来说并不简单，也不有趣，从长远来看意味着更多的工作）。

score 0 · Accepted Answer

0

会有什么问题std::vector<bool>？

于 2008-11-20T22:46:57.893 回答

score 0 · Accepted Answer

令我惊讶的是，这里只有一个答案提到了 CHAR_BIT。一个字节通常是 8 位，但并非总是如此。

score -1 · Accepted Answer

您的分配代码是正确的，请参阅此答案set_bit()中给出的和get_bit()函数来访问布尔值。

score -1 · Accepted Answer

布尔值在 C 中“从不”是一个单独的值。所以一个结构可能是为了让你继续前进。

确实，您没有初始化 mem 区域，因此您需要单独执行此操作。

这是一个简单的示例，说明如何使用联合结构和枚举来做到这一点

typedef unsigned char           BYTE;
typedef unsigned short          WORD;
typedef unsigned long int       DWORD;
typedef unsigned long long int  DDWORD;
enum STATUS
{
    status0 = 0x01,
    status1 = 0x02,
    status2 = 0x04,
    status3 = 0x08,
    status4 = 0x10,
    status5 = 0x20,
    status6 = 0x40,
    status7 = 0x80,
status_group = status0 + status1 +status4
};
#define GET_STATUS( S ) ( ((status.DDBuf&(DDWORD)S)==(DDWORD)S) ? 1 : 0  )
#define SET_STATUS( S ) (  (status.DDBuf|=  (DDWORD)S) )
#define CLR_STATUS( S ) (  (status.DDBuf&= ~(DDWORD)S) )
static union {
 BYTE   BBuf[8];
 WORD   WWBuf[4];
 DWORD  DWBuf[2];
 DDWORD DDBuf;
}status;

int main(void)
{
    // Reset status bits
    status.BBuf[0] = 0;
    printf( "%d \n", GET_STATUS( status0 ) );

    SET_STATUS( status0 );
    printf( "%d \n", GET_STATUS( status0 ) );

    CLR_STATUS(status0);
    printf( "%d \n", GET_STATUS( status0 ) );
    SET_STATUS( status_group );
    printf( "%d \n", GET_STATUS( status0 ) );
    system( "pause" );
    return 0;
}

希望这可以帮助。此示例最多可以处理 64 个状态布尔值，并且可以轻松扩展。

此示例基于 Char = 8 bits int = 16 bits long int = 32 bits 和 long long int = 64 bits

我现在还添加了对状态组的支持。

score -1 · Accepted Answer

如果您仅限于几个位，您可以代替 eaanon01 解决方案，还可以使用位域的 c 内置工具（很少有场合可以使用它们，但这就是其中之一）

对于这个有点敲击的东西，我可以推荐：Herny Warrens “Hacker Delight”

c - 我可以在 C 中分配特定数量的位吗？

16 回答 16

Related

Reference