Как я могу эффективно перемешать биты?

Question

Как я могу эффективно перемешать биты?

Мне нужно перемешать 16-битное целое число без знака таким образом, чтобы четные индексы попадали в младший байт, а нечетные индексы попадали в верхний байт.

input:
fedcba98 76543210 (contiguously numbered)

output:
fdb97531 eca86420 (even and odd separated)

Мой код выглядит следующим образом:

typedef unsigned short u16;

u16 segregate(u16 x)
{
u16 g = (x & 0x0001);
u16 h = (x & 0x0004) >> 1;
u16 i = (x & 0x0010) >> 2;
u16 j = (x & 0x0040) >> 3;
u16 k = (x & 0x0100) >> 4;
u16 l = (x & 0x0400) >> 5;
u16 m = (x & 0x1000) >> 6;
u16 n = (x & 0x4000) >> 7;

u16 o = (x & 0x0002) << 7;
u16 p = (x & 0x0008) << 6;
u16 q = (x & 0x0020) << 5;
u16 r = (x & 0x0080) << 4;
u16 s = (x & 0x0200) << 3;
u16 t = (x & 0x0800) << 2;
u16 u = (x & 0x2000) << 1;
u16 v = (x & 0x8000);

return g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v;
}

Интересно, есть ли более элегантное решение, чем простое извлечение и сдвиг каждого отдельного бита?

18

bit-manipulation c++z-order-curve

Решение

Другие решения

Настольный подход, показанный другими, является наиболее переносимой версией и, вероятно, довольно быстрым.

Если вы хотите воспользоваться специальными наборами команд, есть и другие варианты. Например, для Intel Haswell и более поздних версий можно использовать следующий подход (требуется расширение набора команд BMI2):

unsigned segregate_bmi (unsigned arg)
{
unsigned oddBits  = _pext_u32(arg,0x5555);
unsigned evenBits = _pext_u32(arg,0xaaaa);
return (oddBits | (evenBits << 8));
}

13

Вы можете использовать 256-байтовую таблицу для каждого байта вашего 16-битного числа, созданного таким образом, чтобы выполнялось ваше четное / нечетное условие. Для создания таблиц вручную закодируйте записи в таблице (или используйте алгоритм, который у вас уже есть), и тогда будет произведено перемешивание во время компиляции. По сути, это будет концепция таблицы перевода.

12

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

Ах да, ищите таблицы для спасения 🙂 Вы можете даже сделать это с одной таблицей и одной дополнительной сменой:

u16 every_other[256] = {
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f};

u16 segregate(u16 x)
{
return every_other[x & 0xff]
| every_other[(x >> 8)] << 4
| every_other[(x >> 1) & 0xff] << 8
| every_other[(x >> 9)] << 12;
}

6

Таблицы. Но генерируйте их во время компиляции!

namespace details {
constexpr uint8_t bit( unsigned byte, unsigned n ) {
return (byte>>n)&1;
}
constexpr uint8_t even_bits(uint8_t byte) {
return bit(byte, 0) | (bit(byte, 2)<<1) | (bit(byte, 4)<<2) | (bit(byte, 6)<<3);
}
constexpr uint8_t odd_bits(uint8_t byte) {
return even_bits(byte/2);
}
template<unsigned...>struct indexes{using type=indexes;};
template<unsigned Max,unsigned...Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...>{};
template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{};
template<unsigned Max>using make_indexes_t=typename make_indexes<Max>::type;

template<unsigned...Is>
constexpr std::array< uint8_t, 256 > even_bit_table( indexes<Is...> ) {
return { even_bits(Is)... };
}
template<unsigned...Is>
constexpr std::array< uint8_t, 256 > odd_bit_table( indexes<Is...> ) {
return { odd_bits(Is)... };
}
constexpr std::array< uint8_t, 256 > even_bit_table() {
return even_bit_table( make_indexes_t<256>{} );
}
constexpr std::array< uint8_t, 256 > odd_bit_table() {
return odd_bit_table( make_indexes_t<256>{} );
}

static constexpr auto etable = even_bit_table();
static constexpr auto otable = odd_bit_table();
}

uint8_t constexpr even_bits( uint16_t in ) {
return details::etable[(uint8_t)in] | ((details::etable[(uint8_t)(in>>8)])<<4);
}
uint8_t constexpr odd_bits( uint16_t in ) {
return details::otable[(uint8_t)in] | ((details::otable[(uint8_t)(in>>8)])<<4);
}

живой пример

5

Ваш ответ на четные и нечетные биты в случайном порядке для 64 битов не является точным. Чтобы расширить 16-битное решение до 64-битного, нам нужно не только расширить маски, но и покрыть интервал перестановки от 1 до 16:

x = bit_permute_step(x, 0x2222222222222222, 1);
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0c, 2);
x = bit_permute_step(x, 0x00f000f000f000f0, 4);
**x = bit_permute_step(x, 0x0000ff000000ff00, 8);
x = bit_permute_step(x, 0x00000000ffff0000, 16);**

1

В пользу того, чтобы быть коротким:

unsigned short segregate(unsigned short x)
{
x = (x & 0x9999) | (x >> 1 & 0x2222) | (x << 1 & 0x4444);
x = (x & 0xC3C3) | (x >> 2 & 0x0C0C) | (x << 2 & 0x3030);
x = (x & 0xF00F) | (x >> 4 & 0x00F0) | (x << 4 & 0x0F00);
return x;
}

0

Источник

Accepted Answer

Существует очень удобный веб-ресурс, который помогает решить многие проблемы перестановки битов: Генератор кода для битовых перестановок. В этом конкретном случае подача «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;
}

Уровень параллелизма может быть увеличен еще больше (8 или 16 перестановок одновременно) с инструкциями SSE. (И последние версии gcc могут автоматически векторизовать этот код).

Если параллелизм не требуется и кэш данных не используется широко другими частями программы, лучшей альтернативой будет использование таблицы поиска. Различные подходы к 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 как отметил Нильс Пипенбринк. С парой 64 бит pext мы могли бы выполнить 4 16-битных шаффла параллельно. поскольку pext Инструкция предназначена именно для этого типа битовых перестановок, этот подход легко превосходит все остальные.

10