Jak uniknąć rozgałęzienia w C dla tej operacji

Question

Czy istnieje sposób usunięcia poniższej instrukcji if, aby sprawdzić, czy wartość jest niższa niż 0?

int a = 100; 
int b = 200; 
int c = a - b; 

if (c < 0) 
{ 
    c += 3600; 
} 

Wartość c powinna leżeć pomiędzy 0 i 3600. Zarówno a i b są podpisane. Wartość a również powinna leżeć między 0 a 3600. (tak, jest to wartość zliczająca w 0.1 stopnia). Wartość zostanie zresetowana przez przerwanie do 3600, ale jeśli to przerwanie przychodzi zbyt późno, to niedomiar, co nie stanowi problemu, ale oprogramowanie powinno nadal być w stanie sobie z nim poradzić. Które to robi.

Dokonujemy tego w niektórych miejscach, w których obliczamy pozycje. (Obliczanie nowej pozycji itp.)

Byłem przyzwyczajony do podpowiedzi, że operator modulo używa podpisu dzielnika, w którym nasz kompilator (C89) używa sygnatury dywidendy.

Czy jest jakiś sposób na wykonanie tego obliczenia w inny sposób? wyniki przykład:

a - b = c 
100 - 200 = 3500 
200 - 100 = 100 

Answer 1

Dobre pytanie! Co powiesz na to?

c += 3600 * (c < 0); 

Jest to jeden ze sposobów zachowania gniazd predykcyjnych gałęzi.

Answer 2

Dlaczego jesteś zaniepokojony branży? [powodów podanych w komentarzach do pytania.]

Alternatywą jest takim jak:

((a - b) + 3600) % 3600 

Zakłada a i b są w zakresie 0..3600 już; jeśli nie są one pod kontrolą, tym bardziej ogólne rozwiązanie jest jeden Drew McGowensuggests:

((a - b) % 3600 + 3600) % 3600 

Oddział panna musi być bardzo drogie, aby to znacznie obliczenie warto.

Answer 3

@skjaidev pokazał, jak to zrobić bez rozgałęziania. Oto w jaki sposób automatycznie uniknąć mnożenia jak również gdy int s są dwójki-uzupełnienie:

#if ((3600 & -0) == 0) && ((3600 & -1) == 3600) 
c += 3600 & -(c < 0); 
#else 
c += 3600 * (c < 0); 
#endif 

Answer 4

Co o tym (przy założeniu 32-bitowych ints):

c += 3600 & (c >> 31); 

c >> 31 ustawia wszystkie bity do oryginalnego MSB, co oznacza 1 dla liczb ujemnych i 0 dla innych w 2-dopełniaczu.

Negatywna zmiana liczby cyfr jest formalnie definiowana przez implementację zgodnie ze standardowymi dokumentami C, jednak prawie zawsze jest realizowana z kopiowaniem MSB (wspólne procesory mogą to zrobić w pojedynczej instrukcji).

To na pewno nie spowoduje powstania oddziałów, w przeciwieństwie do (c < 0), które mogą być implementowane z odgałęzieniem w niektórych przypadkach.

Answer 5

Co chcesz zrobić to arytmetyka modułowa.Twój komputer z uzupełnieniem 2 już to robi z matematyką całkowitą. A zatem, mapując twoje wartości na arytmetyczne uzupełnienie 2, możesz uwolnić działanie modolo.

Podstęp przedstawia kąt jako ułamek 360 stopni między 0 a 1-epsilon. Oczywiście wtedy wasze stałe kąty musiałyby być reprezentowane podobnie, ale nie powinno to być trudne; to tylko odrobina matematyki, którą możemy ukryć w funkcji konwersji (er, makro).

Wartość tego pomysłu polega na tym, że jeśli dodasz lub odejmiesz kąty, otrzymasz wartość, której części ułamka chcesz i której część całkowita chcesz wyrzucić. Jeśli reprezentujemy frakcję jako 32-bitową stałą liczbę punktów z dwójkowym punktem na 2^32 (np. Na lewo od tego, co zwykle uważa się za bit znaku), wszelkie przepełnienia frakcji po prostu spadają z góry 32-bitowa wartość za darmo. Więc robisz wszystkie matematykę całkowitą, a usuwanie "przepełnienia" dzieje się za darmo.

Więc ja przepisać kod (konserwujący ideę stopni razy 10):

typedef unsigned int32 angle; // angle*3600/(2^32) represents degrees 
    #define angle_scale_factor 1193046.47111111 // = 2^32/3600 
    #define make_angle(degrees) (unsigned int32)((degrees%3600)*angle_scale_factor) 
    #define make_degrees(angle) (angle/(angle_scale_factor*10)) // produces float number 

    ... 

    angle a = make_angle(100); // compiler presumably does compile-time math to compute 119304647 
    angle b = make_angle(200); // = 238609294 
    angle c = a - b; // compiler should generate integer subtract, which computes 4175662649 

    #if 0 // no need for this at all; other solutions execute real code to do something here 
    if (c < 0) // this can't happen 
    { c += 3600; } // this is the wrong representation for our variant 
    #endif 


    // speed doesn't matter here, we're doing output: 
    printf("final angle %f4.2 = \n", make_degrees(c)); // should print 350.00 

Nie skompilowany i uruchomić tego kodu.

Zmiany, które sprawiają, że stopnie razy 100 lub 1 są dość łatwe; zmodyfikuj współczynnik angle_scale_factor. Jeśli masz maszynę 16-bitową, przełączanie na 16 bitów jest równie łatwe; jeśli masz 32 bity i nadal chcesz zrobić tylko 16-bitową matematykę, musisz zamaskować wartość do wydrukowania na 16 bitów.

To rozwiązanie ma jeszcze jedną fajną właściwość: udokumentowałeś, które zmienne są kątami (i mają zabawne reprezentacje). Pierwotny kod OP właśnie nazwał je ints, ale to nie jest to, co reprezentują; przyszły opiekun zostanie zaskoczony oryginalnym kodem, zwłaszcza jeśli znajdzie odejmowanie od zmiennych.