以两个字节查找公共前缀的长度

Question

给定两个字节,如何在两个字节的开头找到公共位的长度.

例如:

9 == 00001001
6 == 00000110

Common prefix is 0000, length 4

我在C#工作,所以请坚持使用C#操作.

附录:这段特殊的代码将运行数千次,并且需要非常快.

Answer 1

byte x = 9;
byte y = 6;

while ( x != y )
{
    x >>= 1;
    y >>= 1;
}

基本上,从每个数字的右边删除一个位,直到两个相等.当它们变得相等时,它们的位也是相等的.

您可以通过引入另一个变量轻松跟踪前缀的长度.我会留给你的.

如果您希望它快速,并且考虑到您正在处理字节,为什么不预先计算值并在单个操作中返回答案？对两个字节的所有可能组合运行此算法,并将结果存储在表中.

你只需要2^8 * 2^8 = 2^16准备(2^15实际上,因为x = 6和y = 9是一样的x = 9和y = 6).如果你能负担起初始时间和内存,那么预计算最终应该是最快的.

编辑:

你得到的解决方案至少更适合预计算,一般来说可能更快:找到最左边的1位x ^ y.使用它,Pre在其中构建一个表Pre[i] = position of leftmost 1 bit in i.此表只需要2 ^ 8个字节.

Answer 2

编辑：感谢评论，我发现我误解了这个问题。（以下是固定版本）。

使用查找表：

readonly static int[] bytePrefix = new int[] {
    8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

并使用它对两个字节进行异或：

bytePrefix[9 ^ 6]

我相信这是尽可能快的，它只是一个 XOR 操作和一个数组查找（您也可以将其更改为 2 个数组查找，但它会使用 256 倍的内存并且可能更慢，按位计算它真的很快）。