できるだけ効率的に機能する論理演算を実装したいと考えています。この真理値表が必要です:
p q p → q
T T T
T F F
F T T
F F T
これは、ウィキペディアによると「論理的含意」と呼ばれています
私は長い間、条件を使用せずに C のビット演算でこれを行う方法を理解しようと試みてきました。たぶん、誰かがそれについていくつかの考えを持っています。
ありがとう
Álvaro
質問する
11142 次
5 に答える
12
!p || q
かなり速いです。真剣に、心配しないでください。
于 2009-03-21T02:59:33.110 に答える
11
~p | q
視覚化の場合:
perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111'
1011
タイトなコードでは、これは "!p || q" よりも高速になるはずです。後者には分岐があり、分岐予測エラーにより CPU でストールが発生する可能性があるためです。ビット単位バージョンは決定論的であり、おまけとして、32 ビット整数でブール型バージョンよりも 32 倍多くの作業を行うことができます!
于 2009-03-21T03:00:25.557 に答える
9
参考までに、gcc-4.3.3 の場合:
int foo(int a, int b) { return !a || b; }
int bar(int a, int b) { return ~a | b; }
与えます (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
したがって、分岐はありませんが、命令は 2 倍になります。
さらに良いことに、_Bool(@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
_Boolそのため、の代わりに使用intすることをお勧めします。
今日更新しているので、gcc 8.2.0 が同様の結果を生成することを確認しましたが、同一ではありません。_Bool:
0000000000000020 <baz>:
20: 83 f7 01 xor $0x1,%edi
23: 89 f8 mov %edi,%eax
25: 09 f0 or %esi,%eax
27: c3 retq
于 2009-03-21T03:52:28.367 に答える
4
ブール値のプリミティブまたは関数の組み合わせとして任意の真理値表を表現する方法について、真理値表からのブール式の導出について読むことができます(正規形も参照してください)。
于 2009-03-21T07:05:04.410 に答える
1
Cブール値の別の解決策（少し汚いですが、機能します）：
((unsigned int)(p) <= (unsigned int)(q))
これは、C 標準で0は false を表し、その他の値は true であるため機能します (1ブール演算子inttype によって true に対して返されます)。
「汚れ」は、ブール値 (pおよびq) を整数として使用することです。これは、いくつかの強力な型指定ポリシー (MISRA など) と矛盾します。まあ、これは最適化の問題です。#define汚れたものを隠すために、常にマクロとして使用できます。
適切なブール値pとq（0または1バイナリ表現のいずれかを持つ）場合、それは機能します。そうしないと、 ifのT->T生成に失敗し、真を表す任意のゼロ以外の値を持つ可能性があります。Tpq
Pentium II以降、結果のみを保存する必要がある場合は、cmovcc（条件付き移動）命令があります（Derobertの回答に示されているように）。ただし、ブール値の場合、386 にも分岐なしのオプションがありました。これは、または結果のバイト位置 (バイト レジスタまたはメモリ)setccを生成する命令です。また、Derobert の回答でも確認できます。このソリューションは、( : Set if below or equal) を含む結果にもコンパイルされます。01setccsetbe
Derobert と Chris Dolan のバリアントは、すべてのビットの含意を個別~p | qに処理できるため、大量のデータを処理するのに最も高速であるはずです。pq
ソリューションでさえ、!p || qx86 では分岐コードにコンパイルされないことに注意してsetccください。命令を使用します。true を表すゼロ以外の任意の値が含まれている場合、pまたは含まれる可能性がある場合は、これが最適なソリューションです。qタイプを使用する_Boolと、生成される命令はほとんどありません。
x86用にコンパイルすると、次の図が得られました。
__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);
}
組み立て結果:
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
型を使用する場合_Bool、コンパイラは、可能な値が 2 つ ( 0false と1true の場合) しかないことを明確に利用し、ソリューションと非常によく似た結果を生成し~a | bます (唯一の違いは、後者がビットだけではなくすべてのビットの補数を実行することです)。最下位ビット)。
64 ビット用にコンパイルすると、ほぼ同じ結果が得られます。
いずれにせよ、条件の生成を回避するという点から言えば、メソッドはそれほど重要ではないことは明らかです。
于 2016-08-16T11:51:27.130 に答える