String into binary

Question

I used Huffman encoding that we wrote to compress a file. The function takes String and its output is String.

The problem is I want to save it as binary to get lower size than the original size, but when I take it back (0's and 1's ) as a string its size is larger than the main file. How can I convert that string of (0's and 1's) to a binary so that every character is saved in 1 bit? I am using Qt to achieve this:

string Huffman_encoding(string text)
{
    buildHuffmanTree(text);

    string encoded = "";
    unordered_map<char, string> StringEncoded;
    encoding(main_root, "", StringEncoded);

    for (char ch : text) {
        encoded += StringEncoded[ch];
    }
    return encoded;
}

Does this answer your question? [How to read/write arbitrary bits in C/C++](https://stackoverflow.com/questions/11815894/how-to-read-write-arbitrary-bits-in-c-c) — 500 - Internal Server Error, Dec 17 '21 at 12:34
This is not enough code to help you. Hoffman codes don't fit into bytes (they can for example be 3 bits or 5 bits). So you need kind of a bitstream and then write that bitstream to file. — Pepijn Kramer, Dec 17 '21 at 12:35

Botje · Answer 1 · 2021-12-17T12:45:46.880

The canonical solution uses a "bit packer" that accepts bitstrings and emits packed bytes. As a first start, replace encoded by an instance of the following:

class BitPacker {
  QByteArray res;
  quint8 bitsLeft = 8;
  quint8 buf = 0;

  public:
  void operator+=(const std::string& s) {
    for (auto c : s) {
      buf = buf << 1 | c - '0';
      if (--bitsLeft == 0) {
        res.append(buf);
        buf = 0;
        bitsLeft = 8;
      }
    }
  }

  QByteArray finish() {
    if (bitsLeft < 8) {
      res.append(buf << bitsLeft);
      buf = 0;
      bitsLeft = 8;
    }
    return res;
  }
}

operator+= will add additional bits to buf and flush complete bytes to res. At the end of the process you may be left with, say, 3 bits. finish uses a simple algorithm: it pads the buffer with zeroes to produce a final byte and hands you back the fully encoded buffer.

A more sophisticated solution might be to introduce an explicit "end of stream" token that is not present in the source character set.

codeling · Accepted Answer · 2021-12-17T12:57:49.680

1

Seems what you're searching for is a way to convert a string containing a sequence of 0s and 1s like "0000010010000000" to an actual binary representation (numbers 4 and 128 in this example).

This could be achieved with a function like this:

#include <iostream>
#include <string>

#include <cstdint>
#include <vector>

std::vector<uint8_t> toBinary(std::string const& binStr)
{
    std::vector<uint8_t> result;
    result.reserve(binStr.size() / 8);
    size_t pos = 0;
    size_t len = binStr.length();
    while (pos < len)
    {
         size_t curLen = std::min(static_cast<size_t>(8), len-pos);
         auto curStr = binStr.substr(pos, curLen) + std::string(8-curLen, '0');
         std::cout << "curLen: " << curLen << ", curStr: " << curStr << "\n";
         result.push_back(std::stoi(curStr, 0, 2));
         pos += 8;
    }
    return result;
}

// test:
int main()
{
  std::string binStr("000001001000000001");
  auto bin = toBinary(binStr);
  for (auto i: bin)
  {
    std::cout << static_cast<int>(i) << "  ";
  }
  return 0;
}

Output:

4 128 64

You can then do whatever you want with these numbers, e.g. write them into a binary file.

Note that toBinary as above, pads the last byte, if incomplete, with zeros.

edited Dec 17 '21 at 12:57

answered Dec 17 '21 at 12:35

codeling

11,056
4
42
71

@AnoopRana had pressed the submit button a bit early ;). Hope it's all good now? – codeling Dec 17 '21 at 12:46
Yes now it looks good. – Jason Dec 17 '21 at 13:09
Thanks for Trying to help but iam not trying to do that , i want them to still be 0.1 but when i save them in a file they are saving as 0's 1's not as a string of 0's and 1's ,Because String Character takes 8 bits while i want to save it as binary to take only 1 bit – Zeyad Khaled Dec 17 '21 at 13:27
not sure I understand what you mean- you want to convert a string containing '0' and '1' characters (lets call that a bit string) to actual binary data, right? that's what my function is doing. the numeric format that I convert to here takes 8 times less memory than the "bit string". and everything is binary in a computer - even a string is stored in bits; so I don't know what you mean when you "still want them be 0.1". in the computer, both representations are stored as zeros and ones in the end... – codeling Dec 17 '21 at 13:46
i Used it but do u have any idead how to save it to a file using qt ? ,thx for help – Zeyad Khaled Dec 17 '21 at 14:07
that's a new question entirely, but as a starter I would recommend looking into [QDataStream](https://doc.qt.io/qt-5/qdatastream.html) – codeling Dec 17 '21 at 14:12
This is the Only one that worked for me huge thanks to you <3 – Zeyad Khaled Dec 17 '21 at 20:49

score 1 · Answer 3 · answered Dec 17 '21 at 12:49

You can create a bitstream using bitwise logic like this :

#include <cassert>
#include <string>
#include <stdexcept>
#include <vector>


auto to_bit_stream(const std::string& bytes)
{
    std::vector<std::uint8_t> stream;
    std::uint8_t shift{ 0 };
    std::uint8_t out{ 0 };

    // allocate enough bytes to hold the bits
    // speeds up the code a bit
    stream.reserve((bytes.size() + 7) / 8);

    // loop over all bytes
    for (const auto c : bytes)
    {
        // check input
        if (!((c == '0') || (c == '1'))) throw std::invalid_argument("invalid character in input");

        // shift output by one to accept next bit
        out <<= 1;

        // keep track of number of shifts
        // after 8 shifts a byte has been filled
        shift++;

        // or the output with a 1 if needed
        out |= (c == '1');

        // complete an output byte
        if (shift == 8)
        {
            stream.push_back(out);
            out = 0;
            shift = 0;
        }
    }

    return stream;
}


int main() 
{
    // stream is 8 bits per value, values 0,1,2,3
    auto stream = to_bit_stream("00000000000000010000001000000011");

    assert(stream.size() == 4ul);
    assert(stream[0] == 0);
    assert(stream[1] == 1);
    assert(stream[2] == 2);
    assert(stream[3] == 3);
        
    return 0;
}

score 1 · Answer 4 · answered Dec 17 '21 at 12:50

1

Use std::stoi()

int n = std::stoi("01000100", nullptr, 2);

answered Dec 17 '21 at 12:50

Nanev

106
7

String into binary

4 Answers4