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

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

2 голосов
/ 24 апреля 2011

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

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

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

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

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

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

Ответы [ 2 ]

3 голосов
/ 24 апреля 2011

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

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 бит, это, вероятно, даже выполнимо с точки зрения потребления памяти.

РЕДАКТИРОВАТЬ :

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

x&=x>>4
x&=x>>2
x&=x>>1

здесь 

110* ****

дает 

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

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

РЕДАКТИРОВАТЬ:

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

1 голос
/ 24 апреля 2011

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

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

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

...