3

2 バイトが与えられた場合、2 バイトの先頭にある共通ビットの長さを見つけるにはどうすればよいでしょうか。

例えば：

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 つの数値が等しくなるまで、各数値の右側からビットを削除します。それらが等しくなると、それらのビットも等しくなります。

別の変数を導入することで、プレフィックスの長さを簡単に追跡できます。お任せします。

高速にしたい場合、およびバイトを扱っていることを考えると、値を事前に計算して、1 回の操作で答えを返さないのはなぜですか? 2 バイトのすべての可能な組み合わせに対してこのアルゴリズムを実行し、結果をテーブルに格納します。

可能性しかありません2^8 * 2^8 = 2^16(2^15実際には、x = 6andはandy = 9と同じです)。初期時間とメモリに余裕がある場合は、事前計算が最終的に最速になるはずです。x = 9y = 6

編集：

少なくとも事前計算には優れており、おそらく一般的には高速なソリューションが得られました: の左端の 1 ビットを見つけます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
};

そして、2 バイトの XOR を使用します。

bytePrefix[9 ^ 6]

これは可能な限り高速だと思います.1回のXOR操作と配列ルックアップだけです.(2回の配列ルックアップに変更することもできます.

于 2010-07-22T22:24:46.193 に答える
3

まず、xor演算子を使用して、バイト間の2進差を取得します。次に、差がゼロになるまでビットを右にシフトします。

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 に答える
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 に答える
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;
 }

これは、64 ビットの長さで共通のプレフィックスを見つけるのに 6 回の反復しか必要としません。バイト バージョンでは 3 回の反復しか必要ありません。ループを展開して、さらに高速化します。

于 2010-07-22T22:30:02.260 に答える
1

これは、テーブルまたはループのないものです。

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

説明：

log 2 Xは、値Xを取得するために数値2を累乗する必要がある累乗です。2進数の各ビットは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を差し引くと、先行ゼロの数=共通ビットの数になります。：log2（0）が-Infinityの場合は特殊なケースがありa XOR b == 0、これは機能しませんが、すべてのビットが一致する必要があることがわかっているため、答えは8です。

于 2010-07-22T23:55:50.700 に答える
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 に答える
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)
{
  unsigned char の不一致。
  不一致 = a^b;
  if (不一致 & 0xF0)
    テーブルを返します[不一致 >> 4];
  そうしないと
    テーブルを返す[ミスマッチ]+4;
}

分岐を含むより多くの命令がありますが、テーブルが 16 バイトしかないため、1 つまたは 2 つのキャッシュ ミスで完全に満たされます。別の方法として、16 バイトのテーブルと 5 バイトのテーブルで合計 3 回のルックアップを使用しますが、分岐は使用しません。

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

unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  符号なし文字の不一致、temp2;
  不一致 = a^b;
  temp2 = テーブル [ミスマッチ >> 4];
  return temp2 + (table2[temp2] & table[ミスマッチ & 15]);
}

実際のアプリケーションでプロファイリングを行って、小さいテーブルのキャッシュ負荷の削減が余分な命令を相殺するのに十分かどうかを確認する必要があります。

于 2010-07-23T15:03:16.280 に答える