Ищете более эффективный алгоритм декодирования битового поля

Question

У меня есть приложение Visual Studio 2008 C++, где я получаю бит-карту (а не изображение). Каждый бит, который перевернулся, соответствует позиции на карте декодирования.

typedef unsigned char BYTE; 
const unsigned int COL_COUNT = 8; 
const unsigned int ROW_COUNT = 4; 

static char g_decode_map[ ROW_COUNT ][ COL_COUNT ] = 
{ 
    { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' }, 
    { 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p' }, 
    { 'q', 'r', 's', 't', 'u', 'v', 'w', 'x' }, 
    { 'y', 'z', ',', '.', ' ', ':', '-', '+' } 
}; 

// current implementation 
void Decode(const BYTE bitmap[ ROW_COUNT ], 
      const char decode_map[ ROW_COUNT ][ COL_COUNT ], 
      char decoded[ ROW_COUNT * COL_COUNT ]) 
{ 
    int found = 0; 
    for(int i = 0; i < ROW_COUNT; ++i) 
    { 
     for(int j = 0; j < COL_COUNT; ++j) 
     { 
      if(std::bitset<COL_COUNT>(bitmap[ i ]).test(j)) 
      { 
       decoded[ found++ ] = g_decode_map[ i ][ COL_COUNT - j - 1 ]; 
      } 
     } 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    BYTE bitmap[ ROW_COUNT ] = { 0x01, 0x80, 0x00, 0x00 }; 
    // expected output { 'h', 'i' } or { 'i', 'h' } order is unimportant 

    char decoded[ ROW_COUNT * COL_COUNT + 1 ] = { }; 
    Decode(bitmap, g_decode_map, decoded); 
    printf("Decoded: %s\r\n", decoded); 
    return 0; 
} 

Моя текущая реализация декодирования работает нормально, но мне кажется, что может быть более эффективный способ сделать это. Может ли кто-нибудь предложить более эффективный алгоритм?

Answer 1

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

for(int i = 0; i < ROW_COUNT; ++i) { 
    for(int j = 0; j < COL_COUNT; ++j) { 
     if(bitmap[i] & (1 << j)) { 
      ... 

1 << j производит маску, которая имеет только бит вы желающий набор для тестирования. Побитовая привязка маски с байт-байт возвращает true, только если этот бит установлен в bitmap[i]. Результат этого условного эквивалента должен быть эквивалентен результату вашего условного, и он должен быть намного быстрее.

Answer 2

Вы выполняете 64 условных проверки. 32 в циклах for и 32 внутри цикла for. Если вы не можете избавиться от 32 внутри цикла for, лучше всего вы можете сделать цикл, чтобы уменьшить количество условных операторов, выполняемых forloops. Строка и длина столбца определяются как константы. Вы можете развернуть циклы и жесткие коды некоторых чисел для индексов. Вместо того, чтобы иметь внутренний цикл for, вы можете написать 8 операторов if, как показано ниже.

Оставьте вопрос, что, если кто-то изменит постоянные значения? Затем код прерывается. Это верно. Если вам нужно, чтобы он был достаточно прочным, чтобы выдержать это, вы можете использовать рекурсию времени компиляции, чтобы развернуть петли (ссылки ниже). Кроме того, любой, кто смотрит на ваш код, будет страшно бояться и думать, что вы бог. : P Кроме того, решение Джейсона также ускорит процесс.

if(std::bitset<COL_COUNT>(bitmap[ i ]).test(0)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(1)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(2)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(3)) 
... 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(7)) 

Compile Time Loops(Answer #1)
Template Meta Programming

Answer 3

Это, как сделать это быстро, предполагая COL_COUNT == 8 (сделать это действительно быстро, использовать в линии ассемблер):

for(int i = 0; i < ROW_COUNT; ++i) 
    { 
     unsigned char next_byte = bitmap[i] ; 
     for(int j = 0; j < COL_COUNT; ++j) 
     { 
      if (next_byte & 0x80) 
      { 
       decoded[ found++ ] = g_decode_map[ i ][ j ]; 
      } 
      next_byte <<= 1 ; 
     } 
    } 

I закодировали его, чтобы воспроизвести поведение вашей программы - но уверены ли вы, что у вас все в порядке? Я ожидал бы, что вы будете увеличивать found каждый раз, а не только при обнаружении 1 -bit.