c# - 最快的方法从部分位中获取整数

Question

我有byte[] byteArray，通常是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;
    }

而且运行速度非常快！

Answer 1

如果您追求“快速”，那么最终您需要使用位逻辑而不是 LINQ 等来完成此操作。我不打算编写实际代码，但您需要：

使用 / 8 和 % 8 的偏移量找到起始字节和该字节 bit-offset 中的
编写你需要的字节数——如果你在一个 32 位数字之后，很可能最多 5 个字节（因为可能存在偏移量） ;例如进入一个long，无论你期望
在组合值上使用 right-shift (>>) 以删除 however-many 位，您需要应用 bit-offset（即 value >>= offset % 8;）
屏蔽掉任何你不想要的部分；例如 value &= ~(-1L << length);（-1 给你 all-ones；<< length 在右手边创建 length 个零，~ 交换所有零代表一，一代表零，所以你现在在右手边有 length 个）
如果值是有符号的，您需要考虑如何处理负值，尤其是当您并不总是读取 32 位时

Answer 2

首先，您要求优化。但你所说的唯一事情是：

太慢了
需要经常调用

没有以下信息：

慢多少算太慢？你测量过当前代码吗？你估计过你需要多快吗？
“经常”是多久一次？
源字节数组有多大？
等等

可以通过多种方式进行优化。当要求优化时，一切都很重要。例如，如果源 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
}

A：LINQ 很有趣，但除非仔细操作，否则速度不快。对于每个输入字节，它需要 1 个字节，将其拆分为 8 个布尔值，将它们包裹在 compiler-generated IEnumerable 对象 *) 中传递。请注意，这一切也需要稍后清理。可能您只需 returning new bool[8] 甚至 BitArray(size=8).

即可获得更好的性能

*) 在概念上。事实上 yield-return 是惰性的，所以它不是 8valueobj+1refobj，而只是 1 个可枚举生成项。但是，你在 (B) 中执行 .ToList()，所以我以这种方式写这篇文章与事实相去不远。

A2：8 是硬编码的。一旦删除漂亮的 IEnumerable 并将其更改为 constant-sized array-like 事物，就可以预分配该数组并通过参数将其传递给 GetBitsStartingFromLSB 以进一步减少创建并随后丢弃的临时对象的数量。由于 SelectMany 访问项目 one-by-one 而不会返回，因此可以重用该预分配数组。

B：将整个Source数组转换为字节流，再转换为List。然后丢弃整个列表，除了该列表的一小部分 offset-length 。为什么要隐蔽列出？这只是浪费的另一包对象，内部数据也被复制，因为 bool 是一个值类型。您可以通过 .Skip(X).Take(Y)

直接从 IEnumerable 获取范围

C：填充布尔值列表以包含 32 个项目。 AddRange/Repeat 很有趣，但 Repeat 必须 return 一个 IEnumerable。它又是另一个创建并丢弃的对象。您正在用 false 填充列表。删除列表想法，将其设为 bool[32]。或 BitArray(32)。它们自动以 false 开头。这是 bool 的默认值。遍历 'range' A+B 中的那些位，并按索引将它们写入该数组。写出来的就有价值，没写出来的就一直是假的。工作完成，没有浪费任何物品。

C2：连接预分配32项数组与A+A2。 GetBitsStartingFromLSB 不需要 return 任何东西，它可能会通过参数获取要填充的缓冲区。而且该缓冲区不需要是 8 项缓冲区。您可以传递整个 32 项最终数组，并传递一个偏移量，以便函数确切知道要写入的位置。浪费的物品更少。

D：最后，所有 return 选择的位作为整数。新的临时数组被创建和浪费，新的 BitArray 也被有效地创建和浪费。请注意，之前您已经在 GetBitsStartingFromLSB 中进行了手动 bit-shift 转换 int->bits，为什么不创建一个类似的方法来执行一些移位并执行 bits->int 呢？如果您知道位的顺序，那么现在您也知道它们了。不需要 array&BitArray，一些代码摆动，你又节省了分配和数据复制。

我不知道这会为您节省多少time/space/etc，但这只是乍一看很突出的几点，没有过多修改您对代码的原始想法，没有doing-it-all 通过 math&bitshifts 等。我看到 MarcGravell 也已经给你写了一些提示。如果您有空闲时间，我建议您先尝试我的，一个接一个，看看每个更改如何（如果有的话！）影响性能。只是去看看。然后你可能会放弃它并再次尝试新的“do-it-all via math&bitshifts in one go”版本和 Marc 的提示。

c# - 最快的方法从部分位中获取整数

c# - fastest method get integer from part of bits

c#

arrays

performance

bit