¿Cómo extraigo un bit de forma más óptima?

Question

Hoy tuve una entrevista donde me pidieron que escribiera dos funciones "C", una para extraer un bit y otra para extraer un rango de bits de un personaje. Me tomó un tiempo y se me ocurrieron estos métodos.

int extractBit(char byte, int pos) { 
    assert((pos >= 0) && (pos < 8)); 
    return ((byte & (1<<pos)) >> pos); 
} 
char extractBitRange(char byte, int startingPos, int offset) { 
    assert(((startingPos + offset) >= 0) && ((startingPos + offset) < 8)); 
    return (byte >> startingPos) & ~(0xff << (offset + 1)); 
} 

Pero el entrevistador me preguntaba si podía acelerar el código adicional (en términos de ciclos de CPU) y si hay algún alcance de la optimización que podía hacer para lograrlo. Estaba claramente mal y tengo curiosidad por saber cómo harías esto?

Answer 1

En extractBit, si cambia primero, puede enmascarar con 1 en lugar de (1<<pos). Considerando que pos es un argumento de la función, eso guarda un cálculo.

return (byte >> pos) & 1;

En la segunda función, yo afirmaría que startingPos y offset son ambos positivos en lugar de afirmar que su suma es positivo, tiene más sentido de esa manera.

Answer 2

¿Una tabla de consulta?

Answer 3

Otro haces en el rango de bits:

~(0xff << (offset + 1)) 
--> 
~(0xfe << offset) 

Como << 1 es nada más que *2, puede realizar esta operación en su constante (que si se está operando en bytes signle se acaba de deshacerse de LSB).

Answer 4

Puede acelerar la primera función, en primer lugar desplazando a la derecha y luego enmascarar el bit:

int extractBit(char byte, int pos) { 
    return (byte >> pos) & 0x01; 
} 

Esto le ahorra una operación.

Para la segunda pregunta, supongo que startingPos es el primer bit del fragmento que desea extraer y offset es la cantidad de bits en el fragmento que necesita. Posteriormente, se podría utilizar esto:

char extractBitRange(char byte, int startingPos, int offset) { 
    return (byte >> startingPos) & ((1 << offset)-1); 
} 

Por supuesto que hay que tener cuidado acerca de los rangos, tal como lo hizo en su código.

EDIT: si quieres extractBitRange(b,i,0) a comportarse como extractBit(b,i) y extraer un solo bit en la posición i, esta variante hace eso:

return (byte >> startingPos) & ((2 << offset) - 1); 

Answer 5

Si usted quiere conseguir realmente rápida, se puede utilizar una tabla de consulta. Supongo que eso es lo que el entrevistador estaba buscando (como respuesta final a "cómo puedo hacerlo más rápido").

Básicamente, eso significa que crea de antemano una tabla enorme, asignando todas las combinaciones posibles de parámetros al resultado correcto. Por ejemplo, usted tendría que:

byte = 0x0, pos = 0, result = 0 
byte = 0x0, pos = 1, result = 0 
... 
byte = 0x1, pos = 0, result = 1 

Obviamente esto tendría que ser puesto en structues datos válidos (c arrays, indexados por el byte y pos). Esto le permitiría, en su función, simplemente devolver un lugar en una matriz, según el esquema de indexación que elija.

Para la primera función, esto no ocuparía demasiada memoria. Estamos hablando de valor de un byte de valores (un byte puede tener 256 valores diferentes) Tiempos 8 valores posibles para la posición de partida, lo que hace que un conjunto de 2048.

Para la segunda función, esto en realidad sería tomar una Mucho mas espacio Necesitarás multiplicar 256 veces todos los valores posibles tanto para la posición inicial como la posición final (teniendo en cuenta que existen combinaciones ilegales de posición inicial y final).

Supongo que el entrevistador solo quería que respondiera que esta sería una forma de acelerarlo, y luego proporcionar el pensamiento anterior para tratar de estimar cuánto espacio costaría frente al tiempo ahorrado.

Answer 6

int extractBit(int byte, int pos) 
{ 
    if(!((pos >= 0) && (pos < 16))) 
    { 
     return 0; 
    } 
    return ((byte & (1<<pos)) >> pos); 
} 
int _tmain() 
{ 
    // TODO: Please replace the sample code below with your own. 

    int value; 
    signed int res,bit; 
    value = 0x1155; 
    printf("%x\n",value); 
    //Console::WriteLine("Hello World"); 
    //fun1(); 
    for(bit=15;bit>=0;bit--) 
    { 
     res =extractBit(value,bit); 
     printf("%d",res); 
    } 
    return 0; 
}