Нахождение N непрерывные нулевые биты в целом числе слева от положения MSB другого целого числа

count_leading_zero_bits часто представляет собой единственную инструкцию, для которой компилятор предоставляет встроенную функцию. в противном случае поместите его в петлю.

count_trailing_zero_bits может использовать count_leading_zero_bits (x & -x) или поиск debruijn, если первый является циклом.

для простоты я предполагаю 32-битные значения.

int offset_of_zero_bits_over_msb_of_other_value( unsigned width , unsigned value , unsigned other ) {
  int count = 0;
  int offset = -1;
  int last = 1;
  int lz = count_leading_zero_bits( other );
  other |= ((1<<(32-lz2))-1); // set all bits below msb
  if ( value & ~other ) {
    value |= other; // set all bits below msb of other
    value = ~value; // invert so zeros are ones
    while ( value && count < width ) {
      count += 1; // the widest run of zeros
      last = value; // for counting trailing zeros
      value &= value >> 1; // clear leading ones from groups
    }
    offset = count_trailing_zero_bits( last );
  } else {
    count = lz2;
    offset = 32 - lz2;
  }
  return ( count < width ) ? -1 : offset;
}

Идея, лежащая в основе кода, такова:

  val1:  00000000000000000000000010000000 ( 128 )
  val2:  01000001000100000000100100001001 ( 1091569929 )
  lz1:   24
  lz2:   1
  val2:  01000001000100000000100011111111 // |= ((1<<(32-lz1))-1);
  val2:  10111110111011111111011100000000 // = ~val2
  val2:  00011110011001111111001100000000 // &= val2>>1 , count = 1
  val2:  00001110001000111111000100000000 // &= val2>>1 , count = 2
  val2:  00000110000000011111000000000000 // &= val2>>1 , count = 3
  val2:  00000010000000001111000000000000 // &= val2>>1 , count = 4
  val2:  00000000000000000111000000000000 // &= val2>>1 , count = 5
  val2:  00000000000000000011000000000000 // &= val2>>1 , count = 6
  val2:  00000000000000000001000000000000 // &= val2>>1 , count = 7
  val2:  00000000000000000000000000000000 // &= val2>>1 , count = 8

Таким образом, на каждом шаге все диапазоны нулей, а теперь и единиц, уменьшаются справа. Когда значение равно нулю, количество сделанных шагов равно ширине самого широкого пробега. В любой момент подсчет количества завершающих нулей даст смещение до ближайшего диапазона, состоящего как минимум из count нулей.

Если в какой-то момент количество превышает ширину, вы можете прекратить итерацию. Таким образом, максимальное количество итераций - это ширина, а не размер слова. Вы можете сделать это O (log n) шириной, потому что вы можете удваивать величину сдвига на каждой итерации, если вы не превышаете ширину.

Вот поиск DeBruijn для подсчета завершающих нулевых битов для 32-битных значений.

static const int MultiplyDeBruijnBitPosition[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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Я заметил, что в обоих ваших примерах для val1 установлен только один бит. Если это так, вы можете использовать трюк ДеБрюйна, чтобы найти MSB.

Здесь http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious есть несколько способов вычислить беззнаковое целое логарифмическое основание 2 беззнакового целого числа (которое также является позицией старшего установленного бита).

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

Вот мой новый и улучшенный алгоритм:

int test_fit_within_left_of_msb(  unsigned width,
                                  unsigned val1,
                                  unsigned val2 )
{
    int offset = 32;
    int msb = 0;
    unsigned mask;
    unsigned b;

    msb = 32 - __builtin_clz(val1); /* GCC builtin to count Leading Zeros */

    while(offset - width > msb)
    {
        mask = (((unsigned)1 << width) - 1) << (offset - width);
        b = val2 & mask;

        if (!b)
            return 32 - offset;

        offset = __builtin_ctz(b); /* GCC builtin to Count Trailing Zeros */
    }

    return -1;
}

Этот код имеет много улучшений по сравнению с моей первоначальной реализацией. В первую очередь, это удаление внутреннего цикла while путем простого подсчета нулевых битов. Во-вторых, я также заставил алгоритм работать со смещением, которое использует естественные значения битовых позиций, и таким образом убрал некоторые операции сложения и вычитания, которые использовались в моем первоначальном варианте, до успешного оператора возврата. Вы можете придираться к вычитанию смещения из 32.

Важным моментом здесь, в коде, является алгоритм - я понимаю, что есть проблемы переносимости и предположения, сделанные относительно типов и размеров. Возвращаясь вверх по странице к выводу, где ширина 8 может быть найдена в позиции 12 за 10 итераций, новый alogirthm делает то же самое за 2 итерации цикла.

Здесь я использовал встроенные модули GCC для удобства, код MultiplyDeBruijnBitPosition, который предоставил drawonward (из: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup) можно использовать для замены __builtin_ctz, а __bultin_clz можно заменить одним из кодов целочисленного лога по базе 2 с той же страницы.

Однако здесь есть одно опасение: данные (с разреженными битами), которые я использовал для тестирования заставляют этот алгоритм работать лучше, возможно, это будет не так хорошо, если рассматривать целые числа с более плотно установленными битами. (Неверно - подсчет нулей в конце числа позволяет избежать этого плохого случая).

1 (быстрый) метод заключается в использовании предварительно рассчитанных таблиц LOOKUP TABLES (LUTs) для каждого 8-битного байта:

PosOfFirst1, PosOfLast1, PosOfFirst0, PosOfLast0 -- все массивы по 256 байт

Предварительно рассчитайте таблицы, используя: (прошу прощения за плохой, паскалевский псевдокод)

PosOfLast1:

FOR EACH ByteVal (0..255):

if byteVal>127 return 8
elseif byteVal>63 return 7
...
elseif byteVal>0 return 1
else return 0

PosOfFirst1:

c:=0;
while c<8 do
begin
bv = byteVal and 1; 
if bv=1 then return c
else byteval shr 1;     
inc (c);
end;

Я использую простые ассемблерные процедуры для этих алгов. PosOfFirst0 и PosOfLast0 LUT могут быть предварительно вычислены с помощью этих двух таблиц, также как и TRAILING и LEADING 0 (или 1) count. Полезно также предварительно вычислить "минус 1" версии этих таблиц....

Затем вы можете использовать (для 8-битных байтов) var InputByte: Byte; FirstBit:=PosOfFirst1[InputByte] // v.fast

Для больших размеров (0, 16, 24, 32 +++++) используйте процедуры и циклы, которые проверяют каждый составляющий 8-битный байт. Может потребоваться доступ к памяти LUT, но этот метод все равно быстрее:

a) может быть использован легко, без необходимости вызова процедуры. b) сканирование 32-битного числа занимает 1 сдвиг и сравнение с 0 на байт с 1 необходимым поиском (если найден ненулевой байт) вместо n (0..32) сдвигов, и и сравнений... c) при хорошем программировании остановится после нахождения 1-й/последней 1

Принцип LUT применим к 'подсчету населения' + другие битовые манипуляции...

Cheers, PrivateSi

FASTER IS BETTER?!