es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Concatenar bits individuales en C.

05 Jun, 2023 Programación

Tengo la siguiente situación:

Una función F1 genera una salida O1 que tiene un tamaño de N1 bits, donde en general N1 no será un múltiplo de 8 bits. A su vez, otra función F2 genera una salida O2 que tiene un tamaño de N2 bits, donde N2 puede o no ser múltiplo de 8 bits.

Quiero obtener una cadena de salida O construida con O2 adjunto a O1, con la siguiente condición:

Imaginemos que N1 % 8 es 3, y que los últimos tres bits de N1 son 101. También imaginemos que los primeros ocho bits de N2 son 01011111. La secuencia de bytes que obtendría tendría los primeros floor(N1 / 8) bytes de O1, luego el byte 10101011, y luego los bytes restantes obtenidos en N2, comenzando con el 111 que quedó de antes.

Lo que sucede es que tanto N1 como N2 pueden ser números extremadamente largos: mucho más grandes que la RAM de la computadora anfitriona. Por lo tanto, tendría que guardar los bits de N1 y N2 en el disco duro, luego realizar la concatenación como se describe anteriormente, guardando la salida resultante O.

Estoy buscando sugerencias sobre cómo llevar a cabo la tarea anterior de la manera más eficiente posible, teniendo en cuenta que, como dije, tanto N1 como N2 pueden ser arbitrariamente grandes. Lo que me preocupa en particular es el desplazamiento de bits que se debe realizar en O2.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para concatenar eficientemente las dos cadenas de salida O1 y O2, podemos seguir los siguientes pasos:

    1. Almacenar los bits de O1 y O2 en el disco duro como archivos individuales.
    2. Leer los bits de O1 desde el archivo y almacenarlos en un búfer.
    3. Anexar los bits restantes (si los hay) de O1 al principio de O2.
    4. Leer los bits de O2 desde el archivo y almacenarlos en un búfer, desplazados a la izquierda por el número de bits restantes de O1.
    5. Combinar los búferes de O1 y O2, bit a bit, para formar la cadena de salida concatenada O.
    6. Escribir los bits de O en un archivo nuevo en el disco duro.

    Para mejorar la eficiencia del proceso, podemos utilizar técnicas como la E/S con búfer, archivos mapeados en memoria y multihilo. La E/S con búfer implica utilizar un búfer para reducir el número de lecturas y escrituras en disco, mientras que los archivos mapeados en memoria nos permiten tratar los archivos del disco como si estuvieran en memoria. El multihilo se puede utilizar para leer y escribir los archivos en paralelo, lo que reduce aún más el tiempo que se tarda en realizar la concatenación.

    Al desplazar los bits de O2, podemos utilizar operaciones a nivel de bits en C para realizar el desplazamiento de manera rápida y eficiente. Por ejemplo, para desplazar los bits de un búfer a la izquierda en n bits, podemos utilizar el siguiente código:

    // Desplaza el búfer a la izquierda en n bits
void shiftLeft(char *buffer, int size, int n) {
    int i;
    for (i = 0; i < size - 1; i++) {
        buffer[i] = (buffer[i] << n) | (buffer[i+1] >> (8 - n));
    }
    buffer[size-1] <<= n;
}

    En esta función, desplazamos cada byte del búfer a la izquierda en n bits, y luego OR con los últimos n bits de cada byte y los primeros n bits del siguiente byte. Esto asegura que no perdamos ningún bit durante el desplazamiento.

    En resumen, utilizando una combinación de técnicas como la E/S con búfer, archivos mapeados en memoria, multihilo y operaciones a nivel de bits, podemos concatenar eficientemente grandes cadenas de salida O1 y O2, incluso cuando son demasiado grandes para caber en la RAM.

Comments are closed.