digit coount

digit10.h

// From Andrei Alexandrescu talk
// https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920/
//   Apache License
//   Version 2.0, January 2004
**
 * Returns the number of digits in the base 10 representation of an
 * uint64_t. Useful for preallocating buffers and such. It's also used
 * internally, see below. Measurements suggest that defining a
 * separate overload for 32-bit integers is not worthwhile.
 */

inline uint32_t digits10(uint64_t v) {
#ifdef __x86_64__

  // For this arch we can get a little help from specialized CPU instructions
  // which can count leading zeroes; 64 minus that is appx. log (base 2).
  // Use that to approximate base-10 digits (log_10) and then adjust if needed.

  // 10^i, defined for i 0 through 19.
  // This is 20 * 8 == 160 bytes, which fits neatly into 5 cache lines
  // (assuming a cache line size of 64).
  alignas(64) static const uint64_t powersOf10[20] = {
      1,
      10,
      100,
      1000,
      10000,
      100000,
      1000000,
      10000000,
      100000000,
      1000000000,
      10000000000,
      100000000000,
      1000000000000,
      10000000000000,
      100000000000000,
      1000000000000000,
      10000000000000000,
      100000000000000000,
      1000000000000000000,
      10000000000000000000UL,
  };

  // "count leading zeroes" operation not valid; for 0; special case this.
  if (UNLIKELY(!v)) {
    return 1;
  }

  // bits is in the ballpark of log_2(v).
  const uint32_t leadingZeroes = __builtin_clzll(v);
  const auto bits = 63 - leadingZeroes;

  // approximate log_10(v) == log_10(2) * bits.
  // Integer magic below: 77/256 is appx. 0.3010 (log_10(2)).
  // The +1 is to make this the ceiling of the log_10 estimate.
  const uint32_t minLength = 1 + ((bits * 77) >> 8);

  // return that log_10 lower bound, plus adjust if input >= 10^(that bound)
  // in case there's a small error and we misjudged length.
  return minLength + uint32_t(v >= powersOf10[minLength]);

#else

  uint32_t result = 1;
  while (true) {
    if (LIKELY(v < 10)) {
      return result;
    }
    if (LIKELY(v < 100)) {
      return result + 1;
    }
    if (LIKELY(v < 1000)) {
      return result + 2;
    }
    if (LIKELY(v < 10000)) {
      return result + 3;
    }
    // Skip ahead by 4 orders of magnitude
    v /= 10000U;
    result += 4;
  }

#endif
}