最简单的方法来找到正确的kademlia桶

Question

在 Kademlia协议 节点Id160位数字。节点是存在桶中，桶0存储的所有节点具有相同的ID作为这个节点除了最后一位桶1中储存的所有节点具有相同的ID作为这个节点除了最后的2位，并因此在所有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位整数)?工作与整个词语可以给你更好的性能比字节，但该方法应该在任何情况下。

异或相应的单词的两个节点Id,先从最为显着。如果异或结果为零，移动到下一个最重要的词。

否则，找到最显着的位置，在这个异或结果的使用 恒定时间的方法从黑客的喜悦。.这个算法的结果在32(64)如果最重要的位置和1如果最不重要的位置，等等。这个指数，结合当前的索引词，将会告诉你哪位是不同的。

Answer 2

对于初学者来说，你可以比较逐字节（或字的字），当你找到差异的第一位是字节中的不同搜索（或词）。

这似乎依稀令人难以置信，我认为将节点添加到水桶的数组将是如此之快，它很重要，当你做聪明位变换找到差异的一个字节中的第一位（或字），或只是流失在一个循环中达到CHAR_BIT（或东西）。可能的，虽然。

此外，如果ID是均匀分布基本上是随机的，那么你会发现在大约的时间255/256的前8位的差。如果所有你关心的是一般情况下的行为，而不是最坏的情况，那么就做愚蠢的事情。这是不太可能，你的循环将长期运行

有关参考，虽然，数字x和y之间差的第一位是在x ^ y第一比特集。如果你在GNU C语言进行编程，__builtin_clz可能是你的朋友。或可能__builtin_ctz，我有点困了......

您的代码看起来像Java，虽然如此，我猜你正在寻找的bitfoo是的整数日志。