Преобразовать целое число в строку без доступа к библиотекам
Я недавно прочитал пример вопроса о собеседовании:
Напишите функцию для преобразования целого числа в строку. Предположим, у вас нет доступа к библиотечным функциям, например, itoa() и т. Д.
Как бы вы пошли об этом?
14 ответов
Быстрый удар по нему: (отредактировано для обработки отрицательных чисел)
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[i-t-1];
buffer[i-t-1] ^= buffer[t];
buffer[t] ^= buffer[i-t-1];
}
if(n == 0)
{
buffer[0] = '0';
buffer[1] = '\0';
}
printf(buffer);
Посмотрите в интернете на реализацию 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];
}
Алгоритм легко увидеть на английском языке.
Дано целое число, например 123
разделите на 10 => 123/10. Уступая, результат = 12 и остаток = 3
добавьте 30h к 3 и добавьте стек (добавление 30h преобразует 3 в представление ASCII)
повторите шаг 1, пока результат < 10
добавьте 30h к результату и сохраните в стеке
стек содержит число в порядке | 1 | 2 | 3 |...
Я хотел бы иметь в виду, что все символы в порядке возрастания в наборе символов ASCII и между ними нет других символов.
Я бы также использовал / и% операторы неоднократно.
То, как я получу память для строки, будет зависеть от информации, которую вы не предоставили.
Предполагая, что это в десятичном формате, то вот так:
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;
}
Я столкнулся с этим вопросом, поэтому решил отказаться от кода, который обычно использую для этого:
char *SignedIntToStr(char *Dest, signed int Number, register unsigned char Base) {
if (Base < 2 || Base > 36) {
return (char *)0;
}
register unsigned char Digits = 1;
register unsigned int CurrentPlaceValue = 1;
for (register unsigned int T = Number/Base; T; T /= Base) {
CurrentPlaceValue *= Base;
Digits++;
}
if (!Dest) {
Dest = malloc(Digits+(Number < 0)+1);
}
char *const RDest = Dest;
if (Number < 0) {
Number = -Number;
*Dest = '-';
Dest++;
}
for (register unsigned char i = 0; i < Digits; i++) {
register unsigned char Digit = (Number/CurrentPlaceValue);
Dest[i] = (Digit < 10? '0' : 87)+Digit;
Number %= CurrentPlaceValue;
CurrentPlaceValue /= Base;
}
Dest[Digits] = '\0';
return RDest;
}
#include <stdio.h>
int main(int argc, char *argv[]) {
char String[32];
puts(SignedIntToStr(String, -100, 16));
return 0;
}
Это автоматически выделит память, если в Dest передается NULL. В противном случае он будет писать в Dest.
Чем быстрее тем лучше?
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;
}
Если вы хотите отладить, вы можете разделить условия (инструкции) на
строки кода внутри области видимости {},
Преобразовать целое число в строку без доступа к библиотекам
Сначала преобразуйте младшую цифру в символ, а затем перейдите к более старшей цифре.
Обычно я сдвигаю результирующую строку на место, но рекурсия позволяет пропустить этот шаг с некоторым трудным кодом.
С помощью neg_a в myitoa_helper() избегает неопределенного поведения с INT_MIN,
// Return character one past end of character digits.
static char *myitoa_helper(char *dest, int neg_a) {
if (neg_a <= -10) {
dest = myitoa_helper(dest, neg_a / 10);
}
*dest = (char) ('0' - neg_a % 10);
return dest + 1;
}
char *myitoa(char *dest, int a) {
if (a >= 0) {
*myitoa_helper(dest, -a) = '\0';
} else {
*dest = '-';
*myitoa_helper(dest + 1, a) = '\0';
}
return dest;
}
void myitoa_test(int a) {
char s[100];
memset(s, 'x', sizeof s);
printf("%11d <%s>\n", a, myitoa(s, a));
}
Тестовый код и вывод
#include "limits.h"
#include "stdio.h"
int main(void) {
const int a[] = {INT_MIN, INT_MIN + 1, -42, -1, 0, 1, 2, 9, 10, 99, 100,
INT_MAX - 1, INT_MAX};
for (unsigned i = 0; i < sizeof a / sizeof a[0]; i++) {
myitoa_test(a[i]);
}
return 0;
}
-2147483648 <-2147483648>
-2147483647 <-2147483647>
-42 <-42>
-1 <-1>
0 <0>
1 <1>
2 <2>
9 <9>
10 <10>
99 <99>
100 <100>
2147483646 <2147483646>
2147483647 <2147483647>
Реализация itoa() Функция кажется легкой задачей, но на самом деле вам нужно позаботиться о многих аспектах, связанных с вашими потребностями. Я предполагаю, что в интервью вы должны будете рассказать некоторые подробности о вашем пути к решению, а не копировать решение, которое можно найти в Google ( http://en.wikipedia.org/wiki/Itoa)
Вот несколько вопросов, которые вы можете задать себе или интервьюеру:
- Где должна находиться строка (malloced? Переданная пользователем? Static переменная?)
- Должен ли я поддерживать подписанные номера?
- Должен ли я поддерживать с плавающей запятой?
- Должен ли я поддерживать другие базы, а не 10?
- Нужна ли нам проверка входных данных?
- Выходная строка ограничена в длине?
И так далее.
Эта функция преобразует каждую цифру числа в символ, а символы складываются в один стек, образуя строку. Наконец, строка формируется из целого числа.
string convertToString(int num){
string str="";
for(; num>0;){
str+=(num%10+'0');
num/=10;
}
return str;
}
//Fixed the answer from [10]
#include <iostream>
void CovertIntToString(unsigned int n1)
{
unsigned int n = INT_MIN;
char buffer[50];
int i = 0;
n = n1;
bool isNeg = n<0;
n1 = isNeg ? -n1 : n1;
while(n1!=0)
{
buffer[i++] = n1%10+'0';
n1=n1/10;
}
if(isNeg)
buffer[i++] = '-';
buffer[i] = '\0';
// Now we must reverse the string
for(int t = 0; t < i/2; t++)
{
buffer[t] ^= buffer[i-t-1];
buffer[i-t-1] ^= buffer[t];
buffer[t] ^= buffer[i-t-1];
}
if(n == 0)
{
buffer[0] = '0';
buffer[1] = '\0';
}
printf("%s", buffer);
}
int main() {
unsigned int x = 4156;
CovertIntToString(x);
return 0;
}
Чуть дольше, чем решение:
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<j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
И хотя решение давольно давно здесь есть несколько полезных функций для начинающих. Я надеюсь, что вы будете полезны.
Это самая короткая функция, о которой я могу думать:
Правильно обрабатывает все 32-разрядные целые числа со знаком, включая 0, MIN_INT32, MAX_INT32.
Возвращает значение, которое можно сразу распечатать, например:
printf("%s\n", GetDigits(-123))
Прокомментируйте, пожалуйста, улучшения:
static const char LARGEST_NEGATIVE[] = "-2147483648";
static char* GetDigits(int32_t x) {
char* buffer = (char*) calloc(sizeof(LARGEST_NEGATIVE), 1);
int negative = x < 0;
if (negative) {
if (x + (1 << 31) == 0) { // if x is the largest negative number
memcpy(buffer, LARGEST_NEGATIVE, sizeof(LARGEST_NEGATIVE));
return buffer;
}
x *= -1;
}
// storing digits in reversed order
int length = 0;
do {
buffer[length++] = x % 10 + '0';
x /= 10;
} while (x > 0);
if (negative) {
buffer[length++] = '-'; // appending minus
}
// reversing digits
for (int i = 0; i < length / 2; i++) {
char temp = buffer[i];
buffer[i] = buffer[length-1 - i];
buffer[length-1 - i] = temp;
}
return buffer;
}
Вот простой подход, но я подозреваю, что если вы включите это как есть, не понимая и не перефразируя его, ваш учитель будет знать, что вы только что скопировали его из сети:
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, Я оставлю это вам, чтобы выяснить, как эти функции предназначены для вызова.