bit shifts by multiple bytes

[Lee Crabtree]

I need to shift all of the values in a byte array by more than 8 bits,
meaning that values should flow from one byte to another. Since I don't
know in advance how many bits will be shifting, I can't do something
easy like putting the bytes into a long or uint and shifting that. Let
me give an example:

If I want to shift this:

10010110 00001101

one byte to the right, I need to get:

01001011 00000110 10000000

Now I know how to figure out how many bytes to add onto the end of the
array, but how do I shift the bits across bytes, as opposed to just
lopping them off?

Lee

 

[Nicholas Paldino [.NET/C# MVP]]

Lee,

I would use a BitArray instance to handle this. What you can do is flip
the bits accordingly in the bit array. Then, you can start at the end of
the array, and copy over the bits appropriately, cycling through each
position in the array.

Then, you should be able to copy the bits back to a byte array.

Hope this helps.

 

[Nick Hounsome]

I need to shift all of the values in a byte array by more than 8 bits,
meaning that values should flow from one byte to another. Since I don't
know in advance how many bits will be shifting, I can't do something easy
like putting the bytes into a long or uint and shifting that. Let me give
an example:

If I want to shift this:

10010110 00001101

one byte to the right, I need to get:

01001011 00000110 10000000

Now I know how to figure out how many bytes to add onto the end of the
array, but how do I shift the bits across bytes, as opposed to just
lopping them off?

int byteShift = shift/8;
int bitShift = shift%8;

shift whole bytes in the array by byteShift then go back and do the extra
bitShift by using an intermediary UInt16

(Beware of rounding - you probably need to round up byteShift)

 

[Nick Malik [Microsoft]]

Hi Lee,

I need to shift all of the values in a byte array by more than 8 bits,
meaning that values should flow from one byte to another. Since I don't
know in advance how many bits will be shifting, I can't do something easy
like putting the bytes into a long or uint and shifting that. Let me give
an example:

If I want to shift this:

10010110 00001101

one byte to the right, I need to get:

01001011 00000110 10000000

Now I know how to figure out how many bytes to add onto the end of the
array, but how do I shift the bits across bytes, as opposed to just
lopping them off?

Lee

First off, in your example, you shifted seven bits to the left, not one byte
(8 bits) to the right as you stated.

You have a function composed of two parts: how many whole bytes will you
shift followed by how many remainder bits will you shift. If you add the
blank bytes to the left (when shifting left), then all remainder bits you
shift will be less than 8 (because more than that would register in the
number of bytes).

Therefore, I'd start by breaking your starting number into bytes and store
each byte in the low order bits of an array of 16 bit words. First add the
necessary zero 'words' to the end of the array. Calculate the remainder
(modulo). Now, working back from the right to the left,
a) shift the low word n bits to the left
b) copy the result to a 'holding' variable.
c) truncate the high bits of your array word by using AND with 0x00FF
d) logical-right-shift your holding variable one byte to the right. You
now have the "overflow" bits in the low order byte.
e) move up to the next word in your array.
f) shift the value there n bits to the left
g) add in the overflow bits by using AND with your holding variable.
h) clear your holding variable.
i) pick up with step (b) and repeat until you reach the (high order byte)
in your word array
j) reassemble the original binary value.

--- Nick

 

[Lee Crabtree]

You're right, I wrote my example backwards. Durr.

In the end, I wound up doing just about the same thing you mentioned. I
broke up the bits to be shifted into multiples of bytes, with the
remainder being the number of bits to shift in a single byte. Then I
added all but one of the new bytes onto the front of the array. The
last byte was added to the end, and then it was a matter of moving right
to left across the array, using two bytes in a UInt16 at a time to shift.

I realize this is a reasonably pointless post, but anybody who has a
similar problem in the future should know that this method works.