генерация таблицы, которая указывает позицию nth 1 бит в байте во время компиляции

Question

Я пытаюсь выяснить, как сгенерировать массив предварительно вычисленных значений во время компиляции в C++ (C++ 11).

Массив объявлен как unsigned char precalcalated_positions[256][8], а для precalcalated_positions[x][y] задает положение бита (0-7) y + 1'th 1 бит, считая справа в байтовом значении x или 8, если это не так много 1 бит х

Так, например, элемент массива precalculated_positions[51][2] будет 4, так как 51 = 00110011 в двоичной системе, а с 3-го (2 + 1), 1 бит справа равен 1 < < 4.

While Я мог бы довольно легко написать программу для генерации исходного кода для этого массива, мне интересно, возможно ли, чтобы сам компилятор сгенерировал этот массив при компиляции возможно, используя некоторые умные метапрограммирование шаблона и, возможно, некоторые функции constexpr?

Код, который производит таблицу во время выполнения (не оптимизированной) следующим образом:

int calculate_index(unsigned char c,unsigned char pos) 
{ 
    int mask = 1; 
    for(int i=0;i<8;i++) { 
     if (c&mask) { 
      if (pos==0) { 
       return i; 
      } else { 
       pos--; 
      } 
     } 
     mask<<=1; 
    } 
    return 8; 
} 
void generate_table() { 
    for(int i=0;i<256;i++) for(int j=0;j<8;j++) { 
     precalulated_positions[i][j] = calculate_index(i,j); 
    } 
} 

Хотя любая помощь искренне оценена, пожалуйста, обратите внимание, что это для C++ 11 только. Для моих целей я не могу использовать конструкторы, которые являются новыми для C++ 14.

Если что-то неясно, спросите, пожалуйста, и я попытаюсь при необходимости уточнить.

Answer 1

Итак, я не понимал, что вы не можете использовать C++ 14. Я придумал другое решение, использующее только C++ 11. Я оставил код C++ 14 ниже.

Я преобразовал ваш алгоритм в рекурсивную версию (чтобы вписаться в функцию constexpr) и использовал пакеты параметров шаблонов для заполнения таблицы.

template<int... Is> 
struct Seq {}; 
template<int N, int... Is> 
struct Gen : Gen<N-1, N-1, Is...> {}; 
template<int... Is> 
struct Gen<0, Is...> : Seq<Is...> {}; 

constexpr auto computePosition(int c, int bit, int pos = 0) -> unsigned char { 
    return pos == 8 ? 
     8 : 
     (c & (1 << pos)) == 0 ? 
      computePosition(c, bit, pos+1) : 
      bit == 0 ? 
       pos : 
       computePosition(c, bit-1, pos+1); 
} 

template<int c, int... Is> 
constexpr auto generatePositions(Seq<Is...>) -> std::array<unsigned char, 8> { 
    return {{ computePosition(c, Is)... }}; 
} 

template<int c> 
constexpr auto generatePositions() -> std::array<unsigned char, 8> { 
    return generatePositions<c>(Gen<8>{}); 
} 

template<int... Is> 
constexpr auto generateTable(Seq<Is...>) -> std::array<std::array<unsigned char, 8>, 256> { 
    return {{ generatePositions<Is>()... }}; 
} 

constexpr auto generateTable() -> std::array<std::array<unsigned char, 8>, 256> { 
    return generateTable(Gen<256>{}); 
} 

Live example

C++, версия 14:

struct Table { 
    constexpr Table() : positions() { 
     for (auto c = 0; c < 256; ++c) { 
      for (auto i = 0; i < 8; ++i) { 
       int mask = 1; 
       auto pos = -1; 
       auto bit = i; 
       while (pos < 8 && bit >= 0) { 
        if (c & mask) { 
         --bit; 
        } 
        ++pos; 
        mask <<= 1; 
       } 
       positions[c][i] = pos; 
      } 
     } 
    } 

    unsigned char positions[256][8]; 
}; 

int main() 
{ 
    constexpr auto precalculated_positions = Table(); 
    static_assert(precalculated_positions.positions[51][2] == 4, "wrong"); 
} 

Значения находятся в positions поле любой переменной типа Table.

Live example