logo标签列表

C# - 左移整个字节数组

c#
20

在 C# 中，是否有一种方法可以对整个字节数组进行右/左移位操作（并在最后一位添加一个字节以防止丢失）？

我知道这听起来像是一个奇怪的请求，但我仍然想知道是否可能以及如何开始实现它。

是的：这是可能的。不：这不是标准的。方法：对每个字节应用移位，并带有进位。根据扩展语义，可能需要创建一个新数组。 - user166390
@pst，我认为你应该将你的评论重新创建为一个答案。 - neontapir
如果使用.NET 4，您可以尝试使用 BigInteger。 - leppie
1
你是指在单个位的级别上进行移位（例如，“将每个字节向左移动3位并带有进位”），还是一次移动整个字节（例如，“在前面/后面添加另一个字节”）？起初我假设是前者，但现在... - user166390
我感觉这是关于位移的问题。我正在寻找字节移位。所以我想检查一下Array.Copy()是否适合我正在做的事情。无论如何。 - Bitterblue
8个回答
4

仅供娱乐。移动和旋转字节数组中的字节。(不是位移)

向左移位，填充零：

mybytes.Skip(1).Concat(new byte[] { 0 }).ToArray();

向右移位，填充零：

(new byte[] {0}).Concat(mybytes.Take(mybytes.Length - 1)).ToArray();

向左旋转：

mybytes.Skip(1).Concat(mybytes.Take(1)).ToArray();

向右旋转：

mybytes.Skip(mbytes.Length - 1).Concat(mbytes.Take(mbytes.Length - 1)).ToArray();

似乎他正在寻找一种移动奇数位的方法，这些位不代表整个字节。 - Ben Voigt
1
“在特定的一侧添加一个字节”听起来像是字节移位。 - dthorpe
如果您左移七位，字节数可能会增加。我非常确定这就是问题的意思。而“所以位不会丢失”告诉我您绝对不应该调用Skip函数。 - Ben Voigt
我理解为“位移并进行字节扩展”：P~ - user166390
好的，如果我误读了问题，那就让位移操作的答案得到投票。对于字节移位，我发现 Linq 的解决方案很有趣。;> - dthorpe
3

是的，您可以。请看我写的以下方法：

/// <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是有符号的，当你不想要符号传播时？） - Ben Voigt
1
根据Ben Voigt的批评，编辑此内容。 - JamieSee
它们实际上并不需要，只是因为我开始组合这个项目时的产物。我已经将它们移除了。感谢您指出这一点，@MartinMulder。 - JamieSee
1

看起来你正在对大量位进行位运算，并将它们存储在字节数组中。考虑使用BitArray类和BitVector32结构。根据你对位的操作，你可以创建一个像这样的类。请注意，移位的时间复杂度为O(1)，而不是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();
    }
}
但是这两种类型都不包含本地适当的位移操作。这里有一个它们如何使用的示例吗？ - user166390
不确定这样做有什么帮助，因为BitArray没有提供任何移位运算符或方法。 - Ben Voigt
这取决于你最终要对数据做什么。如果你将位存储在 BitArray 中，你可以在一个整数中存储指向起始索引的指针。移位操作将是 - 在末尾添加一个元素并将起始指针向右移动一个位置。这将以 O(1) 的时间复杂度运行。如果你有一系列位操作而不仅仅是这个移位操作，使用 BitArray 可能是一个好主意。 - George Mamaladze
+1，如果频繁进行移位且完全枚举不频繁，则此解决方案很好。 - Dan Bryant
1
我再仔细想了想，意识到这可能更适合这个问题：
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;
}

可以使用类似的技巧来进行右移操作。
0

左移：

for (int i = byteArray.Length - 1; i >= 0; i--) byteArray[i] = (byte)((byteArray[i] << 1) | ((i == 0) ? 0 : byteArray[i - 1] >> 7));

右移：

for (int i = 0; i <= byteArray.Length - 1; i++) byteArray[i] = (byte)((byteArray[i] >> 1) | ((i == byteArray.Length - 1) ? 0 : byteArray[i + 1] << 7));
0

Linq方式：

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();
    }
}
呸！这是一个字节数组！ - Bitterblue
0

我认为没有内置的方法。我实现了你在下面描述的左移操作（假设是小端）。它不像使用x86汇编语言那样优雅（带进位指令），但与使用C语言相当接近。

或者，你几乎可以使用BigInteger结构体（.NET 4及以上版本），它有一个以字节数组为参数的构造函数和一个ToByteArray方法。但它的左移操作会符号扩展高字节，右移操作会截断。因此，你需要对两者进行补偿，才能得到你所描述的精确行为。

    // 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);
    }
0

这两个函数将按指定的数量移动字节数组中的位，根据需要将它们移动到相邻的字节中。可选地，它们可以将数组的位从一端包装到另一端。请注意，它们创建一个新的数组，但代码可以轻松更改以修改传递的“数组”...

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;
        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 ʀ;
    }
}
你的左位移代码有问题。ʀ[] 数组不存在，但它会反复尝试使用它。我试图建议编辑，但“建议的编辑队列已满”。 - Daniel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接