Я не могу понять следующий код реализации atoi, особенно эту строку:
k = (k << 3) + (k << 1) + (*p) - '0';
Вот код:
int my_atoi(char *p) {
int k = 0;
while (*p) {
k = (k << 3) + (k << 1) + (*p) - '0';
p++;
}
return k;
}
Может кто-нибудь объяснить это мне?
Другой вопрос: каким должен быть алгоритм atof реализации?
k = (k << 3) + (k << 1);
означает
k = k * 2³ + k * 2¹ = k * 8 + k * 2 = k * 10
Помогает ли это?
Термин *p - '0' добавляет значение следующей цифры; это работает, потому что C требует, чтобы цифровые символы имели последовательные значения, так что '1' == '0' + 1, '2' == '0' + 2 и т.д.
Что касается вашего второго вопроса (atof), это должен быть его собственный вопрос, и это тема для диссертации, а не что-то простое ответить...
<< - битовое смещение, (k<<3)+(k<<1) - это k*10, написанный кем-то, кто считал его более умным, чем компилятор (ну, он ошибался...)
(*p) - '0' вычитает значение символа 0 из символа, на который указывает p, эффективно преобразовывая символ в число.
Я надеюсь, что вы можете выяснить все остальное... просто помните, как работает десятичная система.
Вот спецификация для стандартной функции atoi. Извините, что не цитируете стандарт, но это будет работать так же хорошо (с: http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/)
Функция сначала отбрасывает столько пробельных символов (как в
isspace), сколько необходимо, пока не будет найден первый непробельный символ. Затем, начиная с этого символа, принимает необязательный начальный знак плюс или минус, за которым следует как можно больше цифр от 10 до 10, и интерпретирует их как числовое значение.Строка может содержать дополнительные символы после тех, которые образуют целое число, которые игнорируются и не влияют на поведение этой функции.
Если первая последовательность непробельных символов в
strне является допустимым целым числом или если такой последовательности не существует, поскольку либоstrпуста, либо содержит только пробельные символы, преобразование не выполняется и возвращается ноль.
#include <stdio.h>
#include <errno.h>
#include <limits.h>
double atof(const char *string);
int debug=1;
int main(int argc, char **argv)
{
char *str1="3.14159",*str2="3",*str3="0.707106",*str4="-5.2";
double f1,f2,f3,f4;
if (debug) printf("convert %s, %s, %s, %s\n",str1,str2,str3,str4);
f1=atof(str1);
f2=atof(str2);
f3=atof(str3);
f4=atof(str4);
if (debug) printf("converted values=%f, %f, %f, %f\n",f1,f2,f3,f4);
if (argc > 1)
{
printf("string %s is floating point %f\n",argv[1],atof(argv[1]));
}
}
double atof(const char *string)
{
double result=0.0;
double multiplier=1;
double divisor=1.0;
int integer_portion=0;
if (!string) return result;
integer_portion=atoi(string);
result = (double)integer_portion;
if (debug) printf("so far %s looks like %f\n",string,result);
/* capture whether string is negative, don't use "result" as it could be 0 */
if (*string == '-')
{
result *= -1; /* won't care if it was 0 in integer portion */
multiplier = -1;
}
while (*string && (*string != '.'))
{
string++;
}
if (debug) printf("fractional part=%s\n",string);
// if we haven't hit end of string, go past the decimal point
if (*string)
{
string++;
if (debug) printf("first char after decimal=%c\n",*string);
}
while (*string)
{
if (*string < '0' || *string > '9') return result;
divisor *= 10.0;
result += (double)(*string - '0')/divisor;
if (debug) printf("result so far=%f\n",result);
string++;
}
return result*multiplier;
}
Интересно, что страница man atoi не указывает на установку errno, поэтому, если вы говорите любое число > (2 ^ 31) -1, вам не повезло и аналогично для чисел меньше -2 ^ 31 (предполагая 32-битный int). Вы получите ответ, но это не то, что вы хотите. Здесь тот, который может принимать диапазон - ((2 ^ 31) -1) до (2 ^ 31) -1 и возвращать INT_MIN (- (2 ^ 31)), если по ошибке. errno затем может быть проверен, чтобы проверить, не переполнено ли оно.
#include <stdio.h>
#include <errno.h> /* for errno */
#include <limits.h> /* for INT_MIN */
#include <string.h> /* for strerror */
extern int errno;
int debug=0;
int atoi(const char *c)
{
int previous_result=0, result=0;
int multiplier=1;
if (debug) printf("converting %s to integer\n",c?c:"");
if (c && *c == '-')
{
multiplier = -1;
c++;
}
else
{
multiplier = 1;
}
if (debug) printf("multiplier = %d\n",multiplier);
while (*c)
{
if (*c < '0' || *c > '9')
{
return result * multiplier;
}
result *= 10;
if (result < previous_result)
{
if (debug) printf("number overflowed - return INT_MIN, errno=%d\n",errno);
errno = EOVERFLOW;
return(INT_MIN);
}
else
{
previous_result *= 10;
}
if (debug) printf("%c\n",*c);
result += *c - '0';
if (result < previous_result)
{
if (debug) printf("number overflowed - return MIN_INT\n");
errno = EOVERFLOW;
return(INT_MIN);
}
else
{
previous_result += *c - '0';
}
c++;
}
return(result * multiplier);
}
int main(int argc,char **argv)
{
int result;
printf("INT_MIN=%d will be output when number too high or too low, and errno set\n",INT_MIN);
printf("string=%s, int=%d\n","563",atoi("563"));
printf("string=%s, int=%d\n","-563",atoi("-563"));
printf("string=%s, int=%d\n","-5a3",atoi("-5a3"));
if (argc > 1)
{
result=atoi(argv[1]);
printf("atoi(%s)=%d %s",argv[1],result,(result==INT_MIN)?", errno=":"",errno,strerror(errno));
if (errno) printf("%d - %s\n",errno,strerror(errno));
else printf("\n");
}
return(errno);
}
Вот моя реализация (успешно протестирована со случаями, содержащими и начинающимися с букв +, - и нулей). Я попытался перепроектировать функцию Atoi в Visual Studio. Если входная строка содержит только числовые символы, она может быть реализована в одном цикле. но это становится сложным, потому что вы должны заботиться о -, + и буквы.
int atoi(char *s)
{
int c=1, a=0, sign, start, end, base=1;
//Determine if the number is negative or positive
if (s[0] == '-')
sign = -1;
else if (s[0] <= '9' && s[0] >= '0')
sign = 1;
else if (s[0] == '+')
sign = 2;
//No further processing if it starts with a letter
else
return 0;
//Scanning the string to find the position of the last consecutive number
while (s[c] != '\n' && s[c] <= '9' && s[c] >= '0')
c++;
//Index of the last consecutive number from beginning
start = c - 1;
//Based on sign, index of the 1st number is set
if (sign==-1)
end = 1;
else if (sign==1)
end = 0;
//When it starts with +, it is actually positive but with a different index
//for the 1st number
else
{
end = 1;
sign = 1;
}
//This the main loop of algorithm which generates the absolute value of the
//number from consecutive numerical characters.
for (int i = start; i >=end ; i--)
{
a += (s[i]-'0') * base;
base *= 10;
}
//The correct sign of generated absolute value is applied
return sign*a;
}
о коде подсказки atoi() отсюда:
и основываясь на atoi(), моя реализация atof():
[имеют то же ограничение исходного кода, не проверяет длину и т.д.]
double atof(const char* s)
{
double value_h = 0;
double value_l = 0;
double sign = 1;
if (*s == '+' || *s == '-')
{
if (*s == '-') sign = -1;
++s;
}
while (*s >= 0x30 && *s <= 0x39)
{
value_h *= 10;
value_h += (double)(*s - 0x30);
++s;
}
// 0x2E == '.'
if (*s == 0x2E)
{
double divider = 1;
++s;
while (*s >= 0x30 && *s <= 0x39)
{
divider *= 10;
value_l *= 10;
value_l += (double)(*s - 0x30);
++s;
}
return (value_h + value_l/divider) * sign;
}
else
{
return value_h * sign;
}
}