Hay muchas preguntas sobre esto en StackOverflow. mucho Sin embargo, no puedo encontrar una respuesta que:
Más rápido que:
private static int Obvious(ulong v) { int r = 0; while ((v >>= 1) != 0) { r++; } return r; }O incluso
int r = (int)(Math.Log(v,2));Estoy asumiendo una CPU Intel de 64 bits aquí.
Una referencia útil es la página de Bit Hacks y otra es fxtbook.pdf Sin embargo, si bien estos brindan una dirección útil para abordar el problema, no brindan una respuesta inmediata.
Busco una función reutilizable que pueda hacer algo similar a _BitScanForward64 y _BitScanReverse64 solo para C#.
.NET Core 3.0 agregó BitOperations.LeadingZeroCount y BitOperations.TrailingZeroCount para que pueda usarlos directamente. Se asignarán a las instrucciones LZCNT/BSR y TZCNT/BSF del x86, por lo que son extremadamente eficientes.
int mostSignificantPosition = 63 - BitOperations.LeadingZeroCount(0x1234L); int leastSignificantPosition = BitOperations.TrailingZeroCount(0x1234L);Alternativamente, la posición del bit más significativo se puede calcular así
int mostSignificantPosition = BitOperations.Log2(x - 1) + 1Una de las formas de hacer esto, que se describe en la página de Bit Hacks vinculada en la pregunta, es aprovechar la secuencia de De Bruijn . Lamentablemente esta página no ofrece una versión de 64 bits de dicha secuencia. Esta útil página explica cómo se pueden construir las secuencias de De Bruijn, y esta da un ejemplo del generador de secuencias escrito en C++. Si adaptamos el código dado, podemos generar varias secuencias, una de las cuales se proporciona en el código C# a continuación:
public static class BitScanner { private const ulong Magic = 0x37E84A99DAE458F; private static readonly int[] MagicTable = { 0, 1, 17, 2, 18, 50, 3, 57, 47, 19, 22, 51, 29, 4, 33, 58, 15, 48, 20, 27, 25, 23, 52, 41, 54, 30, 38, 5, 43, 34, 59, 8, 63, 16, 49, 56, 46, 21, 28, 32, 14, 26, 24, 40, 53, 37, 42, 7, 62, 55, 45, 31, 13, 39, 36, 6, 61, 44, 12, 35, 60, 11, 10, 9, }; public static int BitScanForward(ulong b) { return MagicTable[((ulong) ((long) b & -(long) b)*Magic) >> 58]; } public static int BitScanReverse(ulong b) { b |= b >> 1; b |= b >> 2; b |= b >> 4; b |= b >> 8; b |= b >> 16; b |= b >> 32; b = b & ~(b >> 1); return MagicTable[b*Magic >> 58]; } }También publiqué mi puerto C# del generador de secuencias en github
Otro artículo relacionado que no se menciona en la pregunta con una cobertura decente de las secuencias de De Bruijn se puede encontrar aquí .
Según mi comentario, esta es una función en C# para contar los bits cero iniciales modificados para un entero de 64 bits.
public static UInt64 CountLeadingZeros(UInt64 input) { if (input == 0) return 64; UInt64 n = 1; if ((input >> 32) == 0) { n = n + 32; input = input << 32; } if ((input >> 48) == 0) { n = n + 16; input = input << 16; } if ((input >> 56) == 0) { n = n + 8; input = input << 8; } if ((input >> 60) == 0) { n = n + 4; input = input << 4; } if ((input >> 62) == 0) { n = n + 2; input = input << 2; } n = n - (input >> 63); return n; } ACTUALIZAR:
Si está utilizando una versión más reciente de C#, verifique si esto está integrado según la respuesta a continuación. https://stackoverflow.com/a/61141435/1587755