C中位数组的结构

Question

我注意到 C 中没有针对单个位的内置结构。有 (unsigned) char 和 int，它们是 8 位（一个字节），long 是 64 位以上，依此类推 (uint64_t, bool...)

我在编写霍夫曼树时遇到了这个问题，某些字符的编码不一定正好是 8 位长（例如 00101），因此没有有效的方法来存储编码。我必须找到临时解决方案，例如字符串或布尔数组，但这需要更多的内存。

但无论如何，我的问题更笼统：是否有存储数组位或某种用户定义结构的好方法？我在网上搜索了一个，但最小的结构似乎是 8 位（一个字节）。我试过 int a : 1 之类的东西，但没有用。我阅读了有关位字段的信息，但它们并不能完全实现我想要做的事情。我知道在 C++ 中已经有人问过这个问题，如果有一个位的结构，但主要是我想知道在 C 中存储诸如 00101 之类的编码的最有效内存方式是什么。

Answer 1

It has come to my attention that there is no builtin structure for a single bit in C.

这是真的，而且这是有道理的，因为基本上没有机器具有位可寻址内存。

But anyways, my question is more general: is there a good way to store an array of bits, or some sort of user-defined struct?

通常使用 unsigned char 或其他无符号整数类型，或此类数组。除此之外，您还需要一些屏蔽和移位来设置或读取各个位的值。

I scoured the web for one but the smallest structure seems to be 8 bits (one byte).

从技术上讲，最小的可寻址存储单元 ([[un]signed] char) 可能大于 8 位，尽管您不太可能看到这一点。

I tried things such as int a : 1 but it didn't work. I read about bit fields but they do not simply achieve exactly what I want to do.

位域只能作为结构成员出现。包含此类位域的结构对象的大小仍将是 char 大小的倍数，因此不能很好地映射到位数组或位数组的任何部分。

I know questions have already been asked about this in C++ and if there is a struct for a single bit, but mostly I want to know specifically what would be the most memory-efficient way to store an encoding such as 00101 in C.

如果您需要一个位模式和一个单独的位计数——例如如果位存储对象中的一些可用位实际上并不重要——那么你需要一个单独的有效位计数数据。如果您想要一个用于少量但可变位数的数据结构，那么您可能会采用以下方式：

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

当然，您可以通过为 bits 成员和 num_bits 成员选择不同的数据类型来使其更大。我敢肯定，如果您碰巧需要的话，您可以了解如何将这个概念扩展到处理任意长度的位数组。

Answer 2

如果你真的想要最大的内存效率，你可以将霍夫曼树本身编码为比特流。参见，例如：

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 节点还将包含输入代码值和树指针（如果您想要进一步紧凑，可以是数组中的整数索引）。

Answer 3

如果您主要对一次访问一个位感兴趣，您可以采用 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 |
     ---------------------------------------------------------------------------------

假设您要使用 bit 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 得到相关字节。类似地，mod 将位数加 8 会为您提供该字节内的相关位。然后，您将值 1 左移位数，得到必要的位掩码。

虽然这里有整数除法和 modulus，但被除数是 2 的幂，因此任何体面的编译器都应该用位 shifting/masking.

替换它们

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;
};

C中位数组的结构

Structure for an array of bits in C

c

arrays

struct

bit

huffman-code