将整数转换为字符串而无需访问库
我最近阅读了一份面试问题样本:
编写一个函数将整数转换为字符串。 假设您无权访问库函数,即itoa()等…
你会怎么做?
快速刺伤:(编辑处理负数)
int n = INT_MIN; char buffer[50]; int i = 0; bool isNeg = n<0; unsigned int n1 = isNeg ? -n : n; while(n1!=0) { buffer[i++] = n1%10+'0'; n1=n1/10; } if(isNeg) buffer[i++] = '-'; buffer[i] = '\0'; for(int t = 0; t < i/2; t++) { buffer[t] ^= buffer[it-1]; buffer[it-1] ^= buffer[t]; buffer[t] ^= buffer[it-1]; } if(n == 0) { buffer[0] = '0'; buffer[1] = '\0'; } printf(buffer);
该算法很容易用英语看到。
给定一个整数,例如123
-
除以10 => 123/10。 屈服,结果= 12,余数= 3
-
添加30h到3并推入堆栈(添加30h将3转换为ASCII表示)
-
重复步骤1直到结果<10
-
添加30h到结果并存储在堆栈上
-
堆栈按|的顺序包含数字 1 | 2 | 3 | …
在web上查看itoa实现将为您提供很好的示例。 这是一个,避免在结束时反转字符串。 它依赖于静态缓冲区,因此如果将其重用于不同的值,请务必小心。
char* itoa(int val, int base){ static char buf[32] = {0}; int i = 30; for(; val && i ; --i, val /= base) buf[i] = "0123456789abcdef"[val % base]; return &buf[i+1]; }
假设它是十进制的,那么像这样:
int num = ...; char res[MaxDigitCount]; int len = 0; for(; num > 0; ++len) { res[len] = num%10+'0'; num/=10; } res[len] = 0; //null-terminating //now we need to reverse res for(int i = 0; i < len/2; ++i) { char c = res[i]; res[i] = res[len-i-1]; res[len-i-1] = c; }
我要记住,所有数字字符在ASCII字符集中的顺序递增,并且它们之间没有其他字符。
我也会反复使用/
和%
运算符。
如何获取字符串的内存将取决于您没有给出的信息。
itoa()
函数的实现似乎是一项简单的任务,但实际上您必须处理与您的确切需求相关的许多方面。 我想在访谈中你应该提供一些关于你的解决方案的细节,而不是复制一个可以在谷歌找到的解决方案( http://en.wikipedia.org/wiki/Itoa )
以下是您可能想要问自己或面试官的一些问题:
- 应该在哪里找到字符串(malloced?由用户传递?静态变量?)
- 我应该支持签名号码吗?
- 我应该支持浮点吗?
- 我应该支持其他基地而不是10吗?
- 我们需要任何输入检查吗?
- 输出字符串是否限制在legth?
等等。
这是一个简单的方法,但我怀疑如果你在没有理解和解释它的情况下将其转换为原样,你的老师会知道你刚刚复制了网:
char *pru(unsigned x, char *eob) { do { *--eob = x%10; } while (x/=10); return eob; } char *pri(int x, char *eob) { eob = fmtu(x<0?-x:x, eob); if (x<0) *--eob='-'; return eob; }
可以进行各种改进,特别是如果您希望有效地支持大于intmax_t
的大于整数的整数。 我会留给你来弄清楚这些函数的调用方式。
比解决方案稍长:
static char* itoa(int n, char s[]) { int i, sign; if ((sign = n) < 0) n = -n; i = 0; do { s[i++] = n % 10 + '0'; } while ((n /= 10) > 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); return s; }
相反:
int strlen(const char* str) { int i = 0; while (str != '\0') { i++; str++; } return i; } static void reverse(char s[]) { int i, j; char c; for (i = 0, j = strlen(s)-1; i
虽然davolno这里的决定很长,但对初学者来说是一些有用的function。 我希望你会有所帮助。
越快越好?
unsigned int findDigits(long long x) { int i = 1; while ((x /= 10) && ++i); return i; } // return the number of digits in x. unsigned int digits(long long x) { x < 0 ? x = -x : 0; return x < 10 ? 1 : x < 100 ? 2 : x < 1000 ? 3 : x < 10000 ? 4 : x < 100000 ? 5 : x < 1000000 ? 6 : x < 10000000 ? 7 : x < 100000000 ? 8 : x < 1000000000 ? 9 : x < 10000000000 ? 10 : findDigits(x); } char tochar(unsigned short from) { return from == 0 ? '0' : from == 1 ? '1' : from == 1 ? '1' : from == 2 ? '2' : from == 3 ? '3' : from == 4 ? '4' : from == 5 ? '5' : from == 6 ? '6' : from == 7 ? '7' : from == 8 ? '8' : from == 9 ? '9' : '\0'; } char * tostring(long long from) { unsigned char negative = from < 0; unsigned int i = digits(from); char* to = (char*)calloc(1, i + negative); if (negative && (*to = '-') & (from = -from) & i++); *(to + i) = 0; while ((i>0+negative) && (*(to + (--i)) = tochar(((from) % 10))) | (from /= 10)); return to; }
如果要调试,可以将条件(指令)拆分为
while作用域{}
内的代码行。