Как найти первый нулевой бит в байте?

Здравствуйте.
Есть байт, нумерация битов начинается СПРАВА от НУЛЯ.
Подскажите, пожалуйста, как найти позицию первого нулевого бита без использования цикла?
UPD:
Нужно найти самый правый нулевой бит.
  • Вопрос задан
  • 216 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Сначала инвертируйте число (битовое не). Теперь надо найти самый правый единичный бит.
Можно вычесть из числа 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.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы