计算字节数组中位总和的最快方法

Question

我有两个长度相同的字节数组.我需要在每个字节之间执行XOR运算,然后计算位数之和.

例如:

11110000^01010101 = 10100101 -> so 1+1+1+1 = 4

我需要对字节数组中的每个元素执行相同的操作.

Answer 1

使用查找表.XORing后只有256个可能的值,所以它不会花费很长时间.与izb的解决方案不同,我不建议手动输入所有值 - 使用其中一个循环答案在启动时计算一次查找表.

例如:

public static class ByteArrayHelpers
{
    private static readonly int[] LookupTable =
        Enumerable.Range(0, 256).Select(CountBits).ToArray();

    private static int CountBits(int value)
    {
        int count = 0;
        for (int i=0; i < 8; i++)
        {
           count += (value >> i) & 1;
        }
        return count;
    }

    public static int CountBitsAfterXor(byte[] array)
    {
        int xor = 0;
        foreach (byte b in array)
        {
            xor ^= b;
        }
        return LookupTable[xor];
    }
}

(如果你真的想要,你可以把它变成一种扩展方法......)

注意byte[]在CountBitsAfterXor方法中的使用- 你可以使它IEnumerable<byte>更具普遍性,但迭代一个数组(在编译时已知是一个数组)会更快.可能只是在显微镜下更快,但嘿,你要求最快的方式:)

我几乎可以肯定,实际上它表示为

public static int CountBitsAfterXor(IEnumerable<byte> data)

在现实生活中,但看哪哪个更适合你.

还要注意xor变量的类型int.事实上,没有为byte值定义XOR运算符,如果你创建xor了byte它,由于复合赋值运算符的性质,它仍然会编译,但它会在每次迭代时执行强制转换 - 至少在IL中.很有可能JIT会照顾这个,但是没有必要甚至要求它:)

Answer 2

最快的方式可能是一个256元素的查找表......

int[] lut
{
    /*0x00*/ 0,
    /*0x01*/ 1,
    /*0x02*/ 1,
    /*0x03*/ 2
    ...
    /*0xFE*/ 7,
    /*0xFF*/ 8
}

例如

11110000^01010101 = 10100101 -> lut[165] == 4

Answer 3

这通常被称为比特计数.实际上有几十种不同的算法.这是一个列出一些更为人熟知的方法的站点.甚至还有CPU特定的指令来执行此操作.

从理论上讲,Microsoft可以添加一个BitArray.CountSetBits函数,使用该CPU架构的最佳算法进行JITed.举个例子,我会欢迎这样的补充.