Skip to content

Latest commit

 

History

History
148 lines (113 loc) · 3.85 KB

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

File metadata and controls

148 lines (113 loc) · 3.85 KB
Raw

基本思路

  • 若输入为正整数，则直接按10求模，取出十进制中的每个bit，存储到字符串中即可
  • 若输入为负整数，则先转化为正整数，按正整数方法处理，输出时字符串的存储起始地址存储'-'符号即可

因此，负整数的存储将比正整数的存储所需字符串空间的长度要多1个字节。

如果只是上面那么简单，本文就真是画蛇添足。基于此，本文在写程序时考虑到2个问题：

  1. 除10运算的机器运算复杂度高
  2. 模10运算也不是高效的机器运算

大家肯定在很多文章中见过使用位运算求除2^k和mod(2^k)的方法，但这些方法在除10和mod(10)这根本行不通。

比如计算 x = 100 / 8，只要求x = 100 >> 3即可，可要求x = 100 / 3，或除以5/7之类的数就无能为力了。

本文参考Hacker's Delight By Henry S. Warren，使用所谓的“魔数”计算，让你领略所谓的“奇技淫巧”。

详细的程序

/*
 * FileName : format2str.c
 * Author   : xiahouzuoxin @163.com
 * Version  : v1.0
 * Date     : 2014/4/8 11:08:40
 * Brief    : 
 * 
 * Copyright (C) MICL,USTB
 */
#include "format2str.h" 

/*
 * @brief   
 *   == Use Example
 *   str = (char *)malloc(k*sizeof(char));
 *   if (str) {
 *      int32_to_str(x, str, n);  // n <= k
 *   }
 *   == Be careful of choose the input n
 * @inputs  
 *   x - Interger numbers
 *   n - 
 *      x>0, n >= bit of x in decimal format + 1
 *      x<0, n >= bit of x in decimal format + 2
 * @outputs 
 *   str - Converted string
 * @retval  
 *   If success return 0, else others.
 */
int32_t int32_to_str(int32_t x, char *str, uint32_t n)
{
    uint32_t remain = 0;
    uint32_t div_x  = 0;
    uint32_t le_zero= 0;
    
    if (x<0) {
        x = -x;
        le_zero = 1;
    }

    str[--n] = '\0';
    while ((x > 0) && (n>0)) {
        div_x  = DIV10(x);
        remain = x - ((div_x<<3)+(div_x<<1));  // x - div_x * 10
        x      = div_x;

        str[--n] = remain + '0';
    }
    while (n > 1) {
        str[--n] = '0';
    } 
    if (le_zero > 0) {
        str[--n] = '-';
    } else {
        str[--n] = '0';
    }

    return (n);
}
/*
 * FileName : format2str.h
 * Author   : xiahouzuoxin @163.com
 * Version  : v1.0
 * Date     : 2014/4/9 10:15:09
 * Brief    : 
 * 
 * Copyright (C) MICL,USTB
 */
#ifndef _FORMAT2STR_H
#define _FORMAT2STR_H

#ifdef __cplusplus
extern "C" {
#endif


#include <stdint.h>

/* 
 * Magic Number 0x66666667 
 * Refrence to <<Hacker's Delight>> By Henry S. Warren
 */
#define DIV5(x)        (((int64_t)x*0x66666667L) >> 33)
#define DIV10(x)       (((int64_t)x*0x66666667L) >> 34)

extern int32_t int32_to_str(int32_t x, char *str, uint32_t n);

#ifdef __cplusplus
}
#endif
#endif

除3的魔数是0x55555556，除7的魔数是0x92492493，除5的魔数是0x66666667，程序中就使用到除5的魔数用于/10的运算。

因此，求mod(x,10)可以通过x-DIV10(x)*10计算得到。

这里又有个技巧，

x*10 = x*(8+2) = x*8 + x*2 = x<<3 + x<<1

关于int32_t int32_to_str(int32_t x, char *str, uint32_t n)函数调用的提示：

  1. n不能大于str分配空间的最大长度k
  2. 若x为正数：则n至少取x十进制格式的bit数+1（+1用于存储字符串结尾字符'\0'）
  3. 若x为正数：则n至少取x十进制格式的bit数+2（+2用于存储'\0'和负数的符号字符'-'）

源代码

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