寻找正确的Kademlia桶的最简单方法

Question

在 Kademlia协议中，节点ID是160位数字。 节点存储在存储桶中，桶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个项目的字节数组中，对这种结构有效的解决方案将被优先考虑。

- Martin

Answer 1

你是否考虑过使用一个包含5个32位整数的数组？（或者3个64位整数）使用整个字来处理可能比使用字节更能提高性能，但无论如何方法都应该可行。

对应的节点ID的单词进行异或操作，从最高有效位开始。如果异或结果为零，则继续下一个最高有效单词。

否则，使用 Hacker's Delight中的常量时间方法查找在此异或结果中设置的最高有效位。如果设置了最高有效位，则此算法的结果为32（64），如果设置了最低有效位，则结果为1，以此类推。这个索引和当前单词的索引组合起来将告诉你哪个位不同。

- erickson

---

字节似乎是最自然的方式，正如你所说，整数可能会更快。 - Martin

Answer 2

首先，您可以逐字节（或逐字）进行比较，当找到差异时，在该字节（或单词）内搜索第一个差异位。

对我来说，向桶数组添加节点会如此快，以至于是否聪明地做位扭曲以在字节（或单词）中找到第一位差异或者只是在循环中运行CHAR_BIT（或其他东西）并不重要。虽然有可能。

此外，如果ID基本上是具有均匀分布的随机数，则您将发现大约255/256的时间在前8位中存在差异。如果您只关心平均情况而不是最坏情况，则只需做愚蠢的事情：很少有可能使您的循环运行很长时间。

供参考，但是数字x和y之间的第一个差异位是在x ^ y中设置的第一个位。如果您在GNU C中编程，则__builtin_clz可能是您的朋友。或者可能是__builtin_ctz，我有点困了...

你的代码看起来像是Java，所以我猜你要找的bitfoo是整数对数。

- Steve Jessop

---

C#与Java非常相似。正如您所说，这个算法的速度可能并不重要，我提出这个问题主要是出于兴趣。以前关于位操作的问题曾经揭示了一些聪明的技巧，解开它们的工作原理非常有趣。 - Martin