Maneira mais fácil de encontrar o balde Kademlia correto

Question

No Protocolo Kademlia Os IDs dos nó são números de 160 bits. Os nós são armazenados em baldes, o balde 0 armazena todos os nós que têm o mesmo ID que este nó, exceto pelo último bit, o Bucket 1 armazena todos os nós que têm o mesmo ID que este nó, exceto nos últimos 2 bits, e assim para todos os 160 baldes.

Qual é a maneira mais rápida de descobrir em qual balde eu devo colocar um novo nó?

Eu tenho meus baldes simplesmente armazenados em uma matriz e preciso de um método como assim:

Bucket[] buckets; //array with 160 items

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

A abordagem óbvia é trabalhar com a parte mais significativa, comparando pouco a pouco até encontrar uma diferença, espero que haja uma abordagem melhor baseada em um bit giratório.

Nota prática: meu INT160 é armazenado em uma matriz de bytes com 20 itens, soluções que funcionam bem com esse tipo de estrutura serão preferidas.

Answer 1

Você estaria disposto a considerar uma matriz de 5 números inteiros de 32 bits? (ou 3 inteiros de 64 bits)? Trabalhar com palavras inteiras pode oferecer melhor desempenho do que trabalhar com bytes, mas o método deve funcionar em qualquer caso.

Xor as palavras correspondentes dos dois IDs de nós, começando com os mais significativos. Se o resultado do XOR for zero, passe para a próxima palavra mais significativa.

Caso contrário, encontre o bit mais significativo definido neste resultado XOR usando o Método de tempo constante do deleite de Hacker.. Esse algoritmo resulta em 32 (64) se o bit mais significativo for definido e 1 se o bit menos significativo for definido e assim por diante. Esse índice, combinado com o índice da palavra atual, dirá qual bit é diferente.

Answer 2

Para iniciantes, você pode comparar byte por byte (ou palavra por palavra) e quando encontrar uma pesquisa de diferença nesse byte (ou palavra) pela primeira diferença.

Parece-me vagamente implausível que a adição de um nó a uma variedade de baldes seja tão rápido que importa se você faz uma variação inteligente para encontrar a primeira diferença dentro de um byte (ou palavra) ou apenas agitar em um loop até char_bit (ou algo assim). Possível, no entanto.

Além disso, se os IDs forem essencialmente aleatórios com distribuição uniforme, você encontrará uma diferença nos 8 primeiros bits cerca de 255/256 do tempo. Se tudo o que você se preocupa é um comportamento médio, não o pior caso, faça a coisa estúpida: é muito improvável que seu loop durar por muito tempo.

Para referência, porém, a primeira diferença entre os números x e y é o primeiro bit em x ^ y. Se você estava programando no GNU C, __builtin_clz pode ser seu amigo. Ou possivelmente __builtin_ctz, Estou meio sonolento ...

Seu código se parece com Java, então acho que o bitfoo que você está procurando é Log inteiro.