C# - 从位的一部分获取整数的最快方法

Question

我有一个byte[]字节数组，通常byteArray.Length = 1-3。

我需要将数组分解为位，取出一些位（例如5-17），并将这些位转换为Int32。

我尝试过这样做：

private static IEnumerable<bool> GetBitsStartingFromLSB(byte b)
{
    for (int i = 0; i < 8; i++)
    {
        yield return (b % 2 != 0);
        b = (byte)(b >> 1);
    }
}
public static Int32 Bits2Int(ref byte[] source, int offset, int length)
{
    List<bool> bools = source.SelectMany(GetBitsStartingFromLSB).ToList();
    bools = bools.GetRange(offset, length);
    bools.AddRange(Enumerable.Repeat(false, 32-length).ToList() );
    int[] array = new int[1];
    (new BitArray(bools.ToArray())).CopyTo(array, 0);
    return array[0];           
}

但是这种方法太慢了，而且我必须经常调用它。

如何更有效地完成这项工作呢？

非常感谢！现在我这样做：

public static byte[] GetPartOfByteArray(  byte[] source, int offset, int length)
    {
        byte[] retBytes = new byte[length];
        Buffer.BlockCopy(source, offset, retBytes, 0, length);
        return retBytes;
    }
    public static Int32 Bits2Int(byte[] source, int offset, int length)
    {
        if (source.Length > 4)
        {
            source = GetPartOfByteArray(source, offset / 8, (source.Length - offset / 8 > 3 ? 4 : source.Length - offset / 8));
            offset -= 8 * (offset / 8);
        }
        byte[] intBytes = new byte[4];
        source.CopyTo(intBytes, 0);
        Int32 full = BitConverter.ToInt32(intBytes);
        Int32 mask = (1 << length) - 1;
        return (full >> offset) & mask;
    }

而且它非常快！

- jaanq

---

我认为这个问题更适合在codereview.stackexchange.com上提问。 - quetzalcoatl

@Fildor 在这种情况下，BitConverter 基本上没有任何用处；而且在我看来，在几乎任何其他情况下也是如此；实际上，BitConverter 上唯一真正有用的方法是 .ToString()，作为在单元测试中以十六进制方式编写的懒惰方法等，或许还有 .IsLittleEndian 用于查询 CPU 的字节序。 - Marc Gravell

@MarcGravell 很遗憾，我必须同意。 - Fildor

Answer 1

如果你想要“快速”，那么最终你需要使用位逻辑，而不是LINQ等。我不会写实际的代码，但你需要：

• 使用/ 8和% 8 将偏移量与起始字节和该字节内的位偏移量相结合
• 组合所需的字节数 - 如果您需要一个32位的数字（因为存在偏移量的可能性），则很可能需要多达5个字节；例如，以任何您期望的字节序（大端序？）组成一个长整型数值
• 对组合值使用右移操作符（>>），以丢弃您需要应用于位偏移量的多少位（即value >>= offset % 8;）
• 屏蔽掉您不需要的任何位；例如：value &= ~(-1L << length);（其中-1给出所有1；<< length在右侧创建length个零，并且~将所有零替换为一，一替换为零，因此您现在在右侧有length个1）
• 如果这个值是带符号的，您需要考虑如何处理负值，尤其是如果您不总是读取32位

- Marc Gravell

Answer 2

首先，你要求进行优化。但你所说的唯一内容是：

- 太慢了 - 需要经常调用它

没有提供以下信息：

- 多慢才算太慢？你有测量过当前代码吗？你估计需要多快？ - “经常”指多久？ - 源byte数组有多大？ - 等等。

优化可以通过多种方式进行。在寻求优化时，每个细节都很重要。例如，如果源byte[]长度只有1或2个字节（是的，可能很荒谬，但你没有告诉我们），并且很少更改，则可以通过缓存结果获得非常好的效果。等等。

因此，我没有给出解决方案，只列出了可能存在的性能问题：

private static IEnumerable<bool> GetBitsStartingFromLSB(byte b) // A
{
    for (int i = 0; i < 8; i++)
    {
        yield return (b % 2 != 0); // A
        b = (byte)(b >> 1);
    }
}
public static Int32 Bits2Int(ref byte[] source, int offset, int length)
{
    List<bool> bools = source.SelectMany(GetBitsStartingFromLSB).ToList(); //A,B
    bools = bools.GetRange(offset, length); //B
    bools.AddRange(Enumerable.Repeat(false, 32-length).ToList() ); //C
    int[] array = new int[1]; //D
    (new BitArray(bools.ToArray())).CopyTo(array, 0); //D
    return array[0]; //D
}

LINQ很有趣，但要小心谨慎才能保证速度。对于每个输入字节，它需要1个字节，将其拆分为8个bool值，并在编译器生成的IEnumerable对象中传递它们*。请注意，所有这些都需要稍后清理。可能只需返回一个new bool [8]或甚至BitArray（size = 8）即可获得更好的性能。

*) 概念上如此。实际上，yield-return是惰性的，因此它不是8valueobj + 1refobj，而只是生成项的1个可枚举对象。但是，您正在（B）中执行.ToList（），因此我以这种方式编写并不远离真相。

A2：8是硬编码的。一旦放弃那个漂亮的IEnumerable并将其更改为类似于常量大小的数组，您可以预先分配该数组并通过参数将其传递给GetBitsStartingFromLSB，以进一步减少创建和丢弃的临时对象数量。由于SelectMany逐个访问项目而永远不会回头，因此可以重复使用预分配的数组。

B: 将整个源数组转换为字节流，将其转换为列表。然后丢弃该列表的所有内容，除了该列表中一个小的偏移长度范围。为什么要转换成列表？这只是另一组浪费的对象，并且内部数据也被复制，因为bool是值类型。您可以通过 .Skip(X).Take(Y) 直接从 IEnumerable 中获取范围。

C: 填充一个包含 32 个布尔值的列表。AddRange/Repeat 很有趣，但 Repeat 必须返回一个 IEnumerable。这又是创建并丢弃的另一个对象。您正在使用 false 填充列表。放弃列表想法，将其变为 bool[32] 或 BitArray(32)。它们自动以false 开始。从 A+B 的 'range' 迭代这些位，并按索引将它们写入该数组中。已写入的将具有其值，未写入的将保持 false。工作完成，没有浪费对象。

C2：连接预分配32项数组与A+A2。GetBitsStartingFromLSB不需要返回任何内容，它可以通过参数获取要填充的缓冲区。并且该缓冲区不需要是8项缓冲区。您可以传递整个32项最终数组，并传递偏移量，以便函数知道确切的写入位置。这样可以减少对象的浪费。

D：最后，所有这些工作都是为了将所选位作为整数返回。创建了一个新的临时数组并浪费掉，实际上也创建并浪费了一个新的BitArray。请注意，在GetBitsStartingFromLSB中，您已经在进行手动位移转换int->bits，为什么不只是创建一个类似的方法，它将执行一些位移并执行bits->int转换呢？如果您知道位的顺序，那么现在您也知道它们。无需数组和BitArray，一些代码调整即可，您可以再次节省分配和数据复制。

我不知道这样做能为您节省多少时间/空间等，但这只是一些首先显眼的点，而不会太大程度地修改您原来的代码想法，也不会通过一次全部使用数学和位移等计算完成所有操作。我已经看到MarcGravell给了你一些提示。如果您有闲暇时间，建议您逐个尝试我的方法，并查看每个更改如何（以及是否！）影响性能。只是为了看看。然后，您可能会放弃所有这些并尝试使用Marc的提示重新尝试“通过一次全部使用数学和位移等计算完成所有操作”的新版本。

- quetzalcoatl