数字转字符串

先看数字转字符串里面算多少位数的/**

 * 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).

  static const uint64_t powersOf10[20] FOLLY_ALIGNED(64) = {

      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 uint8_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) (UNLIKELY (v >= powersOf10[minLength]));

#else

  uint32_t result = 1;

  for (;;) {

    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

}

下面那个for loop多友好，上面x86那段是什么鬼！builtin_clzll 是gcc里面的一个函数，具体定义看这里Other Builtins 简单来说就是算有几个开头的0的。这里面的0是2进制的0,所以63-leading zeros就是说二进制里面有几位数。  const uint32_t minLength = 1 + ((bits * 77) >> 8);

这个就是亮点了。高中数学没学好的话，这里强调一下log_10(v) =log_10(2) * log_2(v) (The Change-of-Base Formula)>> 8 就是处以256bits在这里已经是log(2)了+1是因为 0.3010略小于77/256我们继续瞎，现在开始正式转换/**

 * Copies the ASCII base 10 representation of v into buffer and

 * returns the number of bytes written. Does NOT append a \0. Assumes

 * the buffer points to digits10(v) bytes of valid memory. Note that

 * uint64 needs at most 20 bytes, uint32_t needs at most 10 bytes,

 * uint16_t needs at most 5 bytes, and so on. Measurements suggest

 * that defining a separate overload for 32-bit integers is not

 * worthwhile.

 *

 * This primitive is unsafe because it makes the size assumption and

 * because it does not add a terminating \0.

 */

inline uint32_t uint64ToBufferUnsafe(uint64_t v, char *const buffer) {

  auto const result = digits10(v);

  // WARNING: using size_t or pointer arithmetic for pos slows down

  // the loop below 20x. This is because several 32-bit ops can be

  // done in parallel, but only fewer 64-bit ones.

  uint32_t pos = result - 1;

  while (v >= 10) {

    // Keep these together so a peephole optimization "sees" them and

    // computes them in one shot.

    auto const q = v / 10;

    auto const r = static_cast<uint32_t>(v % 10);

    buffer[pos--] = '0' + r;

    v = q;

  }

  // Last digit is trivial to handle

  buffer[pos] = static_cast<uint32_t>(v) + '0';

  return result;

}