[解決済み】ある整数が、値の集合がわかっている2つの整数（含む）の間にあるかどうかを判断する最速の方法

質問

よりも高速な方法はありますか？ x >= start && x <= end C や C++ で、ある整数が 2 つの整数の間にあるかどうかを調べるには？

アップデイト : 私の特定のプラットフォームはiOSです。これは、ピクセルを与えられた正方形の中の円形に制限するボックスブラー機能の一部です。

アップデイト : を試した結果 回答 を使うよりも、1行のコードで1桁のスピードアップを達成しました。 x >= start && x <= end の方法です。

アップデイト : XCodeからアセンブラを使用した後と前のコードです。

新しい方法

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

OLD WAY

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

分岐を減らしたり削除したりすることで、これほどまでに劇的なスピードアップを実現できるのは非常に驚きです。

どのように解決するのか？

昔から、比較・分岐を1つだけにして行うトリックがあります。本当に速度が向上するかどうかは疑問が残りますし、仮に向上したとしても、気づくことも気にすることもないでしょうが、2つの比較からしか始めない場合、大きく向上する可能性はかなり低いのです。コードは以下のような感じです。

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

一般的な最新のコンピュータ（つまり2進数の補数を使っているもの）では、符号なしへの変換は本当に無意味で、同じビットをどう見るかが変わるだけです。

典型的なケースでは、事前に計算することができることに注意してください。 upper-lower ループの外側にあるため、通常、大きな時間にはなりません。分岐命令の数を減らすと同時に、（一般に）分岐予測も改善されます。この場合、数値が範囲の下端以下でも上端以上でも同じ分岐が行われます。

この仕組みはとてもシンプルで、「負の数は符号なし数として見た場合、正の数としてスタートしたものよりも大きくなる」というものです。

実際には、この方法は、以下のように変換されます。 number と原点までの区間をチェックし、その区間が number が区間内にある場合 [0, D] ここで D = upper - lower . もし number を下限値以下にする。 ネガティブ で、上限を超えたら よりも大きい D .