Сначала инвертируйте число (битовое не). Теперь надо найти самый правый единичный бит.
Можно вычесть из числа 1, тогда поменяются все биты вплоть до этого искомого. Значит xor изначального числа и его же минус 1 даст нам столько единичных бит на конце, каков был номер искомого бита.
Дальше надо у этого числа подсчитать количество единичных бит - это тоже известная задача. Сначала представим, что каждый бит хранит сколько в этом бите единичных бит. Потом преобразуем это так, чтобы каждая пара подряд идущих бит хранила двоичное число - сколько единичных бит там было в этом отрезке. Потом каждая четверка бит и в конце все 8 бит. Переход от одного уровня к следующему можно сделать через сумму со сдвигом. Вот код:
// пусть x = 00001011b
x = ~x; // 11110100b
x = x ^ (x-1); // 11110100 xor 11110011 = 00000111
x = ((x >> 1) & 01010101b)+(x & 01010101b); // 00 00 01 10
x = ((x >> 2) & 00110011b)+(x & 00110011b); // 0000 0011
x = ((x >> 4) & 00001111b)+(x & 00001111b); // 00000011 = 2
x -= 1; // индексация с 0
Отдельно надо проверить, вдруг изначальное число было 255 - в таком случае искомого бита нет, но этот код вернет 7.
Можно сделать для большего количества бит, надо только еще операций добавить и маски расширить. Для 32-битных чисел надо будет добавить еще 2 операции.
Еще есть вариант с ассемблером в x86 есть операция
popcnt.
Средний
