主页 / 问题 / 683822
Accepted
iRumba
Asked:2020-06-26 17:31:59 +0000 UTC2020-06-26 17:31:59 +0000 UTC

一组字节的位移位

  • 772

有byte[]

需要以最小的代价对其进行左移或右移。

在寻找解决方案时，我遇到了BitArray. 它的构造函数之一采用字节数组。该类允许您执行各种位运算（AND NOT OR XOR），但不允许您进行移位。

c#

6 个回答

  1. #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
    • 2

  2. 这个想法是手动复制节拍。也就是说，如果我们左移 4 位，那么我们将第 4 位复制到第 0 位，将第 5 位复制到第 1 位，依此类推。因此，例如，第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];
    }
}
    • 2

  3. 可以试试

    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

  4. 移位将不得不通过算法实现：根据循环中的移位值，需要确定当前字节的数据将落入哪个字节。字节数据分为两部分：偏移量部分和偏移量部分。

    任务不难解决，但需要时间。我建议你把任务分成几个部分，例如：将任何负面偏见变成正面偏见；跳过循环中的所有字节；将字节分成两部分 - 一个在偏移量之后脱落，​​第二个; 将新索引和偏移量在其字节中的值写入局部变量，用于当前字节的数据；在偏移索引处写入另一个相同长度的数组

    • 1 
  5. /// <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;
}
    • 1
  6. Best Answer

    结果，我得到了 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 的倍数等班次添加检查。也许这会加快整个过程，但是，正如实践所示，这种情况比每八班更不常见，并且每个条件和操作都会增加额外的执行时间。

    是的，摄政王说了一些关于字节序的事情。我开始不明白这一点，因为现在的选择完全适合我。如果您从一个类型数字中获取一组字节long并使用我的函数进行移位，那么您将获得与您首先对一个数字进行相同移位，然后从结果中获取一组字节相同的结果。来自数字的一组字节我得到一个函数BitConverter.GetBytes(theLong)

    目前，在我的计算机上，我的函数在 700-900 毫秒内执行 1000 万次移位，移位值为 0-7，时间与移位值除以 8 成反比。也就是说，相同的移位次数8-15 将比 0-7 更快完成，而 16-23 甚至更快，依此类推......

    更新程序

    指定的执行时间用于Debug。在这个版本中，一切都快了 3-4 倍。

    • 0

相关问题