Come posso implementare l'implicazione logica con bit o altro codice efficiente in C?

Question

Voglio implementare un'operazione logica che funzioni il più efficientemente possibile. Ho bisogno di questa tabella di verità:

p q p → q 
T T  T 
T F  F 
F T  T 
F F  T 

Questo, secondo Wikipedia si chiama "logical implication"

Ho a lungo cercato di capire come fare questo con le operazioni bit per bit in C senza l'utilizzo di condizionali. Forse qualcuno ha qualche idea al riguardo.

Grazie

Answer 1

Cordiali saluti, con gcc-4.3.3:

int foo(int a, int b) { return !a || b; } 
int bar(int a, int b) { return ~a | b; } 

Gives (da -d objdump):

0000000000000000 <foo>: 
    0: 85 ff     test %edi,%edi 
    2: 0f 94 c2    sete %dl 
    5: 85 f6     test %esi,%esi 
    7: 0f 95 c0    setne %al 
    a: 09 d0     or  %edx,%eax 
    c: 83 e0 01    and $0x1,%eax 
    f: c3      retq 

0000000000000010 <bar>: 
    10: f7 d7     not %edi 
    12: 09 fe     or  %edi,%esi 
    14: 89 f0     mov %esi,%eax 
    16: c3      retq 

Quindi, no rami, ma il doppio delle istruzioni.

@ litb: Ok, qui è con _Bool:

0000000000000020 <baz>: 
    20: 40 84 ff    test %dil,%dil 
    23: b8 01 00 00 00   mov $0x1,%eax 
    28: 0f 45 c6    cmovne %esi,%eax 
    2b: c3      retq 

Quindi, utilizzando _Bool invece di int è una buona idea.

Answer 2

!p || q 

è molto veloce. sul serio, non ti preoccupare.

Answer 3

~p | q 

Per la visualizzazione:

perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111' 
1011 

Nel codice stretto, questo dovrebbe essere più veloce "! P || q" perché quest'ultimo ha un ramo, che potrebbe causare una stalla nella CPU dovuto a un errore di predizione del ramo. La versione bitwise è deterministica e, come bonus, può fare 32 volte tanto lavoro in un numero intero a 32 bit rispetto alla versione booleana!

Answer 4

È possibile leggere su deriving boolean expressions from truth Tables (vedere anche canonical form), su come è possibile esprimere qualsiasi tabella di verità come combinazione di primitive o funzioni booleane.

Answer 5

Un'altra soluzione per C booleani (un po 'sporco, ma le opere):

((unsigned int)(p) <= (unsigned int)(q))

Funziona in quanto dallo standard C, 0 rappresenta falso, e qualsiasi altro valore true (1 viene restituito per la vera da operatori booleani, tipo int).

Il "sporco" è che io uso booleani (p e q) come numeri interi, che contraddice alcune politiche di battitura forti (come MISRA), beh, questa è una domanda di ottimizzazione. Si può sempre #define come macro per nascondere le cose sporche.

Per il valore corretto booleano p e q (con rappresentazioni binarie 0 o 1) funziona. Altrimenti T->T potrebbe non riuscire a produrre T se p e q hanno valori arbitrari diversi da zero per rappresentare true.

Se è necessario memorizzare solo il risultato, dal momento che il Pentium II, c'è l'istruzione cmovcc (Spostamento condizionato) (come mostrato nella risposta di Derobert). Per i booleani, tuttavia, anche il 386 aveva un'opzione senza ramo, l'istruzione setcc, che produce 0 o 1 in una posizione di byte di risultato (registro byte o memoria). Puoi anche vederlo nella risposta di Derobert, e questa soluzione compila anche un risultato che coinvolge un setcc (setbe: imposta se inferiore o uguale).

La variante di Derobert e Chris Dolan ~p | q dovrebbe essere la più veloce per l'elaborazione di grandi quantità di dati poiché può elaborare l'implicazione su tutti i bit di p e q singolarmente.

Si noti che nemmeno la soluzione !p || q compila il codice di diramazione su x86: utilizza le istruzioni setcc. Questa è la soluzione migliore se p o q può contenere valori non nulli arbitrari che rappresentano true. Se si utilizza il tipo _Bool, genererà pochissime istruzioni.

ho ottenuto le seguenti figure in cui compilazione per il 86: risultato

__attribute__((fastcall)) int imp1(int a, int b) 
{ 
return ((unsigned int)(a) <= (unsigned int)(b)); 
} 

__attribute__((fastcall)) int imp2(int a, int b) 
{ 
return (!a || b); 
} 

__attribute__((fastcall)) _Bool imp3(_Bool a, _Bool b) 
{ 
return (!a || b); 
} 

__attribute__((fastcall)) int imp4(int a, int b) 
{ 
return (~a | b); 
} 

Assemblea:

00000000 <imp1>: 
    0: 31 c0     xor %eax,%eax 
    2: 39 d1     cmp %edx,%ecx 
    4: 0f 96 c0    setbe %al 
    7: c3      ret  

00000010 <imp2>: 
    10: 85 d2     test %edx,%edx 
    12: 0f 95 c0    setne %al 
    15: 85 c9     test %ecx,%ecx 
    17: 0f 94 c2    sete %dl 
    1a: 09 d0     or  %edx,%eax 
    1c: 0f b6 c0    movzbl %al,%eax 
    1f: c3      ret  

00000020 <imp3>: 
    20: 89 c8     mov %ecx,%eax 
    22: 83 f0 01    xor $0x1,%eax 
    25: 09 d0     or  %edx,%eax 
    27: c3      ret  

00000030 <imp4>: 
    30: 89 d0     mov %edx,%eax 
    32: f7 d1     not %ecx 
    34: 09 c8     or  %ecx,%eax 
    36: c3      ret  

Quando si utilizza il tipo di _Bool, il compilatore sfrutta chiaramente che ha solo due possibili valori (0 per false e 1 per true), producendo un risultato molto simile alla soluzione ~a | b (l'unica differenza è che quest'ultimo esegue un complemento su tutti i bit anziché solo sul bit più basso).

La compilazione per 64 bit fornisce gli stessi risultati.

In ogni caso, è chiaro, il metodo non ha molta importanza dal punto di evitare la produzione di condizionali.