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

Question

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

Please specify exactly what your input is, looks like, and what type it has and what your output should be, look like and what type it has. It's a bit unclear. — orlp
– orlp, Commented Mar 10, 2012 at 15:05
The input are unsigned long long ints of any value and the output is an char * array (array of bytes). I need to write the output to a file so I need to have it in bytes. — Smaug
– Smaug, Commented Mar 10, 2012 at 15:08
Due to endian-ness you'll have to specify how things are stored now and supposed to be stored afterwards on a byte level, not a mix between bytes and long long ints. — Joachim Isaksson
– Joachim Isaksson, Commented Mar 10, 2012 at 15:09

strcat · Accepted Answer · 2012-03-10 15:24:31Z

4

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";
}

answered Mar 10, 2012 at 15:24

strcat

5,6632 gold badges31 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Chad Over a year ago

This is nice, combine with the trim_right() function examples from my answer below for likely the simplest possible solution.

jkerian · Accepted Answer · 2012-03-10 15:19:12Z

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.

Chad · Accepted Answer · 2012-03-10 15:35:49Z

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;
}

6502 · Accepted Answer · 2012-03-10 16:07:13Z

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

Collectives™ on Stack Overflow

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

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related