在 C# 中计算汉明距离的最快方法

我有一个很大的 BigInteger 集合（n = 20,000,000），代表位数组长度为 225。给定一个 BigInteger，我想在我的集合中找到低于特定汉明距离的 x BigInteger。

目前，我将所有 BigInteger 转换为字节数组：

bHashes = new byte[hashes.Length][];
for (int i = 0; i < hashes.Length; i++)
{
    bHashes[i] = hashes[i].ToByteArray();
}

然后我创建一个汉明距离查找数组：

int[][] lookup = new int[256][];

for (int i = 0; i < 256; i++) {
    lookup[i] = new int[256];
    for (int j = 0; j < 256; j++)
    {
        lookup[i][j] = HammingDistance(i, j);
    }
}

static int HammingDistance(BigInteger a, BigInteger b)
{
    BigInteger n = a ^ b;

    int x = 0;
    while (n != 0)
    {
        n &= (n - 1);
        x++;
    }
    return x;
}

最后，我通过计算字节之间的汉明距离之和来计算总汉明距离。我的时间测量表明“手动”添加距离比使用循环更快：

static List<int> GetMatches(byte[] a)
{
    List<int> result = new List<int>();
    for (int i = 0; i < bHashes.Length; i++)
    {
        byte[] b = bHashes[i];
        int dist = lookup[a[0]][b[0]] +
                   lookup[a[1]][b[1]] +
                   lookup[a[2]][b[2]] +
                   lookup[a[3]][b[3]] +
                   lookup[a[4]][b[4]] +
                   lookup[a[5]][b[5]] +
                   lookup[a[6]][b[6]] +
                   lookup[a[7]][b[7]] +
                   lookup[a[8]][b[8]] +
                   lookup[a[9]][b[9]] +
                   lookup[a[10]][b[10]] +
                   lookup[a[11]][b[11]] +
                   lookup[a[12]][b[12]] +
                   lookup[a[13]][b[13]] +
                   lookup[a[14]][b[14]];
        if (dist < THRESHOLD) result.Add(i);
    }
    return result;
}

预处理时间无关紧要，只有 GetMatches() 函数的执行时间很重要。使用上述方法，我的系统需要大约 1,2 秒，不幸的是，这远远满足了我的需求。有更快的方法吗？