Buscar todos los valores de 2 bits que coinciden con otro patrón binario y luego sumarlos

Question

Primer valor:

Tengo un valor binario que es en realidad una serie compacta de valores de 2 bits. (Es decir, cada 2 bits en el valor binario representa 0, 1, 2 o 3.) Entonces, por ejemplo, 0, 3, 1, 2 se convierte en 00110110. En esta cadena binaria, todo lo que me importa son los 3 (o alternativamente, podría voltear las partes y solo preocuparme por los 0, si eso hace que tu respuesta sea más fácil). Todos los otros números son irrelevantes (por razones que abordaremos en un momento).

segundo valor:

I tiene un segundo valor binario que es también una serie compacta de los valores de 2 bits representado de la misma manera. Tiene una longitud idéntica al primer valor.

matemática:

Quiero que la suma de los números de 2 bits en el segundo valor que tienen la misma posición que un 3 desde el primer valor. En otras palabras, si tengo:

First: 11000011 
Second: 01111101 

Entonces sería mi respuesta "2" (I añadido el primer número y el último número de "segunda" juntos, porque esos eran los únicos que tenían un "11 "en el primer valor que los combinó.)

Quiero hacer esto en el menor número de ciclos de reloj posible (ya sea en una GPU o en una arquitectura x86). Sin embargo, generalmente estoy buscando un algoritmo, no una solución de ensamblador. ¿Hay alguna manera más rápida que enmascarar dos bits a la vez de cada número y ejecutar varios bucles?

Answer 1

Sure.

// the two numbers 
unsigned int a; 
unsigned int b; 

Ahora crear una máscara a partir de una que contiene bits '1' en una posición extraña sólo si existe en una era '11' que termina en la misma posición.

unsigned int mask = a & (a >> 1) & 0x55555555; 

ampliarlo para conseguir el patrón de '11' de vuelta:

mask = mask | (mask << 1); 

Así que ahora era si un 1101100011, la máscara es 1100000011.

A continuación, la máscara con la máscara de b:

b = b & mask; 

Puede realizar la adición de números (enmascarados) de b en paralelo:

b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2); 
b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4); 
b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8); 
b = (b & 0x0000ffff) + ((b & 0xffff0000) >> 16); 

Para un número de 32 bits, la suma está ahora en los bits más bajos de b. Este es un patrón comúnmente conocido para la adición paralela de campos de bits. Para números mayores a 32 bits, agregaría una ronda más para números de 64 bits y dos rondas para números de 128 bits.