I think you can do this by representing numbers as A * 10^B, where both A and B fit in the lower half of a 64-bit int (so multiplication is easy) and B is only needed some of the time, and then only correct up to an unknown offset.
Write 2^m - 2^n = 2^n * (1 + 2 + 4 + .. 2^(m-n-1)) and do the calculation in two stages:
1) calculate 2^n by repeated squaring
2) Accumulate 2^n + 2^(n+1) + .. 2^(m-1)
If m is much larger than n then just use stage 1 to compute 2^m.
For the first stage you don't need to keep track of powers of 10 at all - just divide A through by some power of 10 to keep it just below 2^32, to make sure multiplication doesn't overflow.
For the second stage, you need to know the relative size of 2^k and 2^(k-1)+2^(k-2)... - but these are almost the same size, so a perfectly ordinary integer will keep track of the difference between the number of powers of 10 used to scale 2^k and those used to scale 2^(k-1)+...
At the end you have roughly 32 bits of precision of the answer you need, up to multiplication by an unknown power of 10. This should be enough to work out the 3 most significant digits of the answer, unless you are very unlucky and it is very close to the gap between 9999... and 10000...