Как устранить чередование битов (UnMortonizing?)
Что самый эффективный путь состоит в том, чтобы устранить чередование битов от интервала на 32 бита? Для этого конкретного случая я только обеспокоен нечетными битами, хотя я уверен, что просто обобщить любое решение обоих наборов.
Например, я хочу преобразовать 0b01000101 в 0b1011. Каков самый быстрый путь?
Править:
В этом приложении я могу гарантировать, что ровные биты являются всеми нулями. Я могу использовать в своих интересах тот факт, чтобы улучшить скорость или уменьшить пространство?
3 ответа
Учитывая, что вы знаете, что каждый второй бит в вашем приложении равен 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
Затем второй шаг работает с двумя битами за раз, и так далее.
Что касается скорости, 16-битная таблица поиска с 2 ^ 32 записями будет непревзойденной! Но если у вас не так много памяти, чтобы сэкономить, четыре поиска в таблице с 256 записями, плюс несколько сдвигов и операторов AND, чтобы сшить их вместе, может быть лучшим выбором. Или, возможно, золотая середина находится где-то посередине ... это зависит от имеющихся у вас ресурсов и как стоимость инициализации таблицы поиска будет амортизироваться в зависимости от количества операций поиска, которые вам необходимо выполнить.
Я не уверен, насколько быстрым это будет, но вы могли бы сделать что-то вроде
int a = 0b01000101;
int b = 0;
int i = 0;
while (a > 0) {
b |= (a & 1) << i;
a >>= 2;
}
, которое вытащит все нечетные биты из a и поместит их в b.