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

Question

I am a bit confused how this short function from the C++ {fmt} library 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 the log10 using log2(__builtin_clz) and that you need to adjust for exact value, but the multiplication is a mystery to me.

Answer 1

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

log_dx = log_bx / log_bd

In our case, b is 2 (binary), and d is 10 (decimal). Hence, 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 shifting by 12 is the same as dividing by 2¹², which is 4096. Dividing 1233 by 4096 yields 0.30102539062, which is a pretty good approximation for the denominator in the base change formula.