bit manipulation - Cómo desentrelazar bits(¿Desmortización?)

bit-manipulation z-order-curve

Question

¿Cuál es la forma más eficiente de desentrelazar bits de un int de 32 bits? Para este caso en particular, solo me preocupan los bits impares, aunque estoy seguro de que es simple generalizar cualquier solución para ambos conjuntos.

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

EDITAR:

En esta aplicación, puedo garantizar que los bits pares son todos ceros. ¿Puedo aprovechar ese hecho para mejorar la velocidad o reducir el espacio?

Answer 1

Dado que sabes que cada bit es 0 en tu aplicación, puedes hacerlo así:

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

El primer paso se ve así:

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

Luego, el segundo paso funciona con dos bits a la vez, y así sucesivamente.

Answer 2

En términos de velocidad, una tabla de búsqueda de 16 bits de ancho con 2 ^ 32 entradas será difícil de superar. Pero si no tiene mucha memoria de sobra, cuatro búsquedas en una tabla de 256 entradas, más algunos turnos y AND para unirlos, podrían ser una mejor opción. O quizás el punto ideal está en un punto intermedio ... depende de los recursos que tenga disponibles y de cómo se amortizará el costo de inicializar la tabla de búsqueda en función del número de búsquedas que necesita realizar.

Answer 3

No estoy seguro de lo rápido que sería, pero podrías hacer algo como

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

Lo que sacaría todos los bits impares de a y los pondría en b.