Copy bits in correct order

Question

In order to parse a binary stream of unmanaged data, I have to recreate data types. The data is compressed which means I read 2 bytes which actually represent a 6-bit byte value and a 10-bit short value.

All I need to do is copy a bit-sequence from one value to another. I know the start bit and length for the source value and the destination value. So far I have made two approaches which both copy the right bits but somehow in reverse order.

byte BitwiseCopy(short value, int sourceStartBit, int destStartBit, int bitCount)
{
    short result = 0;
    for (int i = 0; i < bitCount; i++)
        //result |= (byte) (value & (1 << sourceStartBit + i) | (result & (1 << (destStartBit + bitCount) - i)));
        result |= (short) (value & (1 << sourceStartBit + i));

    return (byte) (result >> ((destStartBit - bitCount) + sizeof(byte) * 8));
}

For my test scenario I am using a short with the following value:

0000 0000 1101 0011
^15               ^0

My goal is to copy the 4-th - 7-th bit of this short to a byte's 0-3rd bits.

When I use either the commented line (without the code in the return clause) approach or the way it's currently highlighted, I always get this result:

0000 1011
^7      ^0

So what I want, just reversed. I'm sure it's something tiny, but what am I overlooking here? I don't get why it reverses order. The bit-shifting approach (copying directly bitwise and shifting it to the correct position) shouldn't reverse it, should it?

EDIT: The method always has an input of type short. I have 3 parameters: sourceStart which is the bit I start to copy from the input value (low to high), destStart which is the bit I copy to into my destination (which is either byte or short - I would make two specific methods for this) and bitCount which is the amount of bits (starting from low to high order) I want to copy.

The method must copy bits in correct order. So for example CopyBitwise(input, 4, 0, 4) should return (left: high, right: low order) 0000 1011 given this input:

input [short]: ... 1011 0110
                   ^8th    ^0th

Another one:

input [short]: 1011 0110 0100 0111
               ^15th             ^0th
                    ^end ^start

CopyBitwise(input, 7, 3, 5) should result in

0011 0000
^8th    ^0th
^end ^start

Answer 1

You do not need a loop for that ! This should do the trick :

byte BitwiseCopy(short value, int sourceStartBit, int destStartBit, int bitCount){
    byte result = (byte) ((value >> sourceStartBit) << destStartBit);
    result &= (byte) ~(0xff << bitCount); // mask for zeros at the left of result
    return result;
}

Answer 2

This should work correctly. First create a mask for the bits that you require then shift them into the required place. Note that the shift is done in two moves as the shift operator must be a positive number.

byte BitwiseCopy(short value, int sourceStartBit, int destStartBit, int bitCount)
{
  short mask = (short)((0xFFFF >> (16-bitCount)) << sourceStartBit);
  short result = (short)(((value & mask) >> sourceStartBit) << destStartBit);
  return (byte)result;
}

Answer 3

It sounds like what you want is to cut out a sub-sequence of a given short. This can be achieved by masking. If you want to cut out the highlighted bits from of the following bit sequence: 1011 0110 0100 0111, you can do so by &ing it with 0000 0000 1111 0000.

  1011 0110 0100 0111
& 0000 0000 1111 0000
= 0000 0000 0100 0000

You can then shift the resulting bits, so that your masked bits start at the desired location (here 1):

  0000 0000 0100 0000 >>
 · 0000 0000 0100 000 >>
 ·· 0000 0000 0100 00 >>
 ··· 0000 0000 0100 0

---

To make it more concrete, here is some code:

byte BitwiseCopy(short value, int sourceStartBit, int destStartBit, int bitCount)
{
    ushort mask = 0; //Start with 0
    mask = (ushort)~mask; //Invert to get all 1s
    mask >>= sizeof(ushort)*8 - bitCount; //Shift right, until we have bitCount bits left
    mask <<= sourceStartBit; //Shift back left, to make sure the bits are in the right place
    
    ushort result = (ushort)value;
    result &= mask; //Mask out the bits we want
    
    //Shift the remaining bits into the desired position
    if (sourceStartBit < destStartBit)
    {
        result <<= destStartBit - sourceStartBit;
    }
    else
    {
        result >>= sourceStartBit - destStartBit;
    }
    return (byte)result;
}

Code Breakdown:

First, we assemble the bit mask. To do so, we start with 0, and then invert all the bits to get all ones. We could start with 0xFFFF, but this way the code will still work if you switch to a different-length input.

Then we shift our mask until there are only bitCount 1s left. For this step, it is important that our mask is an unsigned integer type. If you were using a signed value, the bitshift would shift in new 1s from the left.

To finish our mask, we shift it back left to position it correctly.

Next, we apply the mask to our value to cut out the bits we don't want.

Finally, we shift the result into the desired position; here it is again important to use unsigned shifts, to ensure no erroneous 1s get shifted in from the left.

---

Here's an example of what happens when calling the method with the arguments (0b1011_0110_0100_0111, 7, 3, 5), as in your second example.

mask:
  0000 0000 0000 0000  ~x
= 1111 1111 1111 1111  x>>(16 - 5)
= 0000 0000 0001 1111  x<<7
= 0000 1111 1000 0000

result:
  1011 0110 0100 0111  x&mask
  0000 0110 0000 0000  x>>(7-3)
  0000 0000 0110 0000

EDIT 1: Corrected this line mask >>= bitCount - sizeof(ushort)*8; in the code to mask >>= sizeof(ushort)*8 - bitCount;.

EDIT 2: I had also messed up the line right below, fixed that too. That's what I get for only testing one case.

EDIT 3: Added step-by-step Example.

Answer 4

I have improved the BitWiseCopy method from above so that you can copy bits not only into an empty/new byte, but also into an existing (destination).

In this example, I want to copy 3 bits (bitCount=3) from bit #4 (sourceStartBit) to bit #3 (destinationStartBit). Please note that the numbering of bits starts with "0" and that in my method, the numbering starts with the most significant bit = 0 (reading from left to right).

byte source = 0b10001110;
byte destination = 0b10110001;

byte result = CopyByteIntoByte(source, destination, 4, 1, 3);
Console.WriteLine("The binary result: " + Convert.ToString(result, toBase: 2));
//The binary result: 11110001

byte CopyByteIntoByte(byte sourceByte, byte destinationByte, int sourceStartBit, int destStartBit, int bitCount)
{
    int[] mask = { 0, 1, 3, 7, 15, 31, 63, 127, 255 };
    byte sourceMask = (byte)(mask[bitCount] << (8 - sourceStartBit - bitCount));
    byte destinationMask = (byte)(~(mask[bitCount] << (8-destStartBit - bitCount)));
    byte destinationToCopy = (byte)(destinationByte & destinationMask);
    int diff = destStartBit - sourceStartBit;
    byte sourceToCopy;
    if(diff > 0)
    {
        sourceToCopy = (byte)((sourceByte & sourceMask) >> (diff));
    }
    else
    {
        sourceToCopy = (byte)((sourceByte & sourceMask) << (diff * (-1)));
    }
    return (byte)(sourceToCopy | destinationToCopy);
}