整数转字符串的一种快速实现

Last edited by
AI summary
本文介绍了一种将整数快速转换为字符串的方法,涉及正负整数的处理、使用“魔数”优化除法和取模运算的效率。提供了详细的C语言实现代码,包括整数转字符串的函数和主函数示例,强调了输入参数的注意事项和内存管理。
Tags
IntegerToStringConversion
CProgramming
OptimizationTechniques
Last edited time
Sep 23, 2024 02:42 PM

基本思路

  • 若输入为正整数,则直接按10求模,取出十进制中的每个bit,存储到字符串中即可
  • 若输入为负整数,则先转化为正整数,按正整数方法处理,输出时字符串的存储起始地址存储’-’符号即可
因此,负整数的存储将比正整数的存储所需字符串空间的长度要多1个字节。
如果只是上面那么简单,本文就真是画蛇添足。基于此,本文在写程序时考虑到2个问题:
  1. 除10运算的机器运算复杂度高
  1. 模10运算也不是高效的机器运算
大家肯定在很多文章中见过使用位运算求除2k和mod(2k)的方法,但这些方法在除10和mod(10)这根本行不通。
比如计算 x = 100 / 8,只要求x = 100 >> 3即可,可要求x = 100 / 3,或除以5/7之类的数就无能为力了。
本文参考Hacker’s Delight By Henry S. Warren,使用所谓的“魔数”计算,让你领略所谓的“奇技淫巧”。

详细的程序

除3的魔数是0x55555556,除7的魔数是0x92492493,除5的魔数是0x66666667,程序中就使用到除5的魔数用于/10的运算。
因此,求mod(x,10)可以通过x-DIV10(x)*10计算得到。
这里又有个技巧,
关于int32_t int32_to_str(int32_t x, char *str, uint32_t n)函数调用的提示:
  1. n不能大于str分配空间的最大长度k
  1. 若x为正数:则n至少取x十进制格式的bit数+1(+1用于存储字符串结尾字符’\0’)
  1. 若x为正数:则n至少取x十进制格式的bit数+2(+2用于存储’\0’和负数的符号字符’-’)

主函数

可能还会有其它的更新,如float转字符串等的实现(float可以通过先乘以一个系数化为整数后再转字符串)。
Loading...