c++ - bitwise - Intercalar los bits de manera eficiente

bitwise operators c++

Question

Necesito hacer uint64_t de 2 uint32_t intercalando los bits: si A=a0a1a2...a31 y B=b0b1...b31 , necesito C = a0b0a1b1...a31b31 . ¿Hay alguna manera de hacer esto de manera eficiente? Hasta ahora solo tengo el enfoque ingenuo con un ciclo for de 32 iteraciones, donde cada iteración hace C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1)) .

Supongo que debería haber algún truco matemático como multiplicar A y B por un número especial que da como resultado entrelazar sus bits con ceros en el número resultante de 64 bits, de modo que lo único que queda es a estos productos. Pero no puedo encontrar ese multiplicador.

Otro posible camino a seguir es un compilador de instrucción intrínseca o de montaje, pero no sé de eso.

Answer 1

¿Una búsqueda de matriz corta y precalculada contaría como un "truco matemático"?

Precalcular una matriz de 256 uint16_t s:

static const uint16_t lookup[256]={0x0000, 0x0001, 0x0005 ..., 0x5555};

Podemos entrelazar dos valores de ocho bits y obtener fácilmente un valor de 16 bits:

uint16_t interleave(uint8_t a, uint8_t b)
{
    return (lookup[a] << 1) | lookup[b];
}

Cómo extender esto para intercalar dos valores de 32 bits en un valor de 64 bits debería ser obvio: llame esto cuatro veces, para cada uno de los cuatro bytes que componen uint32_t , luego << an | los resultados juntos. Sobornar al compilador para que complete todo, y el resultado final debería ser bastante rápido y barato.

Dado que la memoria RAM es barata en estos días, es posible que desee considerar una tabla precalculada de 65536 uint32_t s, también.

Answer 2

El enlace de NathanOliver ofrece la implementación de 16 bits -> 32 bits:

static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};

unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.  
            // x and y must initially be less than 65536.

x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];

y = [the same thing on y]

z = x | (y << 1);

Que funciona por:

1. deja los 8 bits bajos de x donde están. Mueva los 8 bits altos hacia arriba por 8;
2. divídalo por la mitad y haga lo mismo, esta vez dejando los pares bajos de 4 bits donde están y moviendo los otros por 4;
3. y otra vez, y otra vez

Es decir, procede como sigue:

abcdefghijklmnop
-> 00000000abcdefgh 00000000ijklmnop
-> 0000abcd0000efgh 0000ijkl0000mnop
-> 00ab00cd00ef00gh 00ij00kl00mn00op
-> 0a0b0c0d0e0f0g0h 0i0j0k0l0m0n0o0p

Y luego combina las dos entradas juntas.

Según mi comentario anterior, para ampliar eso a 64 bits, simplemente agregue un desplazamiento inicial por 16 y enmascare por 0x0000ffff0000ffff , ya sea porque puede seguir intuitivamente el patrón o como un paso de dividir y conquistar, convirtiendo el problema de 32 bits en dos problemas de 16 bits que no se solapan y luego usan la solución de 16 bits.