Redis优秀代码分享[0]-ll2string

转自https://zhuanlan.zhihu.com/p/27795562

 

话不多说，先上代码，代码位置：redis/src/util.c

int ll2string(char* dst, size_t dstlen, long long svalue) { static const char digits[201] = "0001020304050607080910111213141516171819" "2021222324252627282930313233343536373839" "4041424344454647484950515253545556575859" "6061626364656667686970717273747576777879" "8081828384858687888990919293949596979899"; int negative; unsigned long long value; if (svalue < 0) { if (svalue != LLONG_MIN) { value = -svalue; } else { value = ((unsigned long long) LLONG_MAX)+1; } negative = 1; } else { value = svalue; negative = 0; } uint32_t const length = digits10(value)+negative; if (length >= dstlen) return 0; uint32_t next = length; dst[next] = '\0'; next--; while (value >= 100) { int const i = (value % 100) * 2; value /= 100; dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; next -= 2; } if (value < 10) { dst[next] = '0' + (uint32_t) value; } else { int i = (uint32_t) value * 2; dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; } if (negative) dst[0] = '-'; return length; }

如果你已经看明白了，就请默默地关掉窗口吧。

如果你感觉有点懵的话，就继续往下看吧。

 

这个函数的作用从方法名就能看出是将一个long long类型数字转换成字符串。

 

先跳出这段代码，如果按正常思路来实现，大部分人的都会想到循环做再/10，然后将依次拿到的数倒序组成一个字符串。

其实上面的代码跟这种思路是基本是相通的，不同的地方在于它是每次0再/100，这样的好处可以将除法运算减少一半，算法效率得到了很大的提升，据说提升了40%左右（数据来源小道消息，我这里没有进行专门的测试）。

 

其实，上面的代码并不复杂，只需要搞明白digits这个静态常量数组是什么就可以瞬间看破。

digits数据就是对100取模的所有值组成的字符串。

就是00,01,02,03,04,05,06,07,08,09,10,11,12,13,14.....97,98,99.

// 将一个ll类型的数字转换成字符串表示 int ll2string(char* dst, size_t dstlen, long long svalue) { // 从00到99的字符数组 static const char digits[201] = "0001020304050607080910111213141516171819" "2021222324252627282930313233343536373839" "4041424344454647484950515253545556575859" "6061626364656667686970717273747576777879" "8081828384858687888990919293949596979899"; int negative; // 之所以将svalue换成value表示，是为了解决当svalue为LLONG_MIN的情况转成正数时溢出问题 unsigned long long value; // 判断是否是负数，若是负数则标记，并转成正数表示 if (svalue < 0) { if (svalue != LLONG_MIN) { value = -svalue; } else { value = ((unsigned long long) LLONG_MAX)+1; } negative = 1; } else { value = svalue; negative = 0; } // 长度检查 uint32_t const length = digits10(value)+negative; if (length >= dstlen) return 0; uint32_t next = length; dst[next] = '\0'; next--; //每次取100的余数，然后参照digits找到对应的字符赋值 while (value >= 100) { // 因为都是2位，所以乘以2可以直接找到下标 int const i = (value % 100) * 2; value /= 100; // 相邻的两位代表取模后对应的字符 dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; next -= 2; } // 处理最后剩下的数字 if (value < 10) { dst[next] = '0' + (uint32_t) value; } else { int i = (uint32_t) value * 2; dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; } // 若为负数，在前头加负号 if (negative) dst[0] = '-'; return length; }

看明白了吧？看不明白就多看几遍，再看不明白就关掉窗口过两天再来看几遍。

 

作为一个java开发人员，出于好奇，看完redis的实现，我又去看了下jdk中是如何实现的数字转字符串的Long.toString()，发现其实两者思路基本上是一致的，只不过JDK中用了更多的小技巧优化，

当遇到最小值时，直接返回固定字符串，不需要运算，也不需要考虑边界用r = (int)(i - ((q << 6) + (q << 5) + (q << 2)));来代替取模运算对于大数据和小数据区别对待，采用不同的方案缺点在于采用了多个数组，有DigitTens，DigitOnes，digits，相对来说比较繁琐而且不好理解，可以优化为参考redis中的用法。

详细代码如下：

public static String toString(long i) { if (i == Long.MIN_VALUE) return "-9223372036854775808"; int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i); char[] buf = new char[size]; getChars(i, size, buf); return new String(buf, true); } static void getChars(long i, int index, char[] buf) { long q; int r; int charPos = index; char sign = 0; if (i < 0) { sign = '-'; i = -i; } // Get 2 digits/iteration using longs until quotient fits into an int while (i > Integer.MAX_VALUE) { q = i / 100; // really: r = i - (q * 100); r = (int)(i - ((q << 6) + (q << 5) + (q << 2))); i = q; buf[--charPos] = Integer.DigitOnes[r]; buf[--charPos] = Integer.DigitTens[r]; } // Get 2 digits/iteration using ints int q2; int i2 = (int)i; while (i2 >= 65536) { q2 = i2 / 100; // really: r = i2 - (q * 100); r = i2 - ((q2 << 6) + (q2 << 5) + (q2 << 2)); i2 = q2; buf[--charPos] = Integer.DigitOnes[r]; buf[--charPos] = Integer.DigitTens[r]; } // Fall thru to fast mode for smaller numbers // assert(i2 <= 65536, i2); for (;;) { q2 = (i2 * 52429) >>> (16+3); r = i2 - ((q2 << 3) + (q2 << 1)); // r = i2-(q2*10) ... buf[--charPos] = Integer.digits[r]; i2 = q2; if (i2 == 0) break; } if (sign != 0) { buf[--charPos] = sign; } } final static char [] DigitTens = { '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', '4', '4', '4', '4', '4', '4', '4', '4', '4', '4', '5', '5', '5', '5', '5', '5', '5', '5', '5', '5', '6', '6', '6', '6', '6', '6', '6', '6', '6', '6', '7', '7', '7', '7', '7', '7', '7', '7', '7', '7', '8', '8', '8', '8', '8', '8', '8', '8', '8', '8', '9', '9', '9', '9', '9', '9', '9', '9', '9', '9', } ; final static char [] DigitOnes = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', } ; final static char[] digits = { '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' , 'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h' , 'i' , 'j' , 'k' , 'l' , 'm' , 'n' , 'o' , 'p' , 'q' , 'r' , 's' , 't' , 'u' , 'v' , 'w' , 'x' , 'y' , 'z' };