C/C++: Bitwise operators on dynamically allocated memory

Question

In C/C++, is there an easy way to apply bitwise operators (specifically left/right shifts) to dynamically allocated memory?

For example, let's say I did this:

unsigned char * bytes=new unsigned char[3];
bytes[0]=1;
bytes[1]=1;
bytes[2]=1;

I would like a way to do this:

bytes>>=2;

(then the 'bytes' would have the following values):

bytes[0]==0
bytes[1]==64
bytes[2]==64

Why the values should be that way:

After allocation, the bytes look like this:

[00000001][00000001][00000001]

But I'm looking to treat the bytes as one long string of bits, like this:

[000000010000000100000001]

A right shift by two would cause the bits to look like this:

[000000000100000001000000]

Which finally looks like this when separated back into the 3 bytes (thus the 0, 64, 64):

[00000000][01000000][01000000]

Any ideas? Should I maybe make a struct/class and overload the appropriate operators? Edit: If so, any tips on how to proceed? Note: I'm looking for a way to implement this myself (with some guidance) as a learning experience.

Answer 1

• Decouple the allocation from the accessor/mutators
• Next, see if a standard container like bitset can do the job for you
• Otherwise check out boost::dynamic_bitset
• If all fails, roll your own class

Rough example:

typedef unsigned char byte;

byte extract(byte value, int startbit, int bitcount)
{
   byte result;
   result = (byte)(value << (startbit - 1));
   result = (byte)(result >> (CHAR_BITS - bitcount));
   return result;
}

byte *right_shift(byte *bytes, size_t nbytes, size_t n) {
   byte rollover = 0;
   for (int i = 0; i < nbytes; ++i) {
     bytes[ i ] = (bytes[ i ] >> n) | (rollover < n);
     byte rollover = extract(bytes[ i ], 0, n);
   }
   return &bytes[ 0 ];
}

Answer 2

Operator overloading is syntactic sugar. It's really just a way of calling a function and passing your byte array without having it look like you are calling a function.

So I would start by writing this function

 unsigned char * ShiftBytes(unsigned char * bytes, size_t count_of_bytes, int shift);

Then if you want to wrap this up in an operator overload in order to make it easier to use or because you just prefer that syntax, you can do that as well. Or you can just call the function.

Answer 3

Here's how I would do it for two bytes:

unsigned int rollover = byte[0] & 0x3;
byte[0] >>= 2;

byte[1] = byte[1] >> 2 | (rollover << 6);

From there, you can generalize this into a loop for n bytes. For flexibility, you will want to generate the magic numbers (0x3 and 6) rather then hardcode them.

Answer 4

I'm going to assume you want bits carried from one byte to the next, as John Knoeller suggests.

The requirements here are insufficient. You need to specify the order of the bits relative to the order of the bytes - when the least significant bit falls out of one byte, does to go to the next higher or next lower byte.

What you are describing, though, used to be very common for graphics programming. You have basically described a monochrome bitmap horizontal scrolling algorithm.

Assuming that "right" means higher addresses but less significant bits (ie matching the normal writing conventions for both) a single-bit shift will be something like...

void scroll_right (unsigned char* p_Array, int p_Size)
{
  unsigned char orig_l = 0;
  unsigned char orig_r;

  unsigned char* dest = p_Array;

  while (p_Size > 0)
  {
    p_Size--;

    orig_r  = *p_Array++;
    *dest++ = (orig_l << 7) + (orig_r >> 1);

    orig_l = orig_r;
  }
}

Adapting the code for variable shift sizes shouldn't be a big problem. There's obvious opportunities for optimisation (e.g. doing 2, 4 or 8 bytes at a time) but I'll leave that to you.

To shift left, though, you should use a separate loop which should start at the highest address and work downwards.

If you want to expand "on demand", note that the orig_l variable contains the last byte above. To check for an overflow, check if (orig_l << 7) is non-zero. If your bytes are in an std::vector, inserting at either end should be no problem.

EDIT I should have said - optimising to handle 2, 4 or 8 bytes at a time will create alignment issues. When reading 2-byte words from an unaligned char array, for instance, it's best to do the odd byte read first so that later word reads are all at even addresses up until the end of the loop.

On x86 this isn't necessary, but it is a lot faster. On some processors it's necessary. Just do a switch based on the base (address & 1), (address & 3) or (address & 7) to handle the first few bytes at the start, before the loop. You also need to special case the trailing bytes after the main loop.

Answer 5

I'd look into something similar to this:

#define number_of_bytes 3

template<size_t num_bytes>
union MyUnion
{
    char            bytes[num_bytes];
    __int64         ints[num_bytes / sizeof(__int64) + 1];
};

void main()
{
    MyUnion<number_of_bytes> mu;
    mu.bytes[0] = 1;
    mu.bytes[1] = 1;
    mu.bytes[2] = 1;
    mu.ints[0] >>= 2;
}

Just play with it. You'll get the idea I believe.