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

Question

Я пишу функцию для обработки входящего 32-разрядного буфера, представляющего изменение данных, когда он сравнивается с соответствующим сохраненным 32-битным буфером. Позиция изменяющегося бита представляет собой число (то есть значение 8 бит 3 бит), которое необходимо обработать, а также то, является ли изменение 0-> 1 или 1-> 0. Вот текущая реализация, пожалуйста, помогите мне улучшить ее! Обратите внимание, что это не фактический код, он был упрощен, чтобы быть контекстно-нейтральным.

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

Сейчас он работает, но мне не нравится, что он должен проверить каждый бит, проверяя бит 1 и переход через всю вещь. Если бы была гарантия быть только 1 бит, что было бы не слишком сложно понять, но это не так.

Редактировать: К Нейлу, я думаю, я надеюсь найти способ получить позиции бит после XOR в постоянное время, вместо того, чтобы полностью переходить через буфер и проверять бит один за другим.

Answer 1

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 супер небольшие изменения ...

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

Answer 2

uint32_t temp=oldBuffer^newBuffer, ntemp=newBuffer; 
for(int b=0;temp;++b,temp>>=1,ntemp>>=1) 
    if(temp&1) processNumber(b,ntemp&1); 

Answer 3

Вы могли бы получить некоторую работу, используя один или несколько «бит twiddling 'hacks на

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

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

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

/* 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... */ 

} 

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

Однако я был бы поражен, если бы это сделало какую-либо измеримую разницу, если это не было суперкритическим кодом.

Answer 4

Это зависит от того, что вы ожидаете от распределения (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 бит), то поиск таблицы будет снижаться.

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

Answer 5

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

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

Answer 6

Вы можете сделать это рекурсивный 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); 
    } 
}