c ++ 14 — обращение битов для N-разрядных слов с использованием c ++ constexpr
Я работаю над алгоритмом немного реверсирования для реализации FFT, моя реализация до сих пор
//assume the proper includes
template<unsigned long bits>
unsigned long&& bitreverse(unsigned long value){
std::bitset<bits> input(value);
std::bitset<bits> result;
unsigned long j=input.size()-1;
for (unsigned long i=0; i<input.size(); ++i) {
result[i]=input[j];
j--;
}
return std::move(result.to_ulong());
}
Мне нужно иметь возможность обратить биты в N-битное слово. Моя текущая реализация является функциональной, но я хотел бы переписать ее так, чтобы результат можно было использовать как constexprподпись функции должна быть либо:
template<unsigned long bits>
constexpr unsigned long&& bitreverse(unsigned long value);
или же:
template<unsigned long bits,unsigned long value>
constexpr unsigned long&& bitreverse();
или что-то близкое …
Я не уверен, как начать реализацию этого.
Я хотел бы избежать побитовых операций, если это возможно, но я не против них.
Спасибо
Решение
Вы можете просто сделать это:
template <unsigned long bits>
constexpr unsigned long bitreverse(unsigned long value) {
unsigned long result = 0;
for (std::size_t i = 0, j = bits - 1; i < bits; ++i, --j) {
result |= ((value & (1 << j)) >> j) << i;
}
return result;
}
Я не уверен, почему вы хотите использовать ссылку на r-значение для возвращаемого типа. Это не сделает ничего более эффективным, и я думаю, приведет к свисающей ссылке.
Другие решения
Ну, вот очевидный подход «грубой силы».
Это предполагает, что unsigned long long Тип данных для реализации представляет собой 64-битное целое число. Код может быть явно сокращен для 32-битных платформ.
Соблюдайте это bitreverse всегда может быть изначально обработан как 64-битный bitreverseзатем сдвиньте вправо, чтобы получить правильное количество бит из него.
Это немного многословно, но у него есть то преимущество, что оно достаточно простое, что большинство компиляторов может прожевать bitreverse константы во время компиляции. Для переменной это, безусловно, будет генерировать больше кода, чем итеративный подход, но современные процессоры, скорее всего, смогут пролистать ее без особых задержек, поскольку им не придется иметь дело с циклическим и прогнозированием ветвлений.
template<unsigned long bits>
constexpr unsigned long long bitreverse(unsigned long long v)
{
return (((v & 0x00000001ULL) << 63) |
((v & 0x00000002ULL) << 61) |
((v & 0x00000004ULL) << 59) |
((v & 0x00000008ULL) << 57) |
((v & 0x00000010ULL) << 55) |
((v & 0x00000020ULL) << 53) |
((v & 0x00000040ULL) << 51) |
((v & 0x00000080ULL) << 49) |
((v & 0x00000100ULL) << 47) |
((v & 0x00000200ULL) << 45) |
((v & 0x00000400ULL) << 43) |
((v & 0x00000800ULL) << 41) |
((v & 0x00001000ULL) << 39) |
((v & 0x00002000ULL) << 37) |
((v & 0x00004000ULL) << 35) |
((v & 0x00008000ULL) << 33) |
((v & 0x00010000ULL) << 31) |
((v & 0x00020000ULL) << 29) |
((v & 0x00040000ULL) << 27) |
((v & 0x00080000ULL) << 25) |
((v & 0x00100000ULL) << 23) |
((v & 0x00200000ULL) << 21) |
((v & 0x00400000ULL) << 19) |
((v & 0x00800000ULL) << 17) |
((v & 0x01000000ULL) << 15) |
((v & 0x02000000ULL) << 13) |
((v & 0x04000000ULL) << 11) |
((v & 0x08000000ULL) << 9) |
((v & 0x10000000ULL) << 7) |
((v & 0x20000000ULL) << 5) |
((v & 0x40000000ULL) << 3) |
((v & 0x80000000ULL) << 1) |
((v & 0x100000000ULL) >> 1) |
((v & 0x200000000ULL) >> 3) |
((v & 0x400000000ULL) >> 5) |
((v & 0x800000000ULL) >> 7) |
((v & 0x1000000000ULL) >> 9) |
((v & 0x2000000000ULL) >> 11) |
((v & 0x4000000000ULL) >> 13) |
((v & 0x8000000000ULL) >> 15) |
((v & 0x10000000000ULL) >> 17) |
((v & 0x20000000000ULL) >> 19) |
((v & 0x40000000000ULL) >> 21) |
((v & 0x80000000000ULL) >> 23) |
((v & 0x100000000000ULL) >> 25) |
((v & 0x200000000000ULL) >> 27) |
((v & 0x400000000000ULL) >> 29) |
((v & 0x800000000000ULL) >> 31) |
((v & 0x1000000000000ULL) >> 33) |
((v & 0x2000000000000ULL) >> 35) |
((v & 0x4000000000000ULL) >> 37) |
((v & 0x8000000000000ULL) >> 39) |
((v & 0x10000000000000ULL) >> 41) |
((v & 0x20000000000000ULL) >> 43) |
((v & 0x40000000000000ULL) >> 45) |
((v & 0x80000000000000ULL) >> 47) |
((v & 0x100000000000000ULL) >> 49) |
((v & 0x200000000000000ULL) >> 51) |
((v & 0x400000000000000ULL) >> 53) |
((v & 0x800000000000000ULL) >> 55) |
((v & 0x1000000000000000ULL) >> 57) |
((v & 0x2000000000000000ULL) >> 59) |
((v & 0x4000000000000000ULL) >> 61) |
((v & 0x8000000000000000ULL) >> 63)) >> (64 - bits);
}