将整数数组转换为字节数组的快速方法(11位)

Question

我有整数数组，我需要将它转换为字节数组。

但我需要(仅和仅仅)获取ه整数数组中每个元素的前11位，然后将其转换为字节数组。

我试过这段代码

// ***********convert integer values to byte values
//***********to avoid the left zero padding on the byte array
// *********** first step : convert to binary string 
 // ***********second step : convert binary string to byte array
 // *********** first step
string ByteString = Convert.ToString(IntArray[0], 2).PadLeft(11,'0');
for (int i = 1; i < IntArray.Length; i++)
            ByteString = ByteString + Convert.ToString(IntArray[i], 2).PadLeft(11, '0');



        // ***********second step

        int numOfBytes = ByteString.Length / 8;
        byte[] bytes = new byte[numOfBytes];
        for (int i = 0; i < numOfBytes; ++i)
        {
            bytes[i] = Convert.ToByte(ByteString.Substring(8 * i, 8), 2);

        }

但是它需要太长的时间(如果文件大小很大，代码需要超过1分钟)

我需要一个非常快的代码(只有几毫秒)

有人能帮我吗？

Answer 1

基本上，你会做大量的移动和掩蔽。它的确切性质取决于您想要的布局。如果我们假设我们从每个int中打包小endian，并附加在左侧，那么两个11位整数具有位置：

abcdefghijk lmnopqrstuv

变成8位块：

defghijk  rstuvabc 00lmnopq

(即取第一个整数的最低8位，剩下3位，所以将其打包到下一个字节的低3位，然后取第二个整数的最低5位，最后取其余6位，填充为0)，然后这样的东西应该可以工作：

using System;
using System.Linq;

static class Program
{
    static string AsBinary(int val) => Convert.ToString(val, 2).PadLeft(11, '0');
    static string AsBinary(byte val) => Convert.ToString(val, 2).PadLeft(8, '0');
    static void Main()
    {
        int[] source = new int[1432];
        var rand = new Random(123456);
        for (int i = 0; i < source.Length; i++)
            source[i] = rand.Next(0, 2047); // 11 bits

        // Console.WriteLine(string.Join(" ", source.Take(5).Select(AsBinary)));


        var raw = Encode(source);
        // Console.WriteLine(string.Join(" ", raw.Take(6).Select(AsBinary)));
        var clone = Decode(raw);

        // now prove that it worked OK
        if (source.Length != clone.Length)
        {
            Console.WriteLine($"Length: {source.Length} vs {clone.Length}");
        }
        else
        {
            int failCount = 0;
            for (int i = 0; i < source.Length; i++)
            {
                if (source[i] != clone[i] && failCount++ == 0)
                {
                    Console.WriteLine($"{i}: {source[i]} vs {clone[i]}");
                }
            }
            Console.WriteLine($"Errors: {failCount}");
        }
    }
    static byte[] Encode(int[] source)
    {
        long bits = source.Length * 11;
        int len = (int)(bits / 8);
        if ((bits % 8) != 0) len++;

        byte[] arr = new byte[len];
        int bitOffset = 0, index = 0;
        for (int i = 0; i < source.Length; i++)
        {
            // note: this encodes little-endian
            int val = source[i] & 2047;
            int bitsLeft = 11;
            if(bitOffset != 0)
            {
                val = val << bitOffset;
                arr[index++] |= (byte)val;
                bitsLeft -= (8 - bitOffset);
                val >>= 8;
            }

            if(bitsLeft >= 8)
            {
                arr[index++] = (byte)val;
                bitsLeft -= 8;
                val >>= 8;
            }
            if(bitsLeft != 0)
            {
                arr[index] = (byte)val;
            }
            bitOffset = bitsLeft;
        }
        return arr;
    }

    private static int[] Decode(byte[] source)
    {
        int bits = source.Length * 8;
        int len = (int)(bits / 11);
        // note no need to worry about remaining chunks - no ambiguity since 11 > 8

        int[] arr = new int[len];
        int bitOffset = 0, index = 0;
        for(int i = 0; i < source.Length; i++)
        {
            int val = source[i] << bitOffset;
            int bitsLeftInVal = 11 - bitOffset;
            if(bitsLeftInVal > 8)
            {
                arr[index] |= val;
                bitOffset += 8;
            }
            else if(bitsLeftInVal == 8)
            {
                arr[index++] |= val;
                bitOffset = 0;
            }
            else
            {
                arr[index++] |= (val & 2047);
                if(index != arr.Length) arr[index] = val >> 11;
                bitOffset = 8 - bitsLeftInVal;
            }
        }
        return arr;

    }
}

如果您需要一个不同的布局，您将需要调整它。

在我的机器上，它在一秒钟内就编码了512 MiB。

Encode方法概述：

第一件事是预先计算所需的空间数量，并分配输出缓冲区；因为每个输入为输出贡献了11位，这只是一些模数：

    long bits = source.Length * 11;
    int len = (int)(bits / 8);
    if ((bits % 8) != 0) len++;

    byte[] arr = new byte[len];

我们知道输出位置与输入不匹配，而且我们知道每次在不同位置以字节为单位启动每个11位块，因此为这些位置分配变量，并在输入上循环：

    int bitOffset = 0, index = 0;
    for (int i = 0; i < source.Length; i++)
    {
        ...
    }
    return arr;

因此:依次接受每个输入(其中输入是位于i位置的值)，取值的低11位-并观察到我们还有11位(此值)仍需写入：

        int val = source[i] & 2047;
        int bitsLeft = 11;

现在，如果当前的输出值是部分写入的(即bitOffset != 0)，那么我们应该首先处理这个问题。当前输出中留下的空间为8 - bitOffset。因为我们总是有11个输入位，所以我们不需要担心有比值更多的空间来填充，所以:用bitOffset左移我们的值(右边的bitOffset为零，作为二进制操作)，以及输出字节的最小的8位。本质上，这表示“如果bitOffset为3，将val的5位低位写入输出缓冲区的5位高位”；最后，修正值:增加写入位置，记录仍需写入的当前值的位数减少，并使用右移丢弃val的8位低比特(由bitOffset零和8 - bitOffset“实”位组成)：

        if(bitOffset != 0)
        {
            val = val << bitOffset;
            arr[index++] |= (byte)val;
            bitsLeft -= (8 - bitOffset);
            val >>= 8;
        }

下一个问题是:我们还剩下(至少)整个字节的数据吗？例如，如果bitOffset是1(所以我们已经写了7位，只剩下4位)，我们可能不会这么做。如果我们这样做了，我们就可以将其标记下来并增加写入位置--然后再一次跟踪还剩下多少位，并丢弃低的8位：

        if(bitsLeft >= 8)
        {
            arr[index++] = (byte)val;
            bitsLeft -= 8;
            val >>= 8;
        }

我们可能还有一些遗留下来的东西；例如，如果bitOffset是7，我们会在第一个块中写1位，在第二个块中写8位，剩下2位要写-或者如果bitOffset是0，我们就不会在第一个块中写任何东西，在第二个块中写任何东西，剩下3个要写。所以，记下剩下的内容，但是不增加写入位置--我们已经写入了低位，但是下一个值可能需要写入高位。最后，将bitOffset更新为我们在最后一步中编写的许多低位数(可能为零)：

        if(bitsLeft != 0)
        {
            arr[index] = (byte)val;
        }
        bitOffset = bitsLeft;

Decode操作与此逻辑相反--再次计算大小并准备状态：

    int bits = source.Length * 8;
    int len = (int)(bits / 11);

    int[] arr = new int[len];
    int bitOffset = 0, index = 0;

现在循环输入：

    for(int i = 0; i < source.Length; i++)
    {
        ...
    }
    return arr;

现在，bitOffset是我们想要在当前11位值中写入的起始位置，所以如果我们从开始时开始，第一个字节上是0，然后是8；第二个字节的3位与第一个11位整数连接，所以这5位成为第二位的一部分，所以bitOffset在第3字节上是5，等等。我们可以通过从11中减去，来计算当前整数中剩下的位数：

        int val = source[i] << bitOffset;
        int bitsLeftInVal = 11 - bitOffset;

现在我们有三种可能的方案：

1)如果当前值中的大于8位，则可以将输入(按位“或”)标记为“或”，但不要增加写入位置(因为对于此值我们有更多的)，请注意，我们在更远的地方是8位：

        if(bitsLeftInVal > 8)
        {
            arr[index] |= val;
            bitOffset += 8;
        }

2)如果在当前值中完全保留了8位，则可以按位“或”对输入进行标记，并增加写入位置；下一个循环可以从零开始：

        else if(bitsLeftInVal == 8)
        {
            arr[index++] |= val;
            bitOffset = 0;
        }

3)否则，在当前值中只剩下不到8位；因此，我们需要将第一个bitsLeftInVal位写入当前输出位置(增加输出位置)，以及将剩馀的东西写入下一个输出位置。由于我们已经被bitOffset左移，这实际上意味着:按位“或”将低11位(val & 2047)标记到当前位置，如果不超过输出缓冲区(padding )的话，剩下的任何东西(val >> 11)将被标记到下一个。然后计算我们的新bitOffset

        else
        {
            arr[index++] |= (val & 2047);
            if(index != arr.Length) arr[index] = val >> 11;
            bitOffset = 8 - bitsLeftInVal;
        }

基本上就是这样。很多按位操作--移位(<< / >>)、掩码(&)和组合(|)。

Answer 2

如果希望将int中最小的11位存储到两个字节中，那么最小的字节具有1-8位的包含性，而最重要的字节具有9-11位：

int toStore = 123456789;
byte msb = (byte) ((toStore >> 8) & 7); //or 0b111
byte lsb = (byte) (toStore & 255); //or 0b11111111

要检查这一点，二进制数为123456789是：

0b111010110111100110100010101
                  MMMLLLLLLLL

大于L的位是lsb，其值为21，高于m的是msb，值为5。

完成这项工作的是shift操作符>>，其中所有二进制数字都滑到了右边的8个位置(其中8个从右手边消失了--它们消失了，被遗忘了)：

0b111010110111100110100010101 >> 8 =
        0b1110101101111001101 

以及掩码操作符&(掩码操作符只保留位，在每个位置上，它们在值上是1，在掩码中也是1)：

0b111010110111100110100010101 &
0b000000000000000000011111111 (255) =
0b000000000000000000000010101 

如果要处理int数组，只需在循环中这样做：

byte[] bs = new byte[ intarray.Length*2 ];
for(int x = 0, b=0; x < intarray.Length; x++){
  int toStore = intarray[x];
  bs[b++] = (byte) ((toStore >> 8) & 7);
  bs[b++] = (byte) (toStore & 255);
}