2013-07-19 3 views
7

C'è un modo per rimuovere la seguente istruzione if per verificare se il valore è inferiore a 0?Come evitare la ramificazione in C per questa operazione

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

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

Il valore di c deve essere tra 0 e 3600. Sia a e b sono firmati. Anche il valore di a deve essere compreso tra 0 e 3600. (sì, è un valore di conteggio in 0,1 gradi). Il valore viene ripristinato da un interrupt a 3600, ma se tale interrupt arriva troppo tardi, esso non è un problema, ma il software dovrebbe essere ancora in grado di gestirlo. Che fa

Facciamo questo controllo if (c < 0) in alcuni punti in cui stiamo calcolando le posizioni. (Calcolo di una nuova posizione, ecc.)

Ero abituato a pitoni modulo operatore per utilizzare la firma del divisore in cui il nostro compilatore (C89) utilizza la firma dei dividendi.

C'è qualche modo per fare questo calcolo in modo diverso? esempio i risultati:

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

Perché sei preoccupato per la filiale? L'alternativa è qualcosa come '((a - b) + 3600)% 3600'. Questo presuppone che 'a' e' b' siano nel range '0..3600' già; se non sono sotto controllo, la soluzione più generale è quella che Drew McGowen suggerisce: ((a - b)% 3600 + 3600)% 3600'. La perdita del ramo deve essere molto costosa per rendere utile quel calcolo. –

+3

Un trucco che usavo sarebbe '((a - b)% 3600 + 3600)% 3600' - sebbene con due operatori modulo, in realtà potrebbe essere meglio usare solo il confronto –

+0

@JonathanLeffler abbiamo un vecchio, cattivo , tutto tranne il compilatore ottimizzato. Sta generando rami gonfiati. Ho appena controllato entrambe le risposte, ognuna produce meno istruzioni di assemblaggio e un codice più semplice da mantenere. Se entrambi poteste fornirgli una risposta, potrei darvi una conferma e accettare quella di jonathan. Non ho bisogno di 2 ops di modulo. Entrambi i valori 'a' e' b' sono sotto il nostro controllo. –

risposta

12

Buona domanda! Cosa ne pensi di questo?

c += 3600 * (c < 0); 

Questo è un modo in cui vengono conservati gli slot di predittore di branche.

+3

@abelenky no, i valori di verità sono zero/diverso da zero, ma gli operatori di confronto restituiscono solo zero o uno. – loreb

+1

@loreb ha ragione. – jman

+0

Questa soluzione ha reso la mia giornata! Molto lucido, grazie. –

5

Perché sono voi preoccupati per il ramo? [Ragione spiegato nei commenti alla domanda.]

L'alternativa è qualcosa di simile:

((a - b) + 3600) % 3600 

Questo presuppone a e b sono nella gamma 0..3600 già; se non sono sotto controllo, la soluzione più generale è quella Drew McGowensuggests:

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

Il ramo signorina deve essere molto costoso fare più di tanto il calcolo vale la pena.

4

@skjaidev ha mostrato come eseguirlo senza diramazioni. Ecco come evitare automaticamente moltiplicazione come bene quando int s sono complemento a due:

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

+1 per la bellezza! – jman

7

Cosa questa (supponendo interi a 32-bit):

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

c >> 31 insiemi tutte bit all'originale MSB, che è 1 per i numeri negativi e 0 per gli altri in complemento a 2.

Il numero negativo di spostamento a destra è formalmente definito dall'implementazione in base ai documenti standard C, tuttavia è quasi sempre implementato con la copia MSB (i processori comuni possono farlo in una singola istruzione).

Ciò causerà sicuramente nessuna ramificazione, a differenza di (c < 0) che potrebbe essere implementato con la diramazione in alcuni casi.

+0

Molto bello. Ma si dovrebbe annullare (c >> 31) prima di ANDarlo a 3600. –

+0

@ SáT No, voglio avere una maschera completa se il numero è negativo (MSB è 1). Voglio zero se numero è non negativo. – zch

+0

Uh, è vero, mi dispiace per questo: $. –

0

Quello che vuoi fare è l'aritmetica modulare.La macchina del complemento a 2 fa già questo con la matematica intera. Quindi, mappando i tuoi valori nell'aritmetica del complemento a 2, puoi ottenere l'operazione modolo libera.

Il trucco rappresenta l'angolo come una frazione di 360 gradi tra 0 e 1-epsilon. Certo, quindi i tuoi angoli costanti dovrebbero essere rappresentati allo stesso modo, ma ciò non dovrebbe essere difficile; è solo un po 'di matematica che possiamo nascondere in una funzione di conversione (er, macro).

Il valore in questa idea è che se si aggiungono o si sottraggono angoli, si otterrà un valore di cui si desidera la parte frazione e la cui parte intera si desidera eliminare. Se rappresentiamo la frazione come un numero a virgola fissa a 32 bit con il punto binario a 2^32 (ad esempio, a sinistra di quello che è normalmente considerato un bit di segno), qualsiasi overflow della frazione semplicemente cade dalla parte superiore del Valore a 32 bit gratis. Quindi, esegui tutto il calcolo matematico intero e la rimozione "overflow" avviene gratuitamente.

Così mi piacerebbe riscrivere il codice (conservando l'idea di gradi volte 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 

non ho compilato ed eseguire questo codice.

Le modifiche per rendere questi gradi volte 100 o volte 1 sono piuttosto facili; modificare il angle_scale_factor. Se si dispone di una macchina a 16 bit, passare a 16 bit è altrettanto semplice; se si dispone di 32 bit e si desidera eseguire solo la matematica a 16 bit, sarà necessario mascherare il valore da stampare a 16 bit.

Questa soluzione ha un'altra proprietà piacevole: hai documentato quali variabili sono gli angoli (e hanno rappresentazioni divertenti). Il codice originale di OP li ha semplicemente chiamati ints, ma non è quello che rappresentano; un futuro manutentore sarà sorpreso dal codice originale, specialmente se trova la sottrazione isolata dalle variabili.