The easiest way to find the right kademlia bucket

Question

In the Kademlia node protocol, Identifiers are 160-bit numbers. Nodes are stored in buckets, bucket 0 stores all nodes that have the same identifier as this node, with the exception of the very last bit, bucket 1 stores all nodes that have the same identifier as this node, except for the last 2 bit etc. for all 160 buckets.

What is the fastest way to find in which bucket should I put the new node in?

I have my buckets that are just stored in an array, and I need a method like this:

Bucket[] buckets; //array with 160 items

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

The obvious approach is to work with the most significant bit, comparing in parts, until I find the difference, I hope there is a better approach based on smart cue-bits.

Practical Note: My Int160 is stored in an array of bytes with 20 elements, preferred solutions that work well with such a structure.

Answer 1

Would you like to consider an array of 5 32-bit integers? (or 3 64-bit integers)? Working with whole words can give you better performance than working with bytes, but the method should work anyway.

XOR corresponding words of two node identifiers, starting with the most significant. If the result of XOR is zero, go to the next most significant word.

, XOR Hacker Delight.. 32 (64), , 1, , . , .

Answer 2

( ), ( ) .

, node , , -twiddling, ( ) CHAR_BIT ( - ). , .

, , 8 255/256 . , , , , : , .

, , x y - , x ^ y. GNU C, __builtin_clz . , , __builtin_ctz, ...

Java, , , , , .