#c_sharp #net
Есть byte[]
Требуется выполнить для него битовый сдвиг влево или вправо с минимальными затратами.
В поиске решений я наткнулся на BitArray. Один из его конструкторов принимает массив
байт. Класс позволяет выполнять различные битовые операции (AND NOT OR XOR), но не
позволяет делать сдвиги.
Ответы
Ответ 1
Можно было бы попробовать return ((new System.Numerics.BigInteger(b)) << k).ToByteArray() хотя потенциальные 3 копирования массива несколько настораживают. Впрочем, можно заглянуть в его исходники и как-то использовать соответствующий код: public static BigInteger operator <<(BigInteger value, int shift) { if (shift == 0) return value; else if (shift == Int32.MinValue) return ((value >> Int32.MaxValue) >> 1); else if (shift < 0) return value >> -shift; int digitShift = shift / kcbitUint; int smallShift = shift - (digitShift * kcbitUint); uint[] xd; int xl; bool negx; negx = GetPartsForBitManipulation(ref value, out xd, out xl); int zl = xl + digitShift + 1; uint[] zd = new uint[zl]; if (smallShift == 0) { for (int i = 0; i < xl; i++) { zd[i + digitShift] = xd[i]; } } else { int carryShift = kcbitUint - smallShift; uint carry = 0; int i; for (i = 0; i < xl; i++) { uint rot = xd[i]; zd[i + digitShift] = rot << smallShift | carry; carry = rot >> carryShift; } zd[i + digitShift] = carry; } return new BigInteger(zd, negx); }Ответ 2
#region сдвиг на 1 бит byte[] myBytes; BitArray gamma_value = new BitArray(myBytes); int len = gamma_value.Length; //длина массива бит c = gamma_value[0]; //младший бит //создание массива типа bool //такой же длины как gamma_value типа BitArray bool[] gamma_new = new bool[len]; //копируем массив типа BitArray в массив типа bool gamma_value.CopyTo(gamma_new, 0); //копируем массив bool со сдвигом на 1ну позицию в другой массив bool Array.Copy(gamma_new, 1, gamma_new, 0, len - 1); //преобразование массива типа bool в массив типа BitArray gamma_value = new BitArray(gamma_new); gamma_value.CopyTo(myBytes, 0); //переводим массив бит в массив байт #endregionОтвет 3
Идея состоит в ручном копировании битов. То есть если делаем сдвиг влево на 4 бита, то копируем в 0-й бит 4-й бит, в 1-й - 5-й и т.д. Соответственно, в, например, 15-й бит (2-й байт) копируется 19-й бит (3-й байт). Для сдвига вправо - аналогично. private static readonly byte[] bits = new byte[] { 0x80, 0x40, 0x20, 0x10, 8, 4, 2, 1 }; public static byte[] ShiftLeft(byte[] array, int shift) { var result = new byte[array.Length]; var totalLength = array.Length * 8; for (var toIndex = 0; toIndex < totalLength - shift; toIndex++) { var fromIndex = toIndex + shift; SetBit(fromIndex, toIndex, array, result); } return result; } public static byte[] ShiftRight(byte[] array, int shift) { var result = new byte[array.Length]; var totalLength = array.Length * 8; for (var toIndex = totalLength - 1; toIndex >= shift; toIndex--) { var fromIndex = toIndex - shift; SetBit(fromIndex, toIndex, array, result); } return result; } private static void SetBit(int fromIndex, int toIndex, byte[] fromArray, byte[] toArray) { var fromByte = fromArray[fromIndex / 8]; var fromBit = bits[fromIndex % 8]; if ((fromByte & fromBit) != 0) { toArray[toIndex / 8] |= bits[toIndex % 8]; } }Ответ 4
Сдвиг придётся реализовывать алгоритимчески: требуется на основе величины сдвига в цикле определить в какой байт попадут данные из текущего байта. Данные байта делятся на две части: смещённая и смещаемая часть. Задание решить несложно, но это требует времени. Советую разбить задачу на несколько частей, например: превратить любое отрицательное смещение в положительное; сделать переход по всем байтам в цикле; разбить байт на две части - та что выпала после смещения и вторая; в локальные переменные записать значения новых индексов и смещения в их байтах для данных текущего байта; записать в другой массив такой же длинны по смещённым индексамОтвет 5
////// Rotates the bits in an array of bytes to the left. /// /// The byte array to rotate. public static void RotateLeft(byte[] bytes) { bool carryFlag = ShiftLeft(bytes); if (carryFlag == true) { bytes[bytes.Length - 1] = (byte)(bytes[bytes.Length - 1] | 0x01); } } ////// Rotates the bits in an array of bytes to the right. /// /// The byte array to rotate. public static void RotateRight(byte[] bytes) { bool carryFlag = ShiftRight(bytes); if (carryFlag == true) { bytes[0] = (byte)(bytes[0] | 0x80); } } ////// Shifts the bits in an array of bytes to the left. /// /// The byte array to shift. 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; } ////// Shifts the bits in an array of bytes to the right. /// /// The byte array to shift. 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; }Ответ 6
В результате у меня получились 2 функции: Сдвиг влево public static byte[] ShiftLeft(byte[] src, int val) { var res = new byte[src.Length]; var byteShift = val >> 3; if (byteShift >= src.Length) return res; val ^= byteShift << 3; for (var i = 1; i < src.Length - byteShift; i++) res[i + byteShift] = (byte)((src[i] << val) | src[i - 1] >> 8 - val); res[byteShift] = (byte)(src[0] << val); return res; } И сдвиг вправо public static byte[] ShiftRight(byte[] src, int val) { var res = new byte[src.Length]; var byteShift = val >> 3; if (byteShift >= src.Length) return res; val ^= byteShift << 3; for (var i = byteShift; i < src.Length - 1; i++) res[i - byteShift] = (byte)((src[i] >> val) | src[i + 1] << 8 - val); res[src.Length - byteShift - 1] = (byte)(src[src.Length - 1] >> val); return res; } Функции "как есть" предполагают правильное использование. Для меня очень важна скорость, поэтому я не стал делать проверку на отрицательные значения. В идеале отрицательный сдвиг влево - это сдвиг вправо на то же число по модулю. Так же можно было добавить проверки на нулевой сдвиг, на сдвиг кратный 8 и тд. Возможно, это ускорит общий процесс, но, как показала практика, такие случаи бывают реже, чем в каждом восьмом сдвиге, а каждое условие и операция добавляют дополнительное время выполнения. И да, Regent говорил что-то про порядок байтов. Я не стал в этом разбираться, потому что тот вариант, который есть сейчас меня полностью устраивает. Если вы получите набор байт из числа типа long и выполните сдвиг моей функцией, то вы получите тот же результат, как если вы сначала выполните такой же сдвиг для числа, а затем получите из результата набор байтов. Набор байтов из числа я получаю функцией BitConverter.GetBytes(theLong) На данный момент на моем компе мои функции выполняют 10млн сдвигов за 700-900 мс при величине сдвига 0-7 и время обратно пропорционально величине сдвига деленной на 8. То есть то же самое количество сдвигов на 8-15 выполнится быстрее, чем на 0-7, а на 16-23 еще быстрее и тд... UPD Указанное время на выполнение указано для Debug. В релизе все работает в 3-4 раза быстрее.
Комментариев нет:
Отправить комментарий