How to put bit sequence into bytes (C/C++)

I have a couple of integers, for example (in binary represetation):

00001000, 01111111, 10000000, 00000001

and I need to put them in sequence to array of bytes(chars), without the leading zeros, like so:

10001111 11110000 0001000

I understand that it is must be done by bit shifting with <<,>> and using binary or |. But I can't find the correct algorithm, can you suggest the best approach?

The integers I need to put there are unsigned long long ints, so the length of one can be anywhere from 1 bit to 8 bytes (64 bits).

4 Answers
  1. You could use a std::bitset:

    #include <bitset>
    #include <iostream>
    
    int main() {
        unsigned i = 242122534;
        std::bitset<sizeof(i) * 8> bits;
        bits = i;
        std::cout << bits.to_string() << "\n";
    }
    
    strcat2012-03-10 15:24:31
  2. There are doubtless other ways of doing it, but I would probably go with the simplest:

    std::vector<unsigned char> integers; // Has your list of bytes
    integers.push_back(0x02);
    integers.push_back(0xFF);
    integers.push_back(0x00);
    integers.push_back(0x10);
    integers.push_back(0x01);
    std::string str;                     // Will have your resulting string
    for(unsigned int i=0; i < integers.size(); i++)
        for(int j=0; j<8; j++)
            str += ((integers[i]<<j) & 0x80 ? "1" : "0");
    std::cout << str << "\n";
    size_t begin = str.find("1");
    if(begin > 0) str.erase(0,begin);
    std::cout << str << "\n";
    

    I wrote this up before you mentioned that you were using long ints or whatnot, but that doesn't actually change very much of this. The mask needs to change, and the j loop variable, but otherwise the above should work.

    jkerian2012-03-10 15:19:12
  3. Convert them to strings, then erase all leading zeros:

    #include <iostream>
    #include <sstream>
    #include <string>
    #include <cstdint>
    
    std::string to_bin(uint64_t v)
    {
       std::stringstream ss;
    
       for(size_t x = 0; x < 64; ++x)
       {
           if(v & 0x8000000000000000)
              ss << "1";
           else
              ss << "0";
    
            v <<= 1;
       }
    
       return ss.str();
    }
    
    void trim_right(std::string& in)
    {
       size_t non_zero = in.find_first_not_of("0");
    
       if(std::string::npos != non_zero)
          in.erase(in.begin(), in.begin() + non_zero);
       else
       {
           // no 1 in data set, what to do?
           in = "<no data>";
       }
    }
    
    int main()
    {
      uint64_t v1 = 437148234;
      uint64_t v2 = 1;
      uint64_t v3 = 0;
    
      std::string v1s = to_bin(v1);
      std::string v2s = to_bin(v2);
      std::string v3s = to_bin(v3);
    
      trim_right(v1s);
      trim_right(v2s);
      trim_right(v3s);
    
      std::cout << v1s << "\n"
                << v2s << "\n"
                << v3s << "\n";
    
      return 0;
    }
    
    Chad2012-03-10 15:35:49
  4. A simple approach would be having the "current byte" (acc in the following), the associated number of used bits in it (bitcount) and a vector of fully processed bytes (output):

    int acc = 0;
    int bitcount = 0;
    std::vector<unsigned char> output;
    
    void writeBits(int size, unsigned long long x)
    {
        while (size > 0)
        {
            // sz = How many bit we're about to copy
            int sz = size;
    
            // max avail space in acc
            if (sz > 8 - bitcount) sz = 8 - bitcount;
    
            // get the bits
            acc |= ((x >> (size - sz)) << (8 - bitcount - sz));
    
            // zero them off in x
            x &= (1 << (size - sz)) - 1;
    
            // acc got bigger and x got smaller
            bitcount += sz;
            size -= sz;
    
            if (bitcount == 8)
            {
                // got a full byte!
                output.push_back(acc);
                acc = bitcount = 0;
            }
        }
    }
    
    void writeNumber(unsigned long long x)
    {
        // How big is it?
        int size = 0;
        while (size < 64 && x >= (1ULL << size))
            size++;
        writeBits(size, x);
    }
    

    Note that at the end of the processing you should check if there is any bit still in the accumulator (bitcount > 0) and you should flush them in that case by doing a output.push_back(acc);.

    Note also that if speed is an issue then probably using a bigger accumulator is a good idea (however the output will depend on machine endianness) and also that discovering how many bits are used in a number can be made much faster than a linear search in C++ (for example x86 has a special machine language instruction BSR dedicated to this).

    2012-03-10 16:07:13
Related Articles
You Might Also Like