Algoritmo para la expansión/duplicación de bits?

¿Existe un algoritmo eficiente (rápido) que realice la expansión/duplicación de bits?Algoritmo para la expansión/duplicación de bits?

Por ejemplo, expanda cada bit en un valor de 8 bits por 3 (la creación de un valor de 24 bits):

1101 0101 => 11111100 01110001 11000111

El método de fuerza bruta que se ha propuesto es la creación de una tabla de búsqueda. En el futuro, el valor de expansión puede necesitar ser variable. Es decir, en el ejemplo anterior, estamos ampliando en 3, pero puede ser necesario expandirlo por algún otro valor (es). Esto requeriría varias tablas de búsqueda que me gustaría evitar si es posible.

Fuente

2012-01-26 jivany

Si solo se trata de valores de 8 bits, es casi seguro que la tabla de búsqueda sea la mejor opción. Utiliza muy poco espacio. ¿Puede dar más detalles sobre su caso de uso y qué operaciones espera que sean comunes? – templatetypedef

La entrada es un flujo de bits en serie constante. En el requisito actual, cada fragmento de datos llega a 8 bytes a la vez, que luego necesita que cada bit se expanda en 3 para que se envíe como otro flujo de bits. 64bits en 192bits de salida. Un requisito futuro puede implicar la adición de bits de "encabezado" antes de cada valor expandido de 8 bits y, por supuesto, el relleno a un límite de bytes. Las LUT son rápidas, pero dada la frecuencia con la que debe ejecutarse, se apreciará cualquier posible mejora en el rendimiento. – jivany

Muchas arquitecturas tienen instrucciones que pueden acelerar mucho este tipo de cálculos. Si no teme romper la compatibilidad multiplataforma, aprovechar estas instrucciones es casi seguro una ganancia, y si está optimizando algo algorítmicamente "trivial", entonces la clave es la optimización de bajo nivel. – Kaganar

Existe la posibilidad de que sea más rápido que la tabla de búsqueda si los cálculos aritméticos son por algún motivo más rápidos que el acceso a la memoria. Esto puede ser posible si los cálculos están vectorizados (PPC AltiVec o Intel SSE) y/o si otras partes del programa necesitan usar cada bit de memoria caché.

Si = 3, se necesitan factor de expansión de sólo 7 instrucciones:

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7;

O otra alternativa, con 10 instrucciones:

out = (in | in << 8) & 0x0F00F; 
out = (out | out << 4) & 0x0C30C3; 
out = (out | out << 2) & 0x249249; 
out *= 7;

Para otros factores de expansión> = 3:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = out * ((1 << shift) + 1) & mask; 
} 
out *= (1 << N) - 1;

u otra alternativa, para factores de expansión> = 2:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = (out | out << shift) & mask; 
} 
out *= (1 << N) - 1;

shift y mask es mejor calcular los valores antes del procesamiento del flujo de bits.

Fuente

2012-01-28 08:54:21

Respuesta fantástica.Mi colega y yo nos acercábamos a esto mientras hacíamos algunos intercambios de ideas y tableros de ideas, pero esto es mucho más eficiente que nuestro enfoque. Tendré que ejecutar algunas pruebas una vez que tengamos el resto del código implementado y ver cómo le va. – jivany

¿Alguien tiene un enlace a las matemáticas detrás de esto? He estado buscando pero he logrado encontrar magia sin una explicación de cómo funciona esto. Veo que hay un patrón en los números mágicos, pero todo lo demás se está escapando de mí. –

nvm, lo descubrí. Ayuda a escribir el binario y luego encuentra el patrón. Sin embargo, cualquier enlace sobre el tema sería muy apreciado. https://gist.github.com/corytodd/056ed01228f59fee9a13d00fc25b9a62 –

Puede hacerlo un bit de entrada a la vez. Por supuesto, será más lento que una tabla de búsqueda, pero si está haciendo algo así como escribir para un pequeño microcontrolador de 8 bits sin suficiente espacio para una tabla, debería tener la menor huella de ROM posible.

Fuente

2012-01-26 21:37:47 comingstorm

Algoritmo para la expansión/duplicación de bits?

Respuesta

Cuestiones relacionadas