Как я могу подсчитать количество последовательно установленных битов в байте слева направо до первого 0?

ProgramBox

Как я могу подсчитать количество последовательно установленных битов в байте слева направо до первого 0?

Post author:admin
Запись опубликована:15 мая, 2023
Post category:Вопросы по программированию

#c #bit-manipulation #bitwise-operators

#c #манипулирование битами #побитовые операторы

Вопрос:

Я не силен в английском, я не могу спросить лучше, но, пожалуйста, ниже:

если байт в двоичном формате равен 1 0 0 0 0 0 0 0 0 0 0, то результат равен 1
если байт в двоичном формате равен 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000, то результат равен 3
если байт в двоичном формате равен 1 1 1 1 0 0 0 0 0 0, то результат равен 4
если байт в двоичном формате равен 1 1 1 1 0 0 0 0, то результат равен 5
если байт в двоичном формате равен 1 1 1 0 0 0 0, то результат равен
если байт в двоичном формате равен 1 1 1 1 1 1 0 0 тогда результат равен 6
если байт в двоичном формате равен 1 1 1 1 1 1 1 1 0, то результат равен 7
если байт в двоичном формате равен 1 1 1 1 1 1 1 1 1, то результат равен 8

Но если, например, байт в двоичном формате равен 1 1 1 0 * * * * тогда результат равен 3.

Я бы определил, сколько битов установлено последовательно слева направо с помощью одной операции.

Результаты — это не обязательно цифры от 1 до 8, просто что-то, что нужно отличать. Я думаю, что это возможно за одну или две операции, но я не знаю как.

Если вы не знаете решения, состоящего всего из 2 операций, пожалуйста, напишите и это, и я больше не буду его пробовать.

1. Итак, 1 1 1 0 1 1 1 1 0 приводит к 3 или 6?

2. и что вы подразумеваете под «одной операцией»? одна инструкция процессора? (если да, то какой процессор?) или одна строка кода?

3. Это дает 3. 1 1 1 0 1 1 1 0 идеально соответствует 1 1 1 0 * * * * шаблону, приведенному в примере!

4. одна операция, я полагаю, имеет значение O(1) ?

Ответ №1:

Самое простое неветвящееся решение, которое я могу придумать:

 y=~x
y|=y>>4
y|=y>>2
y|=y>>1

Инвертируем x и увеличиваем самый левый 1-бит (который соответствует самому левому 0-биту в неинвертированном значении) вправо. Выдаст разные значения (правда, не 1-8, но сопоставить довольно легко).

 110* ****

превращается в

 001* ****
001* **1*
001* 1*1*
0011 1111

Редактировать:

Как указано в другом ответе, использование предварительно вычисленной таблицы поиска, вероятно, является быстрым. Учитывая только 8 бит, это, вероятно, даже возможно с точки зрения потребления памяти.

Редактировать:

Хех, упс, виноват.. Вы можете пропустить инвертирование и вместо этого выполнить ands.

 xamp;=x>>4
xamp;=x>>2
xamp;=x>>1

здесь

 110* ****

дает

 110* **0*
110* 0*0*
1100 0000

Как вы можете видеть, все значения, начинающиеся со 110, приведут к одному и тому же результату (1100 0000).

Редактировать:

На самом деле, версия ‘и’ основана на неопределенном поведении (смещение отрицательных чисел) и обычно будет поступать правильно, если используется 8-разрядный символ со знаком (т. Е. char, а не беззнаковый char в C), но, как я уже сказал, поведение не определено и может не всегда работать.

Ответ №2:

Я бы поддержал таблицу поиска … в противном случае вы также можете сделать что-то вроде:

 unsigned long inverse_bitscan_reverse(unsigned long value)
{
    unsigned long bsr = 0;
    _BitScanReverse(amp;bsr, ~value); // x86 bsr instruction
    return bsr;
}

РЕДАКТИРОВАТЬ: Не то чтобы вам нужно было остерегаться особого случая, когда «значение» не имеет обнуленных битов. Смотрите документацию для _BitScanReverse .