Comment by lifthrasiir

But you can avoid binary search because there are at most one power of tens between 2^k and 2^(k+1). So you can turn it into a lookup table problem.