Bit array structure in C

Question

It occurred to me that there is no built-in structure for one bit in C. There is (unsigned) char and int, which are 8 bits (one byte) and long, which are 64 + bits, and so on (uint64_t, bool .. .)

I ran into this while encoding a Huffman tree, and the encodings for certain characters did not necessarily have exactly 8 bits (e.g. 00101), so there was no efficient way to store the encodings. I had to find temporary solutions, such as strings or logical arrays, but this takes up much more memory.

But in any case, my question is more general: is there a good way to store an array of bits or some kind of user structure? I combed the network for one, but the smallest structure seems to be 8 bits (one byte). I tried things like int a : 1, but that didn't work. I read about bit fields, but they don't just achieve exactly what I want to do. I know that C ++ has already asked questions about this, and if there is a structure for one bit, but basically I want to know specifically what will be the most memory-efficient way to store the encoding, such as 00101 in C.

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, / .

Answer 2

, C.

, , - .

: - ?

unsigned char . .

web , 8 ( ).

([[ un] signed] char) 8 , - .

, int a: 1, . , .

- . , , - , char, .

++, , , 00101 C.

- , , , -, , . , , - :

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

, , bits , , num_bits. , , - , .

Answer 3

, . . :

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 node (, , ).

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