转载

Yedis源码解析之itoa实现

写在最前

Yedis 是一款高性能的nosql数据库，旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里，Python客户端请点击这里

提出问题

如何用C/C++实现正确的、可移植的、高效的、对所有整数都work的itoa函数？

原型如下

int itoa(char *buffer, int64_t value);

将value转为字符串后存在buffer中，返回字符串的长度。

分析问题

这还不容易么？很容易写出这样的代码：

int itoa(char *buffer, int64_t value) {   char *p = buffer;   int64_t tmp = value;   do {     *p = tmp % 10 + '0';     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; }

这个实现，有什么问题？

问题出在第6、7行。

举个例子，请问，-9/4结果是多少？

因为 -9 = (-2) * 4 + (-1) 因此结果为-2，同时 -9 % 4 = -1

但是！

因为 -9 =(-3)* 4 + 3 因此结果为-3，同时 -9 % 4 = 3

哪个结果是对的？

C++98和C++03标准并没有对被除数和除数不都为正数时的情形进行明确的说明，语言只保证:

如果 a = br + q

那么 a / b = r 且 a % b = q

因此，当a和b都是正数时，语言保证结果是正的；否则，结果是实现相关的。

因此第6、7行的结果是未定义的，是很不可移植的。

有些人说，这还不容易吗？把负数都搞成正数，用它的绝对值来计算，不就行了吗？于是很容易写出这样的代码：

int itoa(char *buffer, int64_t value) {   char *p = buffer;   int64_t tmp = value < 0 ? -value : value;   do {     *p = tmp % 10 + '0';     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; }

还是有问题，注意第4行。我们知道，对于有符号整数，它的最大值和最小值是不对称的，绝对值差1。其中，64位有符号整数的范围为[-9223372036854775808, 9223372036854775807]

因此，在第4行，如果value是INT64_MIN，对它求绝对值-value的结果其实已经超出了64位有符号整数可以表示的范围，这里已经溢出了！！！

哦哦，这好办，对INT64_MIN单独处理行不行？

行，但是代码会非常不优雅了。

解决问题

Yedis中实现了itoa，代码在 src/server/yedis_order.cpp

YEDIS_MUST_INLINE int64_t int2char(char *buffer, int64_t value) {   static const char offset[19] = {'9','8','7','6','5','4','3','2','1','0','1','2','3','4','5','6','7','8','9'};   static const char *digit = offset + 9;   char *p = buffer;   int64_t tmp = value;   do {     *p = *(digit + tmp % 10);     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; }