Come estrarre un po 'in modo ottimale?

Question

Oggi ho avuto un'intervista in cui mi hanno chiesto di scrivere due funzioni "C", una per estrarre un singolo bit e l'altra per estrarre un intervallo di bit da un carattere. Ho impiegato un po 'di tempo e ho trovato questi metodi.

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)); 
} 

Ma l'intervistatore continuava a chiedermi se potevo accelerare il codice ulteriormente (in termini di cicli di CPU), e se non v'è alcuna possibilità di ottimizzazione che ho potuto fare per realizzarlo. Ero chiaramente fuori di sé e sono curioso di sapere come lo faresti?

Answer 1

In extractBit, se si sposta per primo, è possibile mascherare con 1 anziché (1<<pos). Considerando che pos è un argomento della funzione, che salva un calcolo.

return (byte >> pos) & 1;

Nella seconda funzione, che sarebbe affermano che startingPos e offset sono entrambi positivi anziché affermando che la loro somma è positiva, ha più senso in questo modo.

Answer 2

Un look up table?

Answer 3

Un altro si fa nella gamma di bit:

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

Come << 1 non è altro allora *2, è possibile effettuare questa operazione sul vostro costante (che se si opera su byte signle è solo sbarazzarsi di LSB).

Answer 4

È possibile velocizzare la prima funzione in primo luogo lo spostamento a destra e poi mascherare il bit:

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

Ciò consente di risparmiare una sola operazione.

Per la seconda domanda, suppongo che startingPos sia il primo bit del blocco che si desidera estrarre e offset è il numero di bit nel blocco necessario. allora si potrebbe utilizzare questo:

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

Naturalmente si deve stare attenti sui campi, così come avete fatto nel vostro codice.

EDIT: se si vuole extractBitRange(b,i,0) a comportarsi come extractBit(b,i) ed estrarre un singolo bit in posizione i, questa variante lo fa:

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

Answer 5

Se si vuole ottenere davvero veloce, è possibile utilizzare una tabella di ricerca. Immagino che questo è ciò che l'intervistatore stava facendo (come risposta finale a "come posso renderlo più veloce").

Fondamentalmente, ciò significa che si crea in anticipo una tabella enorme, mappando ogni possibile combinazione di parametri al risultato corretto. Ad esempio, si avrebbe:

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

Ovviamente questo avrebbe bisogno di essere messo in structues c dati validi (array, indicizzati da byte e pos). Questo ti permetterebbe, nella tua funzione, di restituire un posto in un array, in base a qualunque schema di indicizzazione tu scelga.

Per la prima funzione, questo non occuperebbe troppa memoria. Stiamo parlando di valori di valore di un byte (un byte può avere 256 valori diversi) volte 8 valori possibili per l'avvio di pos, che rende un array di 2048.

Per la seconda funzione, ciò richiederebbe effettivamente un molto più spazio. Dovresti moltiplicare 256 volte tutti i valori possibili sia per la posizione iniziale che per quella finale (tenendo presente che esistono combinazioni illegali di posizione iniziale e finale).

Immagino che l'intervistatore volesse solo che tu risponda che questo sarebbe un modo per accelerarlo, e quindi fornire il pensiero sopra nel tentativo di stimare quanto spazio costerebbe rispetto al tempo risparmiato.

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; 
}