私が思いつくことができる最高のものはこれです
char a, b, c;
std::cin >> a >> b >> c;
if (((b-a) | (c-a)) & 0x80) {
// a > b || a > c
}
これによりgcc -O2
、条件分岐が1つだけ生成されます
40072e: 29 c8 sub %ecx,%eax
400730: 29 ca sub %ecx,%edx
400732: 09 d0 or %edx,%eax
400734: a8 80 test $0x80,%al
400736: 74 17 je 40074f <main+0x3f>
これは、入力値の制約を利用します。値が 26 を超えることはできないため、 から減算a
するb
と負の値になりa > b
ます。2 の補数7
では、その場合にビットが設定されることがわかっていc
ます。次に、ビットが かどうかを示すように両方をORし、最後に 0x80 を使用してANDでビットを検査し、それで分岐します。7
a > b || a > c
7
更新:好奇心から、これをコーディングする 4 つの異なる方法を計りました。テスト データを生成するために、単純な線形合同疑似乱数ジェネレーターを使用しました。1億回の繰り返しのループで時間を計りました。簡単にするために、条件が true の場合はカウンターに 5 を追加し、それ以外の場合は何もしないと仮定しました。私は使用中の最適化レベルで使用g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)
して時間を計りました。Intel Xeon X5570 @ 2.93GHz
-O2
コードは次のとおりです (条件付きバリアントの 1 つを除いてすべてコメントアウトします)。
#include <iostream>
unsigned myrand() {
static unsigned x = 1;
return (x = x * 1664525 + 1013904223);
}
int main() {
size_t count = 0;
for(size_t i=0; i<100000000; ++i ) {
int a = 1 + myrand() % 26;
int b = 1 + myrand() % 26;
int c = 1 + myrand() % 26;
count += 5 & (((b-a) | (c-a)) >> 31); // 0.635 sec
//if (((b-a) | (c-a)) & 0x80) count += 5; // 0.660 sec
//if (a > std::max(b,c)) count += 5; // 0.677 sec
//if ( a > b || a > c) count += 5; // 1.164 sec
}
std::cout << count << std::endl;
return 0;
}
最も速いのは、私の回答の提案に対する変更です。ここでは、符号拡張を使用して、条件が true または false であるかどうかに応じて321s
または 32のいずれかであるマスクを生成し、それを使用して追加されるものをマスクして、追加するようにします。 5 または 0。このバリエーションには分岐がありません。時刻は各行のコメントにあります。最も遅いのは元の式でした。0s
5
( a > b || a > c)