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

编辑:多亏了这些评论,我发现我误解了这个问题。(以下为固定版本)。

使用查阅表格:

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倍以上的内存,可能会更慢,按位计算,它真的很快)。

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 )如果你能负担起最初的时间和记忆,那么预计算最终应该是最快的。

编辑:

您得到的解决方案至少对预计算更好,一般来说可能更快:在 x ^ y . 使用这个,构建一个表 Pre 在哪里? Pre[i] = position of leftmost 1 bit in i . 此表只需要2^8字节。

首先使用xor运算符获取字节之间的二进制差异。然后将位右移,直到差为零:

byte b1 = 6;
byte b2 = 9;

int length = 8;
for (int diff = b1 ^ b2; diff != 0; length--) diff >>= 1;

这将在循环中为您提供最少的计算,因此它将相当快。

通过已知的快速解决方案,可以将其重述为一个更简单的问题:

• 找到最左边的真位 X ^ Y .

一些代码(显然代码不能立即跟随项目符号列表???)

 int findCommonPrefix(long x, long y, out long common)
 {
    int prefixPlace = 0;
    int testPlace = 32;
    long w, mismatch = x ^ y;
    do {
       w = mismatch >> testPlace;
       if (w != 0) { prefixPlace |= testPlace; mismatch = w; }
       testPlace >>= 1;
    } while (testPlace != 0);
    common = x >> prefixPlace;
    return 64 - prefixPlace;
 }

这只需要6次迭代就可以找到64位长的公共前缀,字节版本只需要3次迭代。展开循环以获得更高的速度。

如果您所处的环境空间有限(显然,如果您使用的是C,但一般情况下不是这样),并且无法提供查阅表格:

byte test = byte1 ^ byte2;
int length = 0;
if ((test & 0x80) == 0)
{
    if ((test & 0x40) == 0)
    {
        if ((test & 0x20) == 0)
        {
            if ((test & 0x10) == 0)
            {
                // I think you get the idea by now.
                // Repeat for the lower nibble.
            }
            else
                length = 3;
        }
        else
            length = 2;
    }
    else
        length = 1;
}

这基本上是一个未分解的循环,用于查找xor'd数中的第一个1位。我认为没有查阅表格,它不会比这个更快。

使用exclusive or(xor)的另一种方法:

public int GetCommonPrefixLength(byte a, byte b)
{
    int c = a ^ b;
    int len = -1;
    while ((++len < 8) && ((c & 0x80) == 0))
        c = c << 1;
    return len;
}

这是一个程序化的方法:

int r = 8;
while (a != b)
{
    a >>= 1;
    b >>= 1;
    r -= 1;
}

下面是一种使用只有256个条目的查阅表格的方法:

int[] lookupTable;

void createLookupTable()
{
    lookupTable = new int[256];
    for (int a = 0; a <= 255; ++a)
    {
        int n = 8;
        byte b = (byte)a;
        while (b > 0) {
            b >>= 1;
            n -= 1;
        }
        lookupTable[a] = n;
    }
}

int commonPrefix(byte a, byte b)
{
    return lookupTable[a ^ b];
}

为了好玩,这里有一种方法可以和Linq一起完成:

int r = 8 - Enumerable.Range(0, 9).Where(n => a >> n == b >> n).First();

这里有一个没有表或循环的:

len =  (a^b) ? (7 - (int)Math.Log( a^b, 2)) : 8;

说明:

日志 _二 x是数字2必须提升到的幂,才能获得值x。由于二进制数字中的每个位代表2的下一个幂,因此可以使用此事实来查找最高的位集(从0开始计数):

2**0   = 1 = 0b0001;  log2(1) = 0
2**1   = 2 = 0b0010;  log2(2) = 1
2**1.6 =~3 = 0b0011;  log2(3) =~1.6; (int)log2(3) = 1
2**2   = 4 = 0b0100;  log2(4) = 2
...
2**3   = 8 = 0b1000;  log2(8) = 3

所以代码是通过 a XOR b ,只设置不同的位。如果结果为非零,则使用log2查找最高的位集。7减去结果得出前导零的数目=公共位的数目。有个特殊情况 a XOR b == 0 :log2(0)是-无穷大的,所以不起作用,但我们知道所有的位都必须匹配,所以答案是8。

int i;
for (i=0;i<sizeof(byte);i++)
    if (a >> sizeof(byte)-i != b >> sizeof(byte)-i) break;

256字节的表版本似乎相当不错;根据缓存和分支问题,16字节的表版本可能运行得更快,也可能不会运行得更快。类似:

/* Assumes table[16] is defined similarly to the table[256] in earlier examples */
unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  unsigned char mismatch;
  mismatch = a^b;
  if (mismatch & 0xF0)
    return table[mismatch >> 4];
  else
    return table[mismatch]+4;
}

更多的指令,包括一个分支,但是由于表现在只有16个字节,所以只需要一个或两个缓存未命中就可以完全填充。另一种方法,在一个16字节的表和一个5字节的表上使用总共三个查找,但不进行分支:

unsigned char table2[5] = {0,0,0,0,0xFF};

unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  unsigned char mismatch,temp2;
  mismatch = a^b;
  temp2 = table[mismatch >> 4];
  return temp2 + (table2[temp2] & table[mismatch & 15]);
}

我们必须在实际应用程序中进行一些分析,以查看减少的较小表的缓存负载是否足以抵消额外的指令。