>>321
x が 0 〜 2^n - 1 の一様乱数なら半分の確率で最上位ビットが１だから、上位ビットからテストした方が速いかもしれない。

各ビットが独立しているようなデータなら、真中のビットから二分探索した方が速いかもしれない。