huffman encoding

Question

I am trying to implement the huffman algorithm for compression, which requires writing bits of variable length to a file. Is there any way in C++ to write variable length data with 1-bit granularity to a file?

Catalogue

Answer 1

No, the smallest amount of data you can write to a file is one byte.

You can use a bitset to make manipulating bits easier, then use an ofstream to write to file. If you don't want to use bitset, you can use the bitwise operators to manipulate your data before saving it.

Christiniachristis

Answer 2

The smallest amount of bits you can access and save is 8 = 1 byte. You can access bits in byte using bit operators ^ & |.

You can set n'th bit to 1 using:

my_byte = my_byte | (1 << n);

where n is 0 to 7.

You can set n'th bit to 0 using:

my_byte = my_byte & ((~1) << n);

You can toggle n'th bit using:

my_byte = my_byte ^ (1 << n);

More details here.

Lyford

Answer 3

klew's answer is probably the one you want, but just to add something to what Bill said, the Boost libraries have a dynamic_bitset that I found helpful in a similar situation.

Curmudgeon

Answer 4

All the info you need on bit twiddling is here:
How do you set, clear, and toggle a single bit?

But the smallest object that you can put in a file is a byte.
I would use dynamic_bitset and every time the size got bigger than 8 extract the bottom 8 bits into a char and write this to a file, then shift the remaining bits down 8 places (repeat).

Again

Answer 5

No. You will have to pack bytes. Accordingly, you will need a header in your file that specifies how many elements are in your file, because you are likely to have trailing bits that are unused.

Waylon

you don't necessary have to count the number of elements of the file a eof special character may fits the bill – Ocam