CODEWITHSUNDEEP
c++bithuffman-code
user9506206
user9506206

Reputation: 11

How to store Huffman's transformed binary code?

I have one example:

string str = "01100111 011011 011 0110011011 0111101 "

There is no data type to hold a bit.

First, i dynamically allocate three bytes;

BYTE* store = new BYTE[3];

Second, put the binary code <- i can't code this.

Third, if it is larger than the specified size, it is increased by 3 bytes.

How do i code it?

Upvotes: 0

Views: 256

Answers (2)

Stephan Lechner
Stephan Lechner

Reputation: 35154

There is a datatype std::bitset in the standard library; unfortunately, it's size needs to be a constexpr, such that you can't define it dynamically (e.g. depending on the size of your content / string).

A way to achieve the behaviour you want is to use std::vector<bool>:

int main() {
    string str = "01100111 011011 011 0110011011 0111101 ";

    //bitset<70> bits(str); // requires 70 as constexpr

    vector<bool> bits;
    for (auto c : str) {
        if (c=='1')
            bits.push_back(true);
        else if (c=='0')
            bits.push_back(false);
        else {
            // ignore
        }
    }

    for (auto bit : bits) {
        cout << bit;
    }

}

Note that datatype vector<bool> may be optimized for speed/memory consumption, but it does not have to be (cf., for example, cppreference.com - vector):

The manner in which std::vector is made space efficient (as well as whether it is optimized at all) is implementation defined.

Upvotes: 1

A P
A P

Reputation: 377

You have a few options:

1) Use a std::vector<bool>

This is probably the most C++-like way of doing it. The std::vector is specialized for bools, where it stores each boolean as a bit. It also allocates memory for you, so you don't have to worry about resizing the vector if there are more bits.

There is a downside of having to go through a reference class to access the bits directly, and using bitwise operators with a std::vector<bool> is a bit awkward.

2) Bitwise shift operators

C++ also has the operators <<, >>, <<=, and >>= that can be used to move bits. The << operator shifts all of the bits to the left, and >> shifts them to the right. <<= and >>= are to << and >>, like += is to +.

Here is an example of them:

unsigned char bits = 0b10010010 // uses binary literal syntax
bits <<= 1 // each bit in the variable is shifted left by one, making
           // the bits be `00100100`. Note that the overflow is ignored.

bits >>= 2 // bits is now `00001001`

You can use these in conjunction with the AND and OR operators (| and &) to manipulate bits.

Also, while this doesn't perfectly solve your problem alone, you also use std::bitset to represent bits. You'll still have to use the bitwise shift operators though.

Upvotes: 3

Related Questions