What is the math for * 1233 >> 12 in this code, counting decimal digits

Question

I'm a little confused how this short function from the C ++ library {fmt} works.

inline std::uint32_t digits10_clz(std::uint32_t n) { std::uint32_t t = (32 - __builtin_clz(n | 1)) * 1233 >> 12; return t - (n < powers_of_10_u32[t]) + 1; } 

I understand the logic that you can approximate log10 with log2(__builtin_clz) and that you need to adjust the exact value, but multiplication is a mystery to me.

Answer 1

Recall the formula for changing the base of the logarithm from b to d is

log _d x = log _b x / log _b d

In our case, b is 2 (binary), and d is 10 (decimal). Therefore, you need to divide by log ₂ 10, which is the same as multiplying by 1 / log ₂ 10, i.e. by 0.30102999566.

Now recall that a shift of 12 coincides with a division of 2 ¹² which is 4096. Dividing 1233 by 4096 gives 0.30102539062, which is a pretty good approximation for the denominator in the formula for changing the base.