CODEWITHSUNDEEP
c++compressionhuffman-code
Krish_Amrita
Krish_Amrita

Reputation:

huffman encoding

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?

Upvotes: 7

Views: 2929

Answers (5)

Loki Astari
Loki Astari

Reputation: 264401

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

Upvotes: 2

Paul Nathan
Paul Nathan

Reputation: 40309

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.

Upvotes: 1

Dan Hook
Dan Hook

Reputation: 7077

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.

Upvotes: 2

Bill the Lizard
Bill the Lizard

Reputation: 405765

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.

Upvotes: 9

klew
klew

Reputation: 14967

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.

Upvotes: 3

Related Questions