C中位数组的结构

Question

我注意到C中的单个位没有内置结构.有(无符号)char和int,它们是8位(一个字节),long是64+位,依此类推(uint64_t) ,布尔...)

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

但不管怎么说,我的问题是更普遍:有存储的一个很好的方式阵位,或某种用户定义的结构吗？我在网上搜索了一个,但最小的结构似乎是8位(一个字节).我试过这样的东西,int a : 1但它没有用.我读到了有关字段的内容,但它们并不能简单地实现我想做的事情.我知道在C++中已经有人问过这个问题,如果有一个单位的结构,但大多数情况下我想知道什么是在C中存储编码如00101的最有效内存的方法.

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

假设您想要使用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可获得相关字节.类似地,将位数修改为8会为您提供该字节内的相关位.然后,您将值1移位一位,以便为您提供必要的位掩码.

虽然这里有整数除法和模数,但被除数是2的幂,所以任何体面的编译器都应该用位移/掩码代替它们.