Jaka jest twoja ulubiona technika bitowa? [Zamknięte]

Kilka dni temu członek StackExchange Anto zapytał o prawidłowe zastosowania dla operatorów bitowych. Stwierdziłem, że przesunięcie było szybsze niż pomnożenie i podzielenie liczb całkowitych przez potęgę dwóch. Członek StackExchange Daemin odparł, stwierdzając, że przesunięcie w prawo przedstawia problemy z liczbami ujemnymi.

W tym momencie nigdy tak naprawdę nie myślałem o użyciu operatorów shift z podpisanymi liczbami całkowitymi. Wykorzystałem tę technikę przede wszystkim przy tworzeniu oprogramowania niskiego poziomu; dlatego zawsze używałem liczb całkowitych bez znaku. C wykonuje logiczne zmiany na liczbach całkowitych bez znaku. Podczas logicznego przesunięcia w prawo nie zwraca się uwagi na bit znaku. Opróżnione bity są wypełnione zerami. Jednak C wykonuje operację przesunięcia arytmetycznego podczas przesuwania liczby całkowitej ze znakiem w prawo. Opróżnione bity są wypełnione bitem znaku. Ta różnica powoduje, że wartość ujemna jest zaokrąglana w kierunku nieskończoności zamiast skracana w kierunku zera, co jest zachowaniem innym niż znak dzielenia liczb całkowitych.

Kilka minut namysłu zaowocowało rozwiązaniem pierwszego rzędu. Rozwiązanie warunkowo konwertuje wartości ujemne na wartości dodatnie przed przesunięciem. Wartość jest warunkowo konwertowana z powrotem do postaci ujemnej po wykonaniu operacji przesunięcia.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

Problem z tym rozwiązaniem polega na tym, że warunkowe instrukcje przypisania są zwykle tłumaczone na co najmniej jedną instrukcję skoku, a instrukcje skoku mogą być kosztowne w procesorach, które nie dekodują obu ścieżek instrukcji. Konieczność dwukrotnego ponownego zalania potoku instrukcji dobrze wpływa na wzrost wydajności uzyskany przez przesunięcie zamiast podziału.

W związku z powyższym obudziłem się w sobotę z odpowiedzią na problem z przypisaniem warunkowym. Problem zaokrąglania występujący podczas wykonywania operacji przesunięcia arytmetycznego występuje tylko podczas pracy z reprezentacją uzupełnienia do dwóch. Nie występuje w przypadku reprezentacji dopełniacza. Rozwiązanie tego problemu polega na przekształceniu wartości uzupełnienia dwóch na wartość uzupełnienia jednego przed wykonaniem operacji przesunięcia. Następnie musimy przekonwertować wartość uzupełnienia jednego z powrotem na wartość uzupełnienia dwóch. Nieoczekiwanie możemy wykonać ten zestaw operacji bez warunkowego przekształcania wartości ujemnych przed wykonaniem operacji przesunięcia.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

Wartość ujemna dopełniacza dwóch jest przekształcana na wartość ujemną dopełniacza jednego przez odjęcie jednego. Z drugiej strony ujemna wartość dopełniacza jednego jest konwertowana na ujemną wartość dopełniacza dwóch poprzez dodanie jednego. Powyższy kod działa, ponieważ bit znaku służy do konwersji dopełniacza dwóch na dopełnienie jednego i odwrotnie . Tylko wartości ujemne będą miały ustawione bity znakowe; dlatego znak zmiennej będzie równy zero, gdy a jest dodatnie.

Biorąc powyższe pod uwagę, czy możesz pomyśleć o innych bitowych hackach, takich jak powyższy, które trafiły do ​​twojej torby z trikami? Jaki jest twój ulubiony bit-hack? Zawsze szukam nowych hacków zorientowanych na wydajność.

Uwielbiam hack Gospera (HAKMEM # 175), bardzo sprytny sposób na pobranie liczby i uzyskanie następnej liczby z taką samą liczbą bitów. Przydaje się na przykład do generowania kombinacji kprzedmiotów z n:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}

Metoda szybkiego odwrotnego pierwiastka kwadratowego wykorzystuje najbardziej dziwne techniki na poziomie bitów do obliczenia odwrotności pierwiastka kwadratowego, jakie kiedykolwiek widziałem:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Dzielenie przez 3 - bez uciekania się do wywołania biblioteki wykonawczej.

Okazuje się, że podział na 3 (dzięki podpowiedzi na temat przepełnienia stosu) może być przybliżony jako:

X / 3 = [(x / 4) + (x / 12)]

A X / 12 to (x / 4) / 3. Nagle pojawia się tutaj element rekurencji.

Okazuje się również, że jeśli ograniczysz zakres liczb, w które grasz, możesz ograniczyć liczbę potrzebnych iteracji.

A zatem, dla liczb całkowitych bez znaku <2000, poniższy jest szybki i prosty algorytm / 3. (W przypadku większych liczb po prostu dodaj więcej kroków). Kompilatory optymalizują to, dzięki czemu są szybkie i małe:

static unsigned short FastDivide3 (const unsigned short arg)
{
  unsigned short RunningSum;
  unsigned short FractionalTwelth;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  // Więcej powtórzeń powyższych 2 linii dla większej precyzji

  return RunningSum;
}

Jeśli spojrzysz na Erlang, istnieje cała DSL do wykonywania operacji bitowych. Więc możesz po prostu rozbić strukturę danych na części, mówiąc coś takiego:

<> = << 1,17,42: 16 >>.

Pełne szczegóły tutaj: http://www.erlang.org/doc/reference_manual/expressions.html#id75782