Sean Anderson publicó trucos de bit twiddling que contienen el algoritmo de Eric Cole para encontrar el de un entero de N bits v en operaciones O ( lg ( N ) ) con multiplicación y búsqueda.
El algoritmo se basa en un número "mágico" de la secuencia De Bruijn. ¿Alguien puede explicar las propiedades matemáticas fundamentales de la secuencia utilizada aquí?
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
fuente
fuente
Respuestas:
fuente
Algunas observaciones basadas en experimentos rápidos (espero haberlo hecho bien):
Hay 65536 enteros de tipo X.
Hay 4096 enteros de tipo X + Y. Estos son precisamente esos enteros de tipo X que comienzan con la secuencia '0000 ...'
Hay 256 enteros de tipo X + Y + Z. Estos son precisamente esos enteros de tipo X que comienzan con la secuencia '0000011111 ...'
Todos los enteros de tipo Y también son de tipo X.
Sin embargo, también hay 768 enteros de tipo Z que no son del tipo X ni del tipo Y. Estos comienzan con '1000011111 ...', '0111100000 ...' o '1111100000 ...'
fuente
Esta constante particular es una secuencia de De Bruijn con alfabeto binario pero con una propiedad adicional. Lo llamaré la 'Propiedad de Marc Dickinson' ya que el algoritmo original podría implementarse sin estas secuencias especiales de DB. Al agregar 2 operaciones adicionales, podríamos usar cualquier secuencia DB común. Operación: v ^ = (v >> 1); // clr todos los bits excepto MSB establecido después del cambio en cascada o-shift.
Si esperaba una fórmula matemática elegante para describirlos o un teorema para producirlos o algo similar, creo que esto requeriría una comprensión profunda de la teoría de números y posiblemente otros campos que están más allá de mi conjunto de habilidades. Si tuviera que adivinar, apostaría a que podrían ser producidos por autómatas celulares. Esta no es una respuesta, ¿por qué? sobre una base rigurosa pero un intento de comprender intuitivamente por qué funciona y por qué funciona correctamente, para que pueda usarlo con confianza.
fuente