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

14

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ść.

bit-twiddler
źródło
3
To pytanie i nazwa twojego konta - świat znów ma sens ...
JK
+1 Ciekawe pytanie jako kontynuacja mojego i innych;)
Anto
Raz wykonałem też szybkie obliczenia parzystości. Parzystość jest trochę uciążliwa, ponieważ tradycyjnie wiąże się z pętlami i liczeniem, jeśli bit jest ustawiony, a wszystko to wymaga wielu skoków. Parzystość można obliczyć za pomocą shift i XOR, a następnie kilka tych wykonanych jeden po drugim unika pętli i skoków.
szybko_niedz
2
Czy wiesz, że jest cała książka o tych technikach? - Hackers Delight amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654
nikie
Tak, jest też strona internetowa poświęcona operacjom bitowym. Zapomniałem adresu URL, ale Google wkrótce go podłączy.
Szybko_niedz 11.0411

Odpowiedzi:

23

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;
}
Peter Taylor
źródło
7
+1. Ale od teraz będę miał koszmary o znalezieniu tego podczas sesji debugowania bez komentarza.
nikie
@nikie, muahahahaha! (Zwykle używam tego do takich problemów jak Project Euler - moja codzienna praca nie wymaga wiele kombinatoryki).
Peter Taylor
7

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;
}
gablin
źródło
Szybki sqrt jest również niesamowity. Carmack wygląda na jednego z najlepszych programistów.
BenjaminB
Wikipedia ma nawet starsze źródła, np. Beyond3d.com/content/articles/15
MSalters
0

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;
}
szybko
źródło
1
Oczywiście dotyczy to tylko mało znanych mikrokontrolerów. Żaden prawdziwy procesor wyprodukowany w ciągu ostatnich dwóch dekad nie potrzebuje biblioteki wykonawczej do dzielenia liczb całkowitych.
MSalters
1
Jasne, ale małe mikrosfery bez mnożnika sprzętowego są w rzeczywistości bardzo popularne. A jeśli pracujesz na terenie zabudowanym i chcesz zaoszczędzić 0,10 USD na każdym z milionów sprzedanych produktów, lepiej poznaj kilka brudnych sztuczek. Zaoszczędzone pieniądze = dodatkowy zysk, który sprawia, że ​​twój szef jest bardzo szczęśliwy.
quickly_now
Cóż, brudne ... to tylko pomnożenie przez .0101010101(około 1/3). Pro wskazówka: możesz także pomnożyć przez .000100010001i 101(co zajmuje tylko 3 przesunięcia bitów, ale ma lepsze przybliżenie.010101010101
MSalters
Jak mogę to zrobić, używając tylko liczb całkowitych i bez zmiennoprzecinkowego?
Szybko_niedz 11.0411
1
Bitowo, x * 101 = x + x << 2. Podobnie, x * 0.000100010001 to x >> 4 + x >> 8 + x >> 12.
MSalters