Concatenating Bits in C++

Question

I am developing a software for convolution encoder and bit puncturing.

So in my program a 55 bit length data is generated in every loop. It is stored in the first 55 bits of unsigned long long type variable. After every iteration I have to transfer these 55 bits into a buffer of unsigned char (Buffer is quite large say around 500 Bytes). The bits must be continuously stored in this buffer. (i.e no gaps). Is there some bit trick to concatenate like this easily?

Answer 1

EDIT: It was correctly pointed out to me that, because I'm aliasing the char-buffer through a uint64_t*, I am violating the strict aliasing rule, and am also vulnerable to bugs due to differences in endianness. Nevertheless, if you have certain guarantees about your platform, this might still work. It can be resolved by having a buffer of 64-bit elements though, instead of single bytes.

In case you want a barebone algorithm that does not depend on any external libraries, you could use the snippet below. Note that bitset is only used to display the result and make sure that it works.

As a test, I defined a 55-bit pattern consisting of 54 consecutive 1's, followed by a 0. The remaining 9 bits in the 64-bit value (x) are also zeros. The buffer is a 500-byte character-array, which I aliased in auint64_t*. The algorithm keeps track of the current 64-bit block (currentBlock) and the current bit within this block (currentBit). It does the following:

1. Shift the bitpattern such that it starts at the current bit-position.
2. OR the result with the current 64-bit block. This means that the first part of the bit-pattern is concatenated to whatever is left of the current block. For example, in the second iteration when the first 55 bits of the first block are filled, the remaining 9 bits will be occupied.
3. Update the currentBit variable.

4. Check if the currentBlock was overflowed, if so move to the next block and concatenate the remainder of the 55-bitpattern.

   #include <iostream>
   #include <bitset> // only used for testing, not for the algorithm
   using namespace std;
   
   int main()
   {
       size_t nBits = 55;
   
       // 54 1's, followed by 10 0's
       uint64_t x = 0b1111111111111111111111111111111111111111111111111111110000000000;
   
       // 500 byte buffer:
       char buf8[500]{};
       uint64_t *buf = reinterpret_cast<uint64_t*>(&buf8[0]);
   
       // This would be better; use this if possible
       // uint64_t buf[100];
   
       int currentBit = 0;
       int currentBlock = 0;
   
       // concatenate the 55-bitpattern 10 times 
       for (int i = 0; i != 10; ++i)
       {
           buf[currentBlock] |= (x >> currentBit);
   
           currentBit += nBits;
           if (currentBit >= 64)
           {
               ++currentBlock;
               currentBit %= 64;
   
               buf[currentBlock] |= x << (nBits - currentBit);
           }
       }
   
       // TEST
       for (int i = 0; i != 5; ++i)
           cout << bitset<64>(buf[i]) << '\n';
   }
   

You should probably generalize this and encapsulate it in a function. This is up to you. The program as is produces the following output:

1111111111111111111111111111111111111111111111111111110111111111
1111111111111111111111111111111111111111111110111111111111111111
1111111111111111111111111111111111110111111111111111111111111111
1111111111111111111111111110111111111111111111111111111111111111
1111111111111111110111111111111111111111111111111111111111111111

Note the 0's marking every 55'th bit.

Answer 2

I wrote this class a while ago when I needed to deal with bits. It might be useful to you as well. Here it is:

#include <deque>
#include <vector>
#include <algorithm>

class bitStream {
public:
    bitStream() {}

    /// Copies the data from another bitStream into this one upon construction
    bitStream(const bitStream& bStream, bool reverse=false) {
        this->appendData(bStream, reverse);
    }

    /// Copies the data from a vector of booleans upon construction
    bitStream(const vector<bool>& vec, bool reverse=false) {
        this->appendData(vec, reverse);
    }

    /// Appends data to the stream from a uint64_t type. The lower-n bits will be appended, starting with the highest bit of those by default.
    void        appendData(uint64_t data, size_t n, bool reverse=false) {
        deque<bool> _buffer;
        n = (n>64)?64:n;
        for (int i=0; i<n; i++) {
            _oneBit tmp;
            tmp.data = data;
            _buffer.push_back(tmp.data);
            data >>= 0x1;
        }
        if (!reverse) std::reverse(_buffer.begin(), _buffer.end());
        for (const auto v: _buffer) _data.push_back(v);
    }

    /// Appends data to the stream from a C-style array of booleans
    void        appendData(bool* data, size_t n, bool reverse=false) {
        if (reverse) {
            for (int i=0; i<n; i++) this->appendBit(*(data+(n-i-1)));
        } else {
            for (int i=0; i<n; i++) this->appendBit(*(data+i));
        }
    }

    /// Appends data to the stream from a vector of booleans
    void        appendData(const vector<bool>& vec, bool reverse=false) {
        if (reverse) {
            for (auto i = vec.size()-1; vec.size() > i; --i) this->appendBit(vec.at(i));
        } else {
            for (const auto& v : vec) this->appendBit(v);
        }
    }

    /// Appends a single bit
    void        appendBit(bool bit) {
        _data.push_back(bit);
    }

    /// Appends the bits from another bitStream object to this one
    void        appendData(const bitStream& bStream, bool reverse=false) {
        if (!bStream.getSize()) return;
        if (reverse) {
            for (int i=0; i<bStream.getSize(); i++) this->appendBit(*(bStream.getData()+(bStream.getSize()-i-1)));
        } else {
            for (int i=0; i<bStream.getSize(); i++) this->appendBit(*(bStream.getData()+i));
        }
    }

    /// Returns a pointer to the begining of the data (read-only!)
    const bool* getData() const { return &_data.front(); }

    /// Reference to the bit at a specified position (assignable, but at lest n+1 elements must exist before calling!)
    bool& operator[] (size_t n) {
        if (n>_data.size()-1) throw runtime_error("Out of range!");
        return _data.at(n);
    }

    /// Fills your vector with the data chopped up into "sizeof(T)"-byte pieces.
    template <typename T>
    void        getDataAsVector(vector<T>& vec) {
        vec.clear();
        size_t oSize = sizeof(T)*8;
        T tmp = 0x0;
        for (int i=0; i<_data.size(); i++) {
            if (!(i%oSize) && i) {
                vec.push_back(tmp);
                tmp = 0x0;
            }
            tmp <<= 0x1;
            tmp |= _data[i];
        }
        vec.push_back(tmp);
    }

    /// Returns the number of bits that are stored
    size_t      getSize() const { return _data.size(); }

    /// Reverses the stored bits
    void        reverse() { std::reverse(_data.begin(), _data.end()); }
private:
    deque<bool> _data;
    struct _oneBit {
        uint8_t data:1;
    };
};

It's fairly trivial to use, so I didn't bother writing an example.

First of all, I never actually ended up using it in a project, so there might be some bugs in there (I remember only testing it very briefly), plus it's not finished completely (there are a couple of possible constructors that I haven't implemented). Also, despite the name "stream", it has nothing to do with what a stream is in C++.

So basically it lets you store bits. The bits you put in it, will be stored at contiguous memory addresses (yes, that's one bit per byte of memory, but whatever), which stay the same for the lifetime of the object (this is because a deque doesn't reallocate itself unlike a vector)! You can append bits to it in various ways (from different data sources, in reversed or non-reversed order), and read them back in different forms as well. In your case, the appendData(uint64_t data, size_t n, bool reverse=false) function is the one you can use to fill it up. To get your data back, you can have a vector<char> filled up with the data chopped into 1-byte pieces (characters), if you want it to!

Again, please don't take this as a 100% tested and working thing. I only tested it briefly, so you should try it out and see if it works for you! I thought I'd share it with you, in case you find it helpful.