Как удалить чередование битов (UnMortonizing?)

Question

Каков наиболее эффективный способ устранения чередования битов из 32-битного int? Для этого конкретного случая меня интересуют только нечетные биты, хотя я уверен, что просто обобщить любое решение для обоих наборов.

Например, я хочу конвертировать 0b01000101 в 0b1011, Какой самый быстрый способ?

РЕДАКТИРОВАТЬ:

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

Answer 1

Учитывая, что вы знаете, что каждый второй бит в вашем приложении равен 0, вы можете сделать это следующим образом:

x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

Первый шаг выглядит так:

  0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

Затем второй шаг работает с двумя битами за раз, и так далее.

Answer 2

С точки зрения скорости, справочную таблицу шириной 16 бит с 2^32 записями будет трудно превзойти! Но если у вас не так много свободной памяти, лучшим выбором может быть четыре поиска в таблице с 256 записями, плюс несколько сдвигов и AND для их соединения. Или, возможно, самое приятное место находится где-то посередине... это зависит от имеющихся у вас ресурсов и того, как стоимость инициализации таблицы поиска будет амортизироваться в зависимости от количества запросов, которые вам нужно выполнить.

Answer 3

Я не уверен, как быстро это будет, но вы могли бы сделать что-то вроде

int a = 0b01000101;
int b = 0;
int i = 0;
while (a > 0) {
    b |= (a & 1) << i;
    a >>= 2;
}

Который вытащил бы все лишние биты из a и поместил бы их в b.