Jak wyodrębnić nieco w bardziej optymalny sposób?

Question

Miałem dzisiaj wywiad, w którym poprosili mnie o napisanie dwóch funkcji "C", jednego, by wyodrębnić jeden i drugi, by wyodrębnić zakres bitów od postaci. Wziąłem chwilę i wymyśliłem te metody.

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

Ale wywiad pytali mnie, czy mogę przyspieszyć kod dalej (pod względem cykli CPU) i czy jest jakiś zakres optymalizacji, które można zrobić, aby go osiągnąć. Byłem zupełnie nieswojo i jestem ciekawa, jak byś to zrobił?

Answer 1

W extractBit, jeśli przesuwasz pierwszy, możesz maskować przy pomocy 1 zamiast (1<<pos). Biorąc pod uwagę, że pos jest argumentem funkcji, która zapisuje obliczenia.

return (byte >> pos) & 1;

W drugiej funkcji, chciałbym stwierdzić, że startingPos i offset są zarówno pozytywne zamiast twierdząc, że ich suma jest dodatnia, to sprawia, że ​​więcej sensu w ten sposób.

Answer 2

Tabela wyników wyszukiwania?

Answer 3

Kolejny zrobić w zakresie bitów:

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

Jak << 1 jest niczym więcej niż *2, można dokonać tej operacji na swojej stałej (który, jeśli działają na signle bajtów jest po prostu pozbycie LSB).

Answer 4

Można przyspieszyć pierwszą funkcję najpierw przesuwa się w prawo, a następnie zamaskowanie bit:

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

Pozwala to zaoszczędzić jedną operację.

Dla drugiego pytania zakładam, że startingPos jest pierwszym fragmentem fragmentu, który chcesz wyodrębnić, a offset to liczba bitów w kawałku, których potrzebujesz. Następnie można użyć tego:

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

Oczywiście trzeba uważać o zakresach, tak samo, jak w kodzie.

EDIT: jeśli chcesz extractBitRange(b,i,0) zachowywać się jak extractBit(b,i) i wyodrębnić pojedynczego bitu na pozycji I, wariant ten robi:

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

Answer 5

Jeśli chcesz uzyskać naprawdę szybkie, można użyć tabeli odnośników. Zgaduję, że właśnie o to chodzi (jako ostateczna odpowiedź na pytanie "jak mogę to przyspieszyć").

Zasadniczo oznacza to, że tworzysz z wyprzedzeniem ogromną tabelę, mapując każdą możliwą kombinację parametrów do prawidłowego wyniku. Na przykład, trzeba:

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

Oczywiście byłoby to muszą być wprowadzone do ważnych structues c danych (tablic, indeksowanych przez bajt i POS). Umożliwi to, w swojej funkcji, zwrócenie miejsca w tablicy, w oparciu o wybrany schemat indeksowania.

Dla pierwszej funkcji, nie zajmie to zbyt dużej ilości pamięci. Mówimy o wartości wartości bajta (bajt może mieć 256 różnych wartości) razy 8 możliwych wartości dla pozycji początkowej, która tworzy tablicę 2048.

Dla drugiej funkcji,, to faktycznie dużo więcej miejsca. Będziesz musiał pomnożyć 256 razy wszystkie możliwe wartości zarówno dla pozycji początkowej, jak i końcowej (pamiętając, że istnieją niedozwolone kombinacje początkowej i końcowej pozycji).

Zgaduję, że prowadzący wywiad chciał tylko, abyś odpowiedział, że jest to sposób na przyspieszenie, a następnie przekazuje powyższe myślenie do próby oszacowania, ile przestrzeni zaoszczędziłoby w porównaniu do czasu.

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