Come avrei potuto implementare implicazione logica con bit a bit o altro codice efficiente in C?

Question

Voglio realizzare un'operazione logica che funziona il più efficiente possibile. Ho bisogno di questa tavola di verità:

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

Questo, secondo Wikipedia si chiama " logica implicazione "

Sono stati a lungo cercando di capire come fare questo con le operazioni bit per bit in C senza l'utilizzo di condizionali. Forse qualcuno ha alcuni pensieri su di esso.

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, senza rami, ma il doppio delle istruzioni.

E ancora meglio, con _Bool (grazie @ litb):

_Bool baz(_Bool a, _Bool b) { return !a || b; }

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 int invece di _Bool: è una buona idea.

Dal momento che sto aggiornando oggi, ho confermato gcc 8.2.0 produce simile, anche se non identici, i risultati per <=>

0000000000000020 <baz>:
  20:   83 f7 01                xor    $0x1,%edi
  23:   89 f8                   mov    %edi,%eax
  25:   09 f0                   or     %esi,%eax
  27:   c3                      retq   

Answer 2

~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 causa di un errore di predizione ramo. La versione bit a bit è deterministico e, come bonus, può fare 32 volte tanto lavoro in un intero a 32 bit rispetto alla versione booleano!

Answer 3

!p || q

è molto veloce. sul serio, non ti preoccupare.

Answer 4

Si può leggere su derivante espressioni booleane dalla verità Tabelle (anche vedi forma canonica ), su come è possibile esprimere alcuna tabella di verità come una combinazione di primitive booleane o funzioni.

Answer 5

Un'altra soluzione per C booleani (un po 'sporco, ma 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 vera da parte degli operatori booleani, int tipo).

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 una macro per nascondere la roba sporca.

Per una corretta booleano T->T e T (aventi una cmovcc o setcc rappresentazioni binarie) funziona. Altrimenti setbe potrebbe non riuscire a produrre ~p | q se !p || q e _Bool hanno valori diversi da zero arbitrari per la rappresentazione vera.

Se avete bisogno di memorizzare il risultato, in quanto il Pentium II, c'è la (Condizionale Move) istruzioni ~a | b (come indicato nella risposta di Derobert). Per booleani, tuttavia anche il 386 aveva un'opzione branchless, l'istruzione <=>, che produce <=> o <=> in una posizione risultato byte (registro byte o memoria). Si può anche vedere che in risposta di Derobert, e questa soluzione compila anche ad un risultato che coinvolge un <=>. (<=>: Imposta se inferiore o uguale)

Derobert e Chris Dolan <=> variante dovrebbe essere il più veloce per l'elaborazione di grandi quantità di dati poiché può elaborare l'implicazione su tutti i bit di <=> e <=> individualmente.

Si noti che nemmeno la soluzione <=> compila per ramificazione codice a 86: utilizza <=> istruzioni. Questa è la soluzione migliore se <=> o <=> può contenere valori diversi da zero arbitrari che rappresentano vere. Se si utilizza il tipo <=>, genererà pochissime istruzioni.

ho ottenuto le seguenti figure durante la compilazione per il 86:

__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);
}

Risultati Assembly:

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, il compilatore sfrutta chiaramente che ha solo due valori possibili (<=> per falso e <=> per vero), producendo un risultato molto simile alla soluzione <=> (l'unica differenza che quest'ultimo svolge un complemento su tutti i bit invece che solo il bit più basso).

compilazione per 64 bit dà quasi gli stessi risultati.

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