0
\$\begingroup\$

Kademlia is a DHT (distributed hash table) which uses a specific type of routing table, dependent on the Hamming distance between the "addresses" of two peers on the network. I'm attempting to implement a modified version of it in Java. To find which "bucket" in the routing table a peer should go into, I xor the peer's address with my client's address and try to find the index of the first true bit in the result. So far I've been using this code:

    private int findBucket(byte[] address) {
        byte[] xorresult = xor(nodeAddress, address);

        for (int i = 0; i < 20; i++) {
            int temp = toBinaryString(xorresult[i]).indexOf('1');

            if (temp != -1) {
                return (i * 8) + temp;
            }
        }

        return -1;
    }

    private static String toBinaryString(byte n) {
        StringBuilder sb = new StringBuilder("00000000");
        for (int bit = 0; bit < 8; bit++) {
            if (((n >> bit) & 1) > 0) {
                sb.setCharAt(7 - bit, '1');
            }
        }
        return sb.toString();
    }
\$\endgroup\$
  • \$\begingroup\$ Why not use the java.util.BitSet? It has build in xor(), nextSetBit() and conversion from/to byte[]. \$\endgroup\$ – user158037 Aug 22 '18 at 12:53
  • \$\begingroup\$ @user158037 I have no control over the inputs, they have to be byte arrays. I had a previous version of this code that converted the arrays to bitsets, but not only was that version (much) slower, the bitsets had a tendency to not keep the imposed 160 bit size. \$\endgroup\$ – Lev Knoblock Aug 22 '18 at 13:02
1
\$\begingroup\$

Java has some useful functions to search for set bits in the Integer class, including numberOfLeadingZeros. Of course, being in the Integer class (and there is no equivalent in the Byte class), it counts the leading zeros of an int instead of a byte, so it returns 24 too much. That's easy to work around by subtracting 24 though, and using this function means we can get rid of the function that converts a byte to a string.

I would also avoid allocating a temporary array just to hold the XORed addresses, it just doesn't seem to add much to the code, and I would also make it more explicit that 20 is indeed the size of the array and not some arbitrary number.

So you can write it like this:

private int findBucket(byte[] address) {
    for (int i = 0; i < address.length; i++) {
        int temp = (address[i] ^ nodeAddress[i]) & 0xFF;

        if (temp != 0) {
            return i * 8 + Integer.numberOfLeadingZeros(temp) - 24;
        }
    }

    return -1;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.