C语言中用于位数组的结构体

Question

我注意到C语言中没有单个位的内置结构。有（无符号）char和int，它们是8位（一个字节），还有64+位的long等等（uint64_t、bool等）。我在编写哈夫曼树时遇到了这个问题，某些字符的编码不一定完全是8位长（如00101），因此没有有效的方法来存储编码。我不得不寻找临时解决方案，例如字符串或布尔数组，但这需要更多的内存。

但是，我的问题更普遍：是否有一种好的方法来存储位数组或某种用户定义的结构？我搜遍了网络，但最小的结构似乎是8位（一个字节）。我尝试了像“int a:1”这样的东西，但它不起作用。我读过关于位域的文章，但它们不能简单地实现我想做的事情。我知道已经有关于C++中是否有单个位的结构的问题，但我主要想知道在C中存储类似00101这样的编码最节省内存的方法。

- Cary Shindell

---

为什么不将其仅存储为char/int，进行位操作并使用它呢？ - Haris

不，没有办法拥有一个位数组（实际上将具有单个位大小的元素）。 - Eugene Sh.

我所能看到的最好的方法是在变量上使用掩码，无论是int还是八位元或其他类型。但这只是一个观点，因为这个问题很可能会被关闭。 - AntonH

@CaryShindell 你现在还猜不到吗？ - Eugene Sh.

是的，无论如何都需要一些额外的位来编码值的实际长度。您可以为长度使用N位，为值挤入M-N位，并将其编码为M位整数类型：或者您可以牺牲两个位使用“01”作为起始序列（因此，在16位int中，例如，您将00101编码为000000000100101，将000101编码为0000000001000101）。 - Lee Daniel Crocker

Answer 1

如果你主要想逐位访问数据，可以使用一个 unsigned char 数组，并将其视为位数组。例如：

unsigned char array[125];

假设每个字节占8位，这可以被视为一个包含1000个位的数组。前16个逻辑上看起来像这样：

     ---------------------------------------------------------------------------------
byte |                   0                   |              1                        |
     ---------------------------------------------------------------------------------
bit  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |
     ---------------------------------------------------------------------------------

假设您想要使用位 b 进行操作。你可以执行以下操作：

读取位 b：

value = (array[b/8] & (1 << (b%8)) != 0;

设置位 b：

array[b/8] |= (1 << (b%8));

清除位b：

array[b/8] &= ~(1 << (b%8));

将位数除以8可得到相应的字节。 同样，将位数模8可得到该字节内部的相关位。 然后，将值1左移位数即可得到必要的位掩码。

虽然这里涉及整数除法和模数运算，但被除数是2的幂，因此任何合理的编译器都应该用位移/屏蔽操作替换它们。

- dbush

---

有趣。但这会节省内存吗（以及多少）？ - Cary Shindell

@CaryShindell 这是存储单个位最节省内存的方法。在整个数组中，最后一个字节最多浪费7个位。 - dbush

请注意，您关于除以2的幂次方取余数的评论并不完全正确：如果b具有带符号的类型，并且编译器无法确定其值为正，则除法和取余操作不能仅简化为移位和掩码，对于负值必须进行调整，因为除法向零舍入。如果这些表达式是宏，则使用移位和掩码，如果它们是内联函数，则使用无符号类型。 - chqrlie

Answer 2

我注意到C语言没有内置的单个位结构体。这是正确的，因为实际上没有多少机器有可寻址的位存储器。通常情况下，我们会使用无符号整数类型（例如unsigned char）或其数组，并且需要使用掩码和移位来设置或读取单个位的值。技术上讲，可寻址存储单元的最小大小可以大于8位，但很少会见到这种情况。尽管可以使用位域，但位域只能作为结构体成员出现，不能很好地映射到位数组或其中的任何部分。如果您需要一个位模式和单独的位数，那么需要单独的数据来存储重要位数的计数。如果您想要一个用于小型但可变位数的数据结构，那么可能会使用类似以下内容的东西：

struct bit_array_small {
    unsigned char bits;
    unsigned char num_bits;
};

当然，你可以通过选择不同的数据类型来使bits成员和num_bits成员变得更大。如果你需要处理任意长度的位数组，我相信你可以看到如何扩展这个概念。

- John Bollinger

---

谢谢，还不错，只多了16-17个比特。 - Cary Shindell

Answer 3

如果您真的想要最高的内存效率，可以将Huffman树本身编码为一系列位流。例如，请参见：https://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html。然后将这些位编码为字节数组，可能会浪费7个位。

但那是一个可怕的想法。为了使内存中的结构有用，必须易于访问。您仍然可以非常有效地完成这项工作。假设您想要编码多达12位代码。使用16位整数和位域即可。

struct huffcode {
    uint16_t length: 4,
             value: 12;
}

C语言将其作为单个16位值存储，并允许您分别访问长度和值字段。完整的Huffman节点还包含输入代码值和树指针（如果要进一步压缩，则可以是数组中的整数索引）。

- Lee Daniel Crocker

---

谢谢！这样我们只使用不超过双倍的内存（如果我们只有位），并且我们可以一次进行多达12位的实际编码。 - Cary Shindell

不要忘记告诉编译器不要填充结构体；不同的编译器使用不同的方法。 - Lee Daniel Crocker

哦，是的，我实际上不得不自己进行冗长的填充，然后在读取文件时考虑填充...虽然有点混乱，但最终还是起作用了。 - Cary Shindell

小心。C语言实现可以自由使用单独的可寻址存储单元和/或足够大小的存储单元来存储结构中的两个位域。它们还可以在结构中包含尾部填充（这也是我的变体可能性）。C语言不能保证结构的实例将占用精确的16位内存。 - John Bollinger

Answer 4

你可以很快地创建自己的位数组。

#define ba_set(ptr, bit)   { (ptr)[(bit) >> 3] |= (char)(1 << ((bit) & 7)); }
#define ba_clear(ptr, bit) { (ptr)[(bit) >> 3] &= (char)(~(1 << ((bit) & 7))); }
#define ba_get(ptr, bit)   ( ((ptr)[(bit) >> 3] & (char)(1 << ((bit) & 7)) ?  1 : 0 )
#define ba_setbit(ptr, bit, value) { if (value) { ba_set((ptr), (bit)) } else { ba_clear((ptr), (bit)); } }


#define BITARRAY_BITS  (120)

int main()
{
    char mybits[(BITARRAY_BITS + 7) / 8];
    memset(mybits, 0, sizeof(mybits));

    ba_setbit(mybits, 33, 1);
    if (!ba_get(33))
        return 1;
    return 0;
};

- Michaël Roy