Cómo des-entrelazar bits (UnMortonizing?)

Question

¿Cuál es la forma más eficiente para de-entrelazar bits de un int de 32 bits? Para este caso particular, sólo estoy preocupado por los bits impares, aunque estoy seguro de que es fácil de generalizar cualquier solución a ambos conjuntos.

Por ejemplo, quiero convertir en 0b01000101 0b1011. ¿Cuál es la forma más rápida?

EDIT:

En esta aplicación, que puede garantizar que incluso los bits son todos ceros. ¿Puedo tomar ventaja de este hecho para mejorar la velocidad o reducir el espacio?

Answer 1

Dado que usted sabe que todos los otros bits es 0 en su aplicación, puede hacerlo de esta manera:

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

El primer paso es similar al siguiente:

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

A continuación, el segundo paso funciona con dos bits a la vez, y así sucesivamente.

Answer 2

En términos de velocidad, una tabla de consulta de 16 bits de ancho con 2 ^ 32 entradas será difícil de superar! Pero si usted no tiene esa cantidad de memoria para repuesto, cuatro operaciones de búsqueda en una tabla de 256 entradas, además de unos cuantos turnos y AND para unirlas, podría ser una mejor elección. O tal vez el punto dulce es en algún punto intermedio ... depende de los recursos que tiene disponibles, y cómo el costo de la inicialización de la tabla de consulta se amortiza en el número de búsquedas que debe realizar.

Answer 3

No estoy seguro de cómo rápido que sería, pero se puede hacer algo como

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

¿Qué se retiraría todos los bits impares fuera de una y ponerlos en b.