正しいカデムリアバケットを見つける最も簡単な方法

Question

の中に Kademliaプロトコル ノードIDは160ビット番号です。ノードはバケットに保存され、バケット0はこのノードと同じIDを持つすべてのノードを最後のビットを除いて保存します。バケット1は、最後の2ビットを除いてこのノードと同じIDを持つすべてのノードをすべて保存します。すべての160バケツの場合。

新しいノードを入れるべきバケツを見つけるための最速の方法は何ですか？

バケツは単に配列に保存されているだけで、次のような方法が必要です。

Bucket[] buckets; //array with 160 items

public Bucket GetBucket(Int160 myId, Int160 otherId)
{
    //some stuff goes here
}

明らかなアプローチは、違いを見つけるまで少しずつ比較して、最も重要なビットから作業することです。私は、賢いビットのツイドリングに基づいたより良いアプローチがあることを望んでいます。

実用的な注：私のINT160は、20個のアイテムを備えたバイト配列に保存されており、そのような構造でうまく機能するソリューションが推奨されます。

Answer 1

5 32ビットの整数の配列を喜んで検討しますか？ （または3 64ビット整数）？単語全体を使用すると、バイトを使用するよりも優れたパフォーマンスが得られる場合がありますが、いずれの場合でもこの方法は機能するはずです。

XOR最も重要なものから始まる2つのノードIDの対応する単語。 XORの結果がゼロの場合は、次の最も重要な単語に進みます。

それ以外の場合は、次のXOR結果に設定されている最も重要なビットを見つけます ハッカーの喜びからの一定の時間方法。. 。このアルゴリズムの結果、最も重要なビットが設定されている場合は32（64）、1が最小のビットが設定されている場合などです。現在の単語のインデックスと組み合わせるこのインデックスは、どのビットが違うかを教えてくれます。

Answer 2

まず第一に、バイトごと（または単語ごと）を比較することができ、そのバイト（または単語）内で最初の違いの違いの検索を見つけると、違いの最初のビットを見つけることができます。

バケツの配列にノードを追加することは非常に速いので、バイト（または単語）内で最初の違いを見つけるために巧妙なビットをするのか、それともループで解約するのかが重要であると私には漠然と信じがたいように思えます。 char_bit（または何か）まで。しかし、可能です。

また、IDが均一な分布で本質的にランダムである場合、最初の8ビットに約255/256に違いが見つかります。最悪のケースではなく、平均ケースの動作だけである場合、愚かなことをするだけです。ループが長く実行される可能性は非常に低いです。

ただし、参照のために、数字間の最初の違いのビット x と y 最初のビットが設定されています x ^ y. 。 GNU Cでプログラミングしていた場合、 __builtin_clz あなたの友達かもしれません。またはおそらく __builtin_ctz, 、私はちょっと眠いです...

あなたのコードはJavaのように見えますが、あなたが探しているBitfooは 整数ログ.