3

给定两个字节，我如何找到两个字节开头的公共位的长度。

例如：

9 == 00001001
6 == 00000110

Common prefix is 0000, length 4

我在 C# 中工作，所以请只使用 C# 操作。

附录：这段特定的代码将运行数千次，并且需要非常快。

4

10 回答 10

6 
byte x = 9;
byte y = 6;

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

基本上，从每个数字的右侧删除一点，直到两者相等。当它们相等时，它们的位也相等。

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

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

您只有2^8 * 2^8 = 2^16可能性（2^15实际上，因为x = 6and 与 and相同y = 9）。如果你能负担得起初始时间和内存，预计算最终应该是最快的。x = 9y = 6

编辑：

你得到的解决方案至少对预计算更好，而且通常可能更快：在x ^ y. 使用它，建立一个表Pre，其中Pre[i] = position of leftmost 1 bit in i. 此表只需要 2^8 个字节。

于 2010-07-22T22:18:22.960 回答
5

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

使用查找表：

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 倍的内存并且可能会更慢，按位计算真的很快）。

于 2010-07-22T22:24:46.193 回答
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 数字中的第一个 1 位。如果没有查找表，我认为它不会比这更快。

于 2010-07-22T22:17:11.313 回答
3

首先使用 xor 运算符获取字节之间的二进制差异。然后你只需将位向右移动，直到差为零：

byte b1 = 6;
byte b2 = 9;

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

这将使您在循环中进行最少的计算，因此速度会相当快。

于 2010-07-22T22:39:34.757 回答
2

这可以用已知的快速解决方案重新表述为一个更简单的问题：

  • 在 中找到最左边的真位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 次迭代。展开循环以获得更快的速度。

于 2010-07-22T22:30:02.260 回答
1

这是一种程序方式：

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();
于 2010-07-22T22:18:53.010 回答
1

另一种使用异或（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;
}
于 2010-07-22T22:34:07.837 回答
1

这是一个没有表格或循环的：

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

解释：

log 2 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

所以代码通过 take 工作a XOR b，它只设置不同的位。如果结果非零，我们使用 log2 来查找最高位集。7减去结果给出了前导零的数量=公共位的数量。有一个特殊情况a XOR b == 0：log2(0) 是-Infinity，所以这不起作用，但我们知道所有位都必须匹配，所以答案是 8。

于 2010-07-22T23:55:50.700 回答
0 
int i;
for (i=0;i<sizeof(byte);i++)
    if (a >> sizeof(byte)-i != b >> sizeof(byte)-i) break;
于 2010-07-22T22:17:28.267 回答
0

256 字节的表格版本看起来相当不错；根据缓存和分支问题，一个 16 字节的表版本可能会或可能不会运行得更快。就像是：

/* 假设 table[16] 的定义类似于前面示例中的 table[256] */
unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  无符号字符不匹配；
  不匹配 = a^b;
  如果（不匹配 & 0xF0）
    返回表[不匹配>> 4]；
  别的
    返回表[不匹配]​​+4；
}

更多指令，包括一个分支，但由于该表现在只有 16 个字节，因此只需一到两次缓存未命中即可完全填充。另一种方法，在 16 字节表和 5 字节表上总共使用三个查找，但没有分支：

无符号字符表2 [5] = {0,0,0,0,0xFF}；

unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  无符号字符不匹配，temp2；
  不匹配 = a^b;
  temp2 = 表[不匹配 >> 4];
  返回 temp2 + (table2[temp2] & table[mismatch & 15]);
}

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

于 2010-07-23T15:03:16.280 回答