Bit Hacking Hacks: intercalar bits de la manera obvia

estoy interesado en este problema

Entrelazar bits de la manera obvia

(de http://graphics.stanford.edu/~seander/bithacks.html )

unsigned short x; // Interleave bits of x and y, so that all of the unsigned short y; // bits of x are in the even positions and y in the odd; unsigned int z = 0; // z gets the resulting Morton Number. for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed... { z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1); } 

¿Puede alguien explicarme cómo funciona esto con un ejemplo?

por ejemplo, si tenemos x = 100101 y y = 010101 , ¿cuál será el resultado?

El intercalado de bits toma esencialmente dos números de entrada de n bits y produce un número de salida de 2 n bits que alternativamente toma bits de los dos números de entrada. Es decir, los bits de un número entran en los índices impares, y los bits del otro entran en los índices pares.

Así que para su ejemplo específico:

 x = 100101 = 1 0 0 1 0 1 y = 010101 = 0 1 0 1 0 1 interleaved = 011000110011 

Aquí utilizamos la convención de que los bits de x entran en los índices pares (0, 2, 4 …) y los bits de y entran en los índices impares (1, 3, 5 …). Es decir, el intercalado de bits no es una operación conmutativa ; interleave(x, y) generalmente no es igual a la interleave(y, x) .

También puede generalizar la operación de entrelazado de bits para incluir más de 2 números.

Los números entrelazados en bits exhiben propiedades estructurales que pueden aprovecharse en muchos algoritmos espaciales / estructuras de datos importantes.

Ver también

  • Wikipedia / Z-order (curva)
    • también conocido como Morton-Order / Morton código

Preguntas relacionadas

  • Cómo calcular un número de Morton 3D (intercalar los bits de 3 pulgadas)
  • Cómo desentrelazar bits (¿Desmortización?)

Algoritmo “obvio”

El algoritmo esencialmente recorre cada bit de los números de entrada, verificando si es 1 o 0 con bitwise y, combinando los dos bits con bitwise o, y concatenándolos con los cambios adecuados.

Para comprender cómo se reorganizan los bits, simplemente trabaje en un ejemplo simple de 4 bits. Aquí xi denota el bit i -th (basado en 0) de x .

 x = x3 x2 x1 x0 y = y3 y2 y1 y0 Mapping: z = y3 x3 y2 x2 y1 x1 y0 x0 x[i] --> z[i+i] z7 z6 z5 z4 z3 z2 z1 z0 y[i] --> y[i+i+1] 

Una vez que se haya convencido de que el patrón de mapeo es correcto, implementarlo es simplemente una cuestión de entender cómo se realizan las operaciones a nivel de bits.

Aquí está el algoritmo reescrito en Java para mayor claridad ( vea también en ideone.com ):

  int x = Integer.parseInt("100101", 2); int y = Integer.parseInt("010101", 2); int z = 0; for (int i = 0; i < Integer.SIZE; i++) { int x_masked_i = (x & (1 << i)); int y_masked_i = (y & (1 << i)); z |= (x_masked_i << i); z |= (y_masked_i << (i + 1)); } System.out.println(Integer.toBinaryString(z)); // prints "11000110011" 

Ver también

  • Wikipedia / Bitwise operaciones

“Intercalado” significa que combina los dos números alternando bits de cada fuente. Es más fácil de ver con el siguiente ejemplo

 x = 0000 y = 1111 result = 01010101 

Entrelazar los dos valores que has dado da el siguiente resultado:

 x = 100101 y = 010101 result = 100100110011