In C#, is there a way to right/left shift an entire byte array (and subsequently adding a byte to a particular side for the last bit isn't lost)?
I know this sounds like a weird request, but I'd still like to know if its possible and/or how to begin doing it.
Just for grins. shifting and rotating bytes in a byte array. (not bitshifting)
shift left, zero fill:
mybytes.Skip(1).Concat(new byte[] { 0 }).ToArray();
shift right, zero fill:
(new byte[] {0}).Concat(mybytes.Take(mybytes.Length - 1)).ToArray();
rotate left:
mybytes.Skip(1).Concat(mybytes.Take(1)).ToArray();
rotate right:
mybytes.Skip(mbytes.Length - 1).Concat(mbytes.Take(mbytes.Length - 1)).ToArray();
Skip.Yes, you can. See the following methods I wrote:
/// <summary>
/// Rotates the bits in an array of bytes to the left.
/// </summary>
/// <param name="bytes">The byte array to rotate.</param>
public static void RotateLeft(byte[] bytes)
{
bool carryFlag = ShiftLeft(bytes);
if (carryFlag == true)
{
bytes[bytes.Length - 1] = (byte)(bytes[bytes.Length - 1] | 0x01);
}
}
/// <summary>
/// Rotates the bits in an array of bytes to the right.
/// </summary>
/// <param name="bytes">The byte array to rotate.</param>
public static void RotateRight(byte[] bytes)
{
bool carryFlag = ShiftRight(bytes);
if (carryFlag == true)
{
bytes[0] = (byte)(bytes[0] | 0x80);
}
}
/// <summary>
/// Shifts the bits in an array of bytes to the left.
/// </summary>
/// <param name="bytes">The byte array to shift.</param>
public static bool ShiftLeft(byte[] bytes)
{
bool leftMostCarryFlag = false;
// Iterate through the elements of the array from left to right.
for (int index = 0; index < bytes.Length; index++)
{
// If the leftmost bit of the current byte is 1 then we have a carry.
bool carryFlag = (bytes[index] & 0x80) > 0;
if (index > 0)
{
if (carryFlag == true)
{
// Apply the carry to the rightmost bit of the current bytes neighbor to the left.
bytes[index - 1] = (byte)(bytes[index - 1] | 0x01);
}
}
else
{
leftMostCarryFlag = carryFlag;
}
bytes[index] = (byte)(bytes[index] << 1);
}
return leftMostCarryFlag;
}
/// <summary>
/// Shifts the bits in an array of bytes to the right.
/// </summary>
/// <param name="bytes">The byte array to shift.</param>
public static bool ShiftRight(byte[] bytes)
{
bool rightMostCarryFlag = false;
int rightEnd = bytes.Length - 1;
// Iterate through the elements of the array right to left.
for (int index = rightEnd; index >= 0; index--)
{
// If the rightmost bit of the current byte is 1 then we have a carry.
bool carryFlag = (bytes[index] & 0x01) > 0;
if (index < rightEnd)
{
if (carryFlag == true)
{
// Apply the carry to the leftmost bit of the current bytes neighbor to the right.
bytes[index + 1] = (byte)(bytes[index + 1] | 0x80);
}
}
else
{
rightMostCarryFlag = carryFlag;
}
bytes[index] = (byte)(bytes[index] >> 1);
}
return rightMostCarryFlag;
}
workRegister signed anyway, when you don't want sign propagation?)
It seems you are performing bit operations on large amount of bits storing them in a byte array. Consider using BitArray class and BitVector32 Structure. Depending on what you are doing with bits you can create a class like this. Note that shifting works in O(1) instead of O(n).
public class BitRing : IEnumerable<bool>
{
private readonly BitArray m_InnerBitArray;
private int m_StarIndex;
public BitRing(byte[] bytes)
{
m_InnerBitArray = new BitArray(bytes);
m_StarIndex = 0;
}
public void ShiftLeft()
{
m_StarIndex++;
}
public void ShiftRight()
{
m_StarIndex--;
}
public bool this[int i]
{
get
{
int index = GetIndex(i);
return m_InnerBitArray[index];
}
set
{
int index = GetIndex(i);
m_InnerBitArray[index] = value;
}
}
private int GetIndex(int i)
{
return i - m_StarIndex%m_InnerBitArray.Count;
}
public IEnumerator<bool> GetEnumerator()
{
for (int i = m_StarIndex; i < m_InnerBitArray.Count; i++)
{
yield return m_InnerBitArray[i];
}
for (int i = 0; i < m_StarIndex; i++)
{
yield return m_InnerBitArray[i];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
BitArray doesn't provide any shifting operators or methods.
BitArray you can store a pointer to the start index in one integer. Shifting would be - adding one element at the end and moving the start pointer by one. This would work in O(1). Using BitArray might be a good idea if you have a series of bit operations and not only this one shift.
I've given it some more thought and realized that this probably fits the question better:
public static void Main()
{
byte[] bytes = new byte[] { 0xFF, 0x01, 0x80, 0x81 };
Stack<bool> bitStack = CreateBitStack(bytes);
ShiftLeftExpand(bitStack, 1);
byte[] newBytes = CreateByteArray(bitStack);
}
public static void ShiftLeftExpand(Stack<bool> bitStack, int count)
{
while (count-- > 0)
{
bitStack.Push(false);
}
}
public static Stack<bool> CreateBitStack(byte[] bytes)
{
Stack<bool> bitStack = new Stack<bool>(bytes.Length * 8);
for (int bytePosition = 0; bytePosition < bytes.Length; bytePosition++)
{
for (int bitPosition = 7; bitPosition >= 0; bitPosition--)
{
int bitMask = 0x01 << bitPosition;
bitStack.Push((bytes[bytePosition] & bitMask) > 0);
}
}
return bitStack;
}
public static byte[] CreateByteArray(Stack<bool> bitStack)
{
int newArrayLength = (int)Math.Ceiling(bitStack.Count / 8.0);
byte[] bytes = new byte[newArrayLength];
int bitCounter = 0;
while (bitStack.Count > 0)
{
bool? bitValue = bitStack.Pop();
int bitPosition = bitCounter % 8;
int bytePosition = newArrayLength - 1 - bitCounter / 8;
if (bitValue == true)
{
bytes[bytePosition] = (byte)(bytes[bytePosition] | (0x01 << bitPosition));
}
bitCounter++;
}
return bytes;
}
A similar technique can be applied to perform the right shift.
Linq way:
static class Shifter
{
public static byte[] ShiftLeft(this byte[] array, int n)
{
var a = array.Select(x => (byte)(x >> 8 - n % 8)).Concat(new byte[(7 + n) / 8]).Select((x, i) => new Tuple<int, byte>(i - (n % 8 == 0 ? 0 : 1), x));
var b = array.Select(x => (byte)(x << n % 8)).Concat(new byte[n / 8]).Select((x, i) => new Tuple<int, byte>(i, x));
return (from x in a
join y in b on x.Item1 equals y.Item1 into yy
from y in yy.DefaultIfEmpty()
select (byte)(x.Item2 | (y == null ? 0 : y.Item2))).ToArray();
}
public static byte[] ShiftRight(this byte[] array, int n)
{
return (new byte[n/8]).Concat(ShiftLeft(array, (8 - (n%8))%8)).ToArray();
}
}
I don't think there's a built-in way. I implemented the shift-left operation you described below (assuming little endian). It's not quite as elegant as you can do with x86 assembly (shift with carry instructions), but pretty close to what you could do with C.
Alternately, you can almost use the BigInteger struct (.NET 4 and above) which has a constructor that takes a byte array and a ToByteArray method. But its shift left operation sign-extends the high byte and its shift right operation truncates. So you'd need to compensate for both to get the exact behavior you described.
// Left-shifts a byte array in place. Assumes little-endian. Throws on overflow.
static public void ShiftByteArrayLeft(byte[] array)
{
if (array == null)
throw new ArgumentNullException("array");
if (array[array.Length - 1] >= 0x80)
throw new OverflowException();
// move left-to-right, left-shifting each byte
for (int i = array.Length - 1; i >= 1; --i)
{
// left-shift current byte
array[i] <<= 1;
// carry the bit from the next/right byte if needed
if (array[i - 1] >= 0x80)
++array[i];
}
// finally shift the left-shift the right-most byte
array[0] <<= 1;
}
// Left-shifts a byte array in place. Assumes little-endian. Grows array as needed.
static public void ShiftByteArrayLeftAutoGrow(ref byte[] array)
{
if (array == null)
throw new ArgumentNullException("array");
if (array[array.Length - 1] >= 0x80)
{
// allocate a bigger array and do the left-shift on it
byte[] oldArray = array;
array = new byte[oldArray.Length + 1];
Array.Copy(oldArray, 0, array, 0, oldArray.Length);
}
ShiftByteArrayLeft(array);
}
Shift left:
for (int i = byteArray.Length - 1; i >= 0; i--) byteArray[i] = (byte)((byteArray[i] << 1) | ((i == 0) ? 0 : byteArray[i - 1] >> 7));
Shift right:
for (int i = 0; i <= byteArray.Length - 1; i++) byteArray[i] = (byte)((byteArray[i] >> 1) | ((i == byteArray.Length - 1) ? 0 : byteArray[i + 1] << 7));
These two functions will shift the bits in an array of bytes the specified amount, shifting them into neighboring bytes as needed. Optionally, they can wrap the bits from one end of the array to the other. Note that they create a new array, but the code can be easily changed to modify the passed 'array' instead...
public static byte[] ShiftRight(byte[] array, int shift, bool wrap = false) {
if(shift < 0) {
throw new ArgumentOutOfRangeException("shift");
} else if(shift == 0) {
return (byte[])array.Clone();
} else {
if(wrap) shift %= (array.Length * 8);
if(shift >= (array.Length * 8)) return new byte[array.Length];
var offset = (shift / 8);
shift %= 8;
var ʀ = new byte[array.Length];
for(var ɪ = 0; ɪ < ʀ.Length; ɪ++) {
var indexL_ɪ = (ɪ + offset);
var indexH_ɪ = (ɪ + offset + 1);
if(wrap) {
if(indexL_ɪ >= array.Length) indexL_ɪ -= array.Length;
if(indexH_ɪ >= array.Length) indexH_ɪ -= array.Length;
}
if(indexL_ɪ < array.Length) ʀ[ɪ] = (byte)(array[indexL_ɪ] >> shift);
if(indexH_ɪ < array.Length) ʀ[ɪ] |= (byte)(array[indexH_ɪ] << (8 - shift));
}
return ʀ;
}
}
public static byte[] ShiftLeft(byte[] array, int shift, bool wrap = false) {
if(shift < 0) {
throw new ArgumentOutOfRangeException("shift");
} else if(shift == 0) {
return (byte[])array.Clone();
} else {
if(wrap) shift %= (array.Length * 8);
if(shift >= (array.Length * 8)) return new byte[array.Length];
var offset = (shift / 8);
shift %= 8;
var ʀ = new byte[array.Length]
for(var ɪ = 0; ɪ < ʀ.Length; ɪ++) {
var indexL_ɪ = (ɪ - offset - 1);
var indexH_ɪ = (ɪ - offset);
if(wrap) {
if(indexL_ɪ < 0) indexL_ɪ += array.Length;
if(indexH_ɪ < 0) indexH_ɪ += array.Length;
}
if(indexL_ɪ >= 0) ʀ[ɪ] = (byte)(array[indexL_ɪ] >> (8 - shift));
if(indexH_ɪ >= 0) ʀ[ɪ] |= (byte)(array[indexH_ɪ] << shift);
}
return ʀ;
}
}
ʀ[] array, but it repeatedly tries to use one. I tried to suggest an edit, but the "suggested edit queue is full".
BigInteger.Array.Copy()is ok for what I was doing. Whatever.