I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but…
Given a number represented in binary, it's fairly easy to derive a decimal representation using integer division and remainders to extract digits in reverse order. You can then simply count how many digits you extracted.
However, I wondered about calculating an exact number of decimal digits more efficiently by avoiding calculating the actual digits.
At first sight this is easy. First, count the binary digits needed (ie determine the position of the highest set bit). Many processors have an operation to do this directly, and there are bit-fiddling algorithms to do it in O(log n) time where n varies with the width of a machine register. In an arbitrary position integer, you normally know how many machine words you have, so you can usually jump directly to the most significant word.
Once you know the size in binary digits, you can scale by $\log 2 \over \log 10$ to get the number of decimal digits. Sort of.
The problem is that this scale factor is (I think) an irrational number. If you have a maximum number of digits you need to worry about, you can use a rational approximation and you only need to worry about getting the rounding right.
The question is, therefore – is there a way to determine this number of decimal digits efficiently and precisely for numbers of any size? Is there (for example) a completely different approach to the calculation that I haven't thought of?
Best Answer
I would post this as a comment if I could, because it seems too simple for an answer. You already said that you can find the highest bit with a single instruction (if the number fits into a register). For every result $r$ you get (that is, your number is between $2^r$ and $2^{r+1}-1$), there are only two possible numbers $k$ and $k+1$ of decimal digits. So you could just use $r$ as an index into a lookup table that stores both $k$ and $10^k$, and output $k$ if your number is less than $10^k$, or $k+1$ otherwise.