Оказывается, это действительно возможно сделать без петель.Проще всего предварительно рассчитать (как минимум) 8-битную версию этой проблемы.Конечно, эти таблицы занимают место в кеше, но все равно должно быть чистое ускорение практически во всех современных компьютерных сценариях.В этом коде n = 0 возвращает наименьший установленный бит, n = 1 - наименьший и т. Д.
Решение с помощью __popcnt
Существует решениеиспользование встроенной функции __popcnt (вам нужно, чтобы __popcnt был чрезвычайно быстрым, иначе любой выигрыш в производительности по сравнению с простым циклическим решением будет спорным. К счастью, большинство процессоров эры SSE4 + поддерживают его).
// 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;
}
Это иллюстрирует, как разделить и победитьподход работает.
Общее решение
Существует также решение для "общих" архитектур - без __popcnt.Это можно сделать обработкой 8-битных блоков.Вам нужна еще одна справочная таблица, которая сообщает вам popcnt байта:
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;
}
Это, конечно, можно сделать с помощью цикла, но развернутая форма быстрее и необычная форма цикла будетмаловероятно, что компилятор может автоматически развернуть его для вас.