Помогите мне улучшить этот код обработки битового буфера C++

Возможно, вы могли бы повысить производительность, используя один или несколько хаков «покрутить биты» на

• http://graphics.stanford.edu/~seander/bithacks.html

В частности, алгоритмы для «нахождения целочисленного логарифмического основания 2» (положение самого старшего набора битов). Это позволит вам определить, какие биты установлены более непосредственно, чем зацикливание на каждом бите.

Если вам необходимо обрабатывать биты в порядке от младшего к старшему, вы можете использовать небольшую модификацию методов Кернигана для подсчета битов:

/* note: untested code */
while (temp) {

    uint32_t bit = temp & (~(temp & (temp - 1)); /* isolate lowest bit */

    temp &= ~bit;

    uint32_t bit_number = /* use find log base 2 hack */;

    /* etc... */

}

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

Однако я был бы удивлен, если бы это имело какое-либо измеримое значение, если бы это не было сверхкритическим фрагментом кода.

Как насчет использования стандартной библиотеки? Нет необходимости сдвигать или, и т. д., чтобы проверить, верны ли биты. Проверка битов в наборе битов гарантированно будет постоянным временем. И пишет намного чище и понятнее.

const std::bitset<32> oldbits( oldBuffer );
const std::bitset<32> newbits ( newBuffer );

for( size_t index = 0; index != oldbits.size(); ++index ) {
   if( oldbits[ index ] != newbits[ index ] ) {
       processNumber( index, newbits[ index ] )
   }
}

Примечание: здесь вам также не нужен XOR, так как у вас есть прямой доступ к битам. Однако вы можете использовать его для экономии производительности.

 uint32_t temp = oldBuffer ^ newBuffer;
 uint32_t number = 0;
 uint32_t bitmask=1;
 while (temp != 0)
 {
     if (temp & 0x1)
     {
         processNumber(number, ((newBuffer & bitmask) != 0));
     }
     number++;
     temp = temp >> 1;
     bitmask <<=1;
 }
 oldBuffer = newBuffer;

2 очень маленьких изменения...

ваш код уже был достаточно эффективным

Это зависит от того, что вы ожидаете от распределения (oldBuffer ^ newBuffer). Если это совершенно случайно и полный диапазон 32 бита, то у вас есть в среднем 16 циклов.

Одним из возможных решений является создание такой таблицы

int lookup[255][8] = {
  { -1, -1, -1, -1, -1, -1, -1, -1 }, // 0 has no bits set
  {  0, -1, -1, -1, -1, -1, -1, -1 }, // 1 has only the 0th bit set
  {  1, -1, -1, -1, -1, -1, -1, -1 }, // 2 has only the 1st bit set
  {  0,  1, -1, -1, -1, -1, -1, -1 }, // 3 has the 0th, 1st bit set
  {  2, -1, -1, -1, -1, -1, -1, -1 }, // 4 has only the 2nd bit set
  ...
  {  0,  1,  2,  3,  4,  5,  6,  7 }, // 255 has all bits set
}       

При этом вам нужно выполнить цикл 4 раза (1 для каждого байта), а затем 1 раз для каждого установленного бита (в среднем 4) - эй, это 16.

Но если количество установленных битов невелико (в среднем намного меньше половины 32-битных), то поиск в таблице будет остановлен.

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

Вы можете сделать это рекурсивно, как B-Tree :)

go(oldBuffer ^ newBuffer, 16, 0, newBuffer);
...

void go(temp, half, pos, bitValue)
{
    if (half > 1) {
      uint32_t mask = (1 << half) - 1;
      if (temp & mask)    go(temp & mask, half/2, pos, bitValue & mask);
      temp >>= half;
      if (temp & mask)    go(temp & mask, half/2, pos + half, (bitValue >> half) & mask);
    } else {
      if (temp & 1) processNumber(pos, bitValue&1);
      if (temp & 2) processNumber(pos+1, bitValue/2&1);
    }
}