Resulta que de hecho es posible hacerlo sin bucles. Es más rápido precomputar la versión (por lo menos) de 8 bits de este problema. Por supuesto, estas tablas usan espacio de caché, pero aún debería haber una aceleración neta en prácticamente todos los escenarios modernos de PC. En este código, n = 0 devuelve el bit menos fijar, n = 1 es segundo-a-menos, etc.
Solución con __popcnt
Hay una solución usando el __popcnt intrínseca (que necesita __popcnt ser extremadamente rápido o cualquier ganancia de rendimiento sobre una simple solución de bucle será discutible. Afortunadamente, la mayoría de los procesadores de era SSE4 + lo soportan).
// lookup table for sub-problem: 8-bit v
byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v < 256 and n < 8
ulong nthSetBit(ulong v, ulong n) {
ulong p = __popcnt(v & 0xFFFF);
ulong shift = 0;
if (p <= n) {
v >>= 16;
shift += 16;
n -= p;
}
p = __popcnt(v & 0xFF);
if (p <= n) {
shift += 8;
v >>= 8;
n -= p;
}
if (n >= 8) return 0; // optional safety, in case n > # of set bits
return PRECOMP[v & 0xFF][n] << shift;
}
Esto ilustra cómo funciona el enfoque de dividir y conquistar.
Solución general
También hay una solución para architectures- "general" sin __popcnt. Se puede hacer procesando en fragmentos de 8 bits. Es necesario un mayor tabla de búsqueda que le indica la POPCNT de un byte:
byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v<256 and n < 8
byte POPCNT[256] = { ... } // POPCNT[v] is the number of set bits in v. (v < 256)
ulong nthSetBit(ulong v, ulong n) {
ulong p = POPCNT[v & 0xFF];
ulong shift = 0;
if (p <= n) {
n -= p;
v >>= 8;
shift += 8;
p = POPCNT[v & 0xFF];
if (p <= n) {
n -= p;
shift += 8;
v >>= 8;
p = POPCNT[v & 0xFF];
if (p <= n) {
n -= p;
shift += 8;
v >>= 8;
}
}
}
if (n >= 8) return 0; // optional safety, in case n > # of set bits
return PRECOMP[v & 0xFF][n] << shift;
}
Esto podría, por supuesto, hacerse con un bucle, pero la forma desenrollada es más rápido y la forma inusual del lazo haría que poco probable que el compilador pueda desenrollarlo automáticamente.
¿Usted está pidiendo un método general que se puede aplicar para darle una forma de calcular el enésimo bit más bajo para cualquier constante n, o necesita que funcione para cualquier n dada en tiempo de ejecución? Basado en el patrón de reducción de máscara de este tipo de ataques, dudo seriamente que haya una manera elegante de hacer lo último sin una construcción de bucle. –
Sí, proporciona tanto v como n en tiempo de ejecución. Tampoco podía pensar en ninguna forma de hacerlo sin bucles. Es difícil dividir el problema, pero no estoy seguro de que sea imposible superarlo. – VoidStar