Ответ 1
Существует очень удобный веб-ресурс, который помогает решить многие проблемы немного перестановки: Генератор кода для битовых перестановок. В этом конкретном случае подача "0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15" на эту страницу производит довольно быстрый код.
К сожалению, этот генератор кода не может производить 64-битный код (хотя любой может загрузить источники и добавить эту опцию). Поэтому, если нам нужно параллельно выполнять 4 перестановки с использованием 64-битных инструкций, мы должны вручную развернуть все задействованные битмаски до 64 бит:
uint64_t bit_permute_step(uint64_t x, uint64_t m, unsigned shift) {
uint64_t t;
t = ((x >> shift) ^ x) & m;
x = (x ^ t) ^ (t << shift);
return x;
}
uint64_t segregate4(uint64_t x)
{ // generated by http://programming.sirrida.de/calcperm.php, extended to 64-bit
x = bit_permute_step(x, 0x2222222222222222ull, 1);
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0cull, 2);
x = bit_permute_step(x, 0x00f000f000f000f0ull, 4);
return x;
}
Уровень parallelism может быть увеличен еще больше (8 или 16 перестановок одновременно) с инструкциями SSE. (И последние версии gcc могут векторизовать этот код автоматически).
Если parallelism не требуется, и кеш данных широко не используется другими частями программы, лучшей альтернативой может быть использование таблицы поиска. Различные альтернативы LUT уже обсуждаются в других ответах, но еще можно сказать здесь:
- Первый и последний бит 16-битного слова никогда не перестраиваются, нам нужно перетасовать только биты 1..14. Поэтому (если мы хотим выполнить задачу с единственным доступом LUT), достаточно иметь LUT с 16K-элементами, что означает 32K памяти.
- Мы могли бы комбинировать подходы к вычислению таблиц и вычислений. Два поиска в одной таблице из 256 байтов могут перемешать каждый исходный байт отдельно. После этого нам нужно только обменять два средних 4-битных куска. Это позволяет поддерживать небольшую таблицу поиска, использует только 2 обращения к памяти и не требует слишком больших вычислений (т.е. Балансирует вычисления и доступ к памяти).
Вот реализация второго подхода:
#define B10(x) x+0x00, x+0x10, x+0x01, x+0x11
#define B32(x) B10(x+0x00), B10(x+0x20), B10(x+0x02), B10(x+0x22)
#define B54(x) B32(x+0x00), B32(x+0x40), B32(x+0x04), B32(x+0x44)
uint8_t lut[256] = {B54( 0x00), B54( 0x80), B54( 0x08), B54( 0x88)};
#undef B54
#undef B32
#undef B10
uint_fast16_t segregateLUT(uint_fast16_t x)
{
uint_fast16_t low = lut[x & 0x00ff];
low |= low << 4;
uint_fast16_t high = lut[x >> 8] << 4;
high |= high << 4;
return (low & 0x0f0f) | (high & 0xf0f0);
}
Но самый быстрый подход (если портативность не проблема) использует pext инструкция из BMI2 набора команд как отметил Нильс Pipenbrinck. С парой 64-битных pext мы могли бы выполнять 4 16-битных перетасовки параллельно. Поскольку инструкция pext предназначена именно для такого рода бит-перестановок, этот подход легко превосходит все остальные.