Jak mogę wdrożyć implikację logiczną z bitowym lub innym efektywnym kodem w C?

Question

Chcę zaimplementować operację logiczną, która działa tak wydajnie, jak to tylko możliwe. Potrzebuję tej tabeli prawdy

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

To, według wikipedii jest nazywany „logical implication”

ja od dawna próbuje dowiedzieć się, jak zrobić to z operacji bitowe w C bez użycia warunkowe. Może ktoś ma jakieś przemyślenia na ten temat.

Dzięki

Answer 1

FYI, z gcc-4.3.3:

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

Daje (od objdump -d):

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 

Tak więc, bez oddziałów, ale dwa razy tyle instrukcjami.

@litb: Ok, tutaj jest z _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 

Więc korzystając _Bool zamiast int jest dobrym pomysłem.

Answer 2

!p || q 

jest mnóstwo szybko. poważnie, nie przejmuj się tym.

Answer 3

~p | q 

do wizualizacji:

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

w obcisłych kodu, to powinno być szybsze niż „P! || q”, ponieważ ten ostatni posiada filię, co może powodować stoisko w CPU ze względu na błąd przewidywania rozgałęzień. Wersja bitowa jest deterministyczna i jako bonus może wykonać 32 razy więcej pracy w 32-bitowej liczbie całkowitej niż wersja boolowska!

Answer 4

Możesz przeczytać na deriving boolean expressions from truth Tables (zobacz także canonical form), w jaki sposób możesz wyrazić dowolną tabelę prawdy jako kombinację boolowskich prymitywów lub funkcji.

Answer 5

Innym rozwiązaniem dla logicznych C (trochę brudny, ale działa):

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

To działa, ponieważ przez standard C, 0 oznacza fałsz, a każda inna wartość true (1 jest zwracana za prawdziwe przez operatorów boolowskich, typ int).

"Nieczystość" polega na tym, że używam booleans (p i q) jako liczb całkowitych, co jest sprzeczne z niektórymi silnymi zasadami pisania (takimi jak MISRA), cóż, jest to pytanie optymalizacyjne. Zawsze możesz #define jako makro, aby ukryć brudne rzeczy.

Dla prawidłowych wartości boolean p i q (mających reprezentacje binarne 0 lub 1) działa. W przeciwnym razie T->T może nie wygenerować T, jeśli p i q ma arbitralne niezerowe wartości reprezentujące wartość true.

Jeśli chcesz przechowywać wynik tylko, ponieważ Pentium II, istnieje instrukcja cmovcc (ruch warunkowy) (jak pokazano w odpowiedzi Derobert'a). Dla bajtanów, nawet 386 miało opcję bez gałęzi, czyli instrukcję setcc, która generuje 0 lub 1 w wynikowej lokalizacji bajtów (rejestr bajtów lub pamięć). Widać to również w odpowiedzi Derobert'a, a to rozwiązanie kompiluje się także z wynikiem obejmującym setcc (setbe: Ustawić poniżej lub równy).

Wersja Derobert i Chris Dolan ~p | q powinna być najszybsza w przetwarzaniu dużych ilości danych, ponieważ może przetwarzać implikacje na wszystkich bitach pojedynczych p i q osobno.

Należy zauważyć, że nawet rozwiązanie nie kompiluje się do kodu rozgałęzionego na x86: używa instrukcji setcc. To najlepsze rozwiązanie, jeśli p lub q może zawierać dowolne niezerowe wartości reprezentujące wartość true. Jeśli użyjesz typu _Bool, wygeneruje on bardzo mało instrukcji.

Mam następujące dane przy zestawianiu dla x86: wynik

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

montaż:

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  

Przy użyciu typu _Bool, kompilator wyraźnie wykorzystujący że ma tylko dwie możliwe wartości (0 dla false i 1 dla true), dając bardzo podobny wynik do rozwiązania ~a | b (jedyną różnicą jest to, że ten ostatni wykonuje dopełnienie wszystkich bitów zamiast tylko najniższy bit).

Kompilacja dla 64 bitów daje prawie takie same wyniki.

W każdym razie jasne jest, że metoda nie ma znaczenia z punktu widzenia unikania warunków warunkowych produkcji.