Этот трюк возвращает позицию самого правого бита
1 в 32-битном числе:
static const int table[32] = {
0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18, 6, 11, 5, 10, 9
};
int lowest_set_bit(uint32_t v)
{
return table[((v & -v) * 0x077CB531U) >> 27];
}
Выражение
v & -v изолирует младший установленный бит.Затем результат умножается на константу
0x077CB531 из последовательности де Брёйна. Для каждой из 32 возможных позиций старшие 5 бит произведения образуют уникальный индекс.Остаётся одно обращение к таблице - и позиция найдена без перебора всех битов.
Важно: функция рассчитана на
v != 0.В современном коде также стоит проверить
std::countr_zero() или __builtin_ctz() - компилятор часто превращает их в одну инструкцию процессора.