Есть некоторые ошибки при реализации моего собственного Atoi () - PullRequest
Новая
       71

Есть некоторые ошибки при реализации моего собственного Atoi ()

0 голосов
/ 27 мая 2020

Я не понимаю. Пока моя функция возвращается из char в основном, случайное число. Исходный atoi () возвращает -1. Сейчас я использую версию C11. Я слышал от кого-то, что это из-за переполнения int, и мне нужно вернуть int из моей функции, но в настоящее время я возвращаюсь долго. Как я могу обнаружить intOverflow, если это не 2147483647 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool mx_isdigit(int c) {
    return c >= 48 && c <= 57;
}


bool mx_isspace(char c) {
    return (c >= 9 && c <= 13) || c == 32;
}


int mx_atoi(const char *str) {
    long num = 0;
    int sign = 1;

    for (; mx_isspace(*str); str++);

    if (*str == '-' || *str == '+') {
        sign = *str == '-' ? -sign : sign;
        str++;
    }

    for (; *str; str++) {
        if (!mx_isdigit(*str)) {
            break;
        }
        num = (num * 10) + (*str - '0');
    }
    return sign == -1 ? -num : 0 + num;
}

int main(void) {

    char str[100] = "12327123061232712306";
    printf("R: %d\n", atoi(str));
    printf("M: %d", mx_atoi(str));
}

Ответы [ 4 ]

1 голос
/ 28 мая 2020

c> = 48 && c <= 57 </p>

Не используйте в коде числа magi c. Вместо 48 используйте '0', который более читабелен и указывает ваше намерение.

Как я могу обнаружить intOverflow

Переполнение происходит, когда результат больше, чем максимум, который может представить тип. Таким образом, имея числа a и b, мы можем написать: 

a + b > MAX

Но это условие не может быть проверено, потому что a + b ... переполнится. Но если перевернуть выражение: 

b > MAX - a

Можно легко проверить с помощью простого if. MAX - максимальное значение для типа, для int то есть INT_MAX из limits.h. 

int mx_atoi(const char *str) {    
    for (; mx_isspace(*str); str++);

    bool negative = false;
    if (*str == '-' || *str == '+') {
        negative = *str == '-';
        str++;
    }

    int num = 0;
    for (; mx_isdigit(*str); str++) {
        if (INT_MAX / 10 < num) {
            goto ERR_OVERFLOW;
        }
        num *= 10;
        const unsigned char c = *str - '0';
        if (INT_MAX - c < num) {
            goto ERR_OVERFLOW;
        }
        num += c;

    }
    return negative ? -num : num;
    ERR_OVERFLOW:
    return negative ? INT_MIN : INT_MAX;
}
1 голос
/ 28 мая 2020

Внутри вашей функции int mx_atoi(const char *str) {... вы вычисляете результат типа long, но функция возвращает int; поэтому, если результат, сохраненный в num типа long, не помещается в int, что-то будет потеряно (на самом деле, поскольку целые значения со знаком преобразованы, поведение "определяется реализацией", то есть зависит от компилятора ). Результат может быть побитово усечен, давая число, которое "выглядит" несколько иначе, чем введенное вами десятичное число. См., Например, это онлайн-черновик C11. Применяется жирный абзац:

6.3.1.3 Целые числа со знаком и без знака

1 Когда значение с целочисленным типом преобразуется в другой целочисленный тип, отличный от _Bool, если значение может быть представлено новым типом, оно не изменяется.

2 В противном случае, если новый тип беззнаковый, значение преобразуется путем многократного добавления или вычитания на единицу больше максимального значения, которое может быть представлено в новом типе до тех пор, пока значение не окажется в диапазоне нового типа. 60)

3 В противном случае новый тип подписывается и значение не может быть представлено в нем; либо результат определяется реализацией, либо возникает сигнал, определяемый реализацией.

Сделать int mx_atoi(const char *str) до long mx_atoi(const char *str), использовать long -переменную для сохранения результата и не забудьте использовать спецификатор формата %ld вместо %d в вашем printf then.

В противном случае, если вам нужно придерживаться int и вы хотите безопасно реагировать на переполнения, вы может сделать что-то вроде 

if (num > INT_MAX) {
  return -1;
}

внутри вашего l oop. INT_MAX определяется в limits.h

0 голосов
/ 28 мая 2020

Это самый простой способ, как я догадался. atoi () с использованием LLONG_MAX check вместо LONG_MAX или INT_MAX. Итак, экспериментируя с теми ограничениями, которые я обнаружил. Если (num * 10) + (*str - '0') превысит предел типа long long, он преобразует число в отрицательное значение LLONG_MIN. Итак, я создал оператор if, который проверяет, будет ли следующий расчет меньше предыдущего. И если это правда, возвращается 0 или -1. 

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

bool mx_isdigit(int c);
bool mx_isspace(char c);

int mx_atoi(const char* str) {
    long long num = 0;
    int sign = 1;

    for (; mx_isspace(*str); str++);

    if (*str == '-' || *str == '+') {
        sign = *str == '-' ? -sign : sign;
        str++;
    }

    for (; *str; str++) {
        if (!mx_isdigit(*str)) {
            break;
        }

      if ((num * 10) + (*str - '0') < num) {
          return sign == -1 ? 0 : -1;
      }

        num = (num * 10) + (*str - '0');
    }

    return sign == -1 ? -num : num;
}

int main(void) {

    char str[100] = "-9223372036854775809";
    printf("R: %d\n", atoi(str));
    printf("M: %d\n", mx_atoi(str));
}
0 голосов
/ 28 мая 2020

int потенциал переполнения

num = (num * 10) + (*str - '0'); встречается int переполнение, что является неопределенным поведением (UB), когда:

1) входная строка должна представлять INT_MIN и int/long иметь одинаковый диапазон ИЛИ
2) входная строка кодирует значение вне диапазона int.

Различные способы избежать этого.

Не обнаруживает строку без цифр

Возвращение 0 в этом случае является разумным, но код может захотеть установить некоторую ошибку.

Не жалуется на завершающие нецифровые цифры

Простое игнорирование завершающих символов является разумным, но код может захотеть установить некоторую ошибку.

Способ избежать int переполнение (и не полагаться на long шире, чем int) - это проверка до (num * 10) + (*str - '0'), и поскольку отрицательных int s больше, чем положительных, накапливаются на отрицательной стороне. 

bool digit_found = false;
int val = 0;
for (; mx_isdigit(*str); str++) {
    digit_found = true;
    int digit = *str - '\0';
    if (val <= INT_MIN/10 && (val < INT_MIN/10 || digit > -(INT_MIN%10))) { // C99
      return sign == 1 ? INT_MAX : INT_MIN;
    }
    val = val * 10 - digit;  // note subtraction here
}

if (!digit_found) {
    return 0; // Or handle in some other fashion
}

if (sign == 1) {
  // If val is too negative to negate ...
  if (val < -INT_MAX) {
    return INT_MAX;  // overflow
  }
  return -val;
}
return val;
...