Sean Anderson publicou pequenos truques de contenção contendo o algoritmo de Eric Cole para encontrar o de um número inteiro de bits nas operações com multiplicação e pesquisa.N v O ( lg ( N ) )
O algoritmo baseia-se em um número "mágico" da sequência De Bruijn. Alguém pode explicar propriedades matemáticas fundamentais da sequência usada aqui?
uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
nt.number-theory
comp-number-theory
Yury Bayda
fonte
fonte
Respostas:
Primeiro, observe que esse algoritmo calcula apenas e, conforme o código é escrito, funciona apenas para que se encaixa em uma palavra de bits.v 32⌈log2v⌉ v 32
A sequência de turnos e -s que aparece primeiro tem a função de propagar o 1 bit principal de até o bit menos significativo. Numericamente, isso fornece .2 ⌈ log 2 v ⌉ - 1v 2⌈log2v⌉−1
A parte interessante é o truque de Bruijn, que vem deste artigo de Leiserson, Prokop e Randall (aparentemente os professores do MIT passam algum tempo fazendo pequenos hacks :)). O que você precisa saber sobre as sequências de De Bruijn é que elas representam todas as sequências possíveis de um determinado comprimento de uma maneira o mais compactada possível. Precisamente, uma sequência de Brujn sobre o alfabeto é uma cadeia binária de comprimento modo que cada cadeia binária de comprimento apareça exatamente uma vez como uma substring contígua (é permitido o agrupamento). A razão pela qual isso é útil é que, se você tiver um número cuja representação de bits seja uma sequência de Bruijn (preenchida coms 2 k k X k k 2 i X i i < k{0,1} s 2k k X k zeros), então os bits superiores de identificam exclusivamente (contanto que ).k 2iX i i<k
fonte
Alguns comentários (não é realmente uma resposta). Vamos classificar números inteiros de 32 bits seguinte maneira:c
Tipo X: (como uma sequência binária) é a sequência De Bruijn (para todas as rotações, os bits [27,31] são distintos). Um exemplo:c
Tipo Y: os bits [27,31] de são distintos para . É isso que Leiserson et al. usos. Exemplos:i = 0 , 1 , . . . , 312i⋅c i=0,1,...,31
Tipo Z: os bits [27,31] de são distintos para . É disso que precisamos na pergunta original. Exemplos:i = 0 , 1 , . . . , 31(2i+1−1)⋅c i=0,1,...,31
Algumas observações baseadas em experimentos rápidos (espero ter acertado):
Existem 65536 inteiros do tipo X.
Existem 4096 números inteiros do tipo X + Y. Esses são precisamente aqueles números inteiros do tipo X que começam com a sequência '0000 ...'
Existem 256 números inteiros do tipo X + Y + Z. Esses são precisamente aqueles números inteiros do tipo X que começam com a sequência '0000011111 ...'
Todos os números inteiros do tipo Y também são do tipo X.
No entanto, também existem 768 números inteiros do tipo Z que não são do tipo X nem do tipo Y. Eles começam com '1000011111 ...', '0111100000 ...' ou '1111100000 ...'
fonte
Essa constante particular é uma sequência de De Bruijn com alfabeto binário, mas com uma propriedade extra. Vou chamá-lo de 'Propriedade de Marc Dickinson', já que o algoritmo original pode ser implementado sem essas sequências especiais de banco de dados. Ao adicionar duas operações extras, poderíamos usar qualquer sequência de banco de dados comum. Operação: v ^ = (v >> 1); // clr todos os bits, exceto o MSB definido após a cascata ou mudança.
Se você estava esperando uma fórmula matemática elegante para descrevê-los ou um teorema para produzi-los ou algo semelhante, acho que isso exigiria uma compreensão profunda da teoria dos números e possivelmente de outros campos que estão além do meu conjunto de habilidades. Se eu quiser adivinhar, eu apostaria que eles poderiam ser produzidos por autômatos celulares. Esta não é uma resposta porque? em uma base rigorosa, mas uma tentativa de entender intuitivamente por que funciona e por que funciona corretamente, para que você possa usá-lo com confiança.
fonte