Как найти младший установленный бит без цикла

Этот трюк возвращает позицию самого правого бита 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() - компилятор часто превращает их в одну инструкцию процессора.