>>40
それだとnビットに対して平均n回弱ループが回る。
二分探索にすれば平均log n回弱にできるよ。