Подтвердить что ты не робот

Atoi() для типа int128_t

Как я могу использовать argv значения с поддержкой int128_t? Я знаю о atoi() и семействе функций, выставленных <cstdlib>, но каким-то образом я не могу найти его для целочисленного значения фиксированной ширины int128_t. Это может быть из-за того, что этот type не поддерживается стандартом c или С++, но есть ли способ заставить этот код работать?

#include <iostream>

int main(int argc, char **argv) {
    __int128_t value = atoint128_t(argv[1]);
}

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

4b9b3361

ОТВЕТЫ

Ответ 1

Вот реализация С++:

#include <string>
#include <stdexcept>

__int128_t atoint128_t(std::string const & in)
{
    __int128_t res = 0;
    size_t i = 0;
    bool sign = false;

    if (in[i] == '-')
    {
        ++i;
        sign = true;
    }

    if (in[i] == '+')
    {
        ++i;
    }

    for (; i < in.size(); ++i)
    {
        const char c = in[i];
        if (not std::isdigit(c)) 
            throw std::runtime_error(std::string("Non-numeric character: ") + c)
        res *= 10;
        res += c - '0';
    }

    if (sign)
    {
        res *= -1;
    }

    return res;
}

int main()
{
  __int128_t a = atoint128_t("170141183460469231731687303715884105727");
}

Если вы хотите протестировать его, тогда есть оператор потока здесь.

Производительность

Я провел несколько тестов производительности. Я генерирую 100 000 случайных чисел, равномерно распределенных во всей поддержке __int128_t. Затем я конвертировал каждый из них в 2000 раз. Все эти (200 000 000) конверсий завершены в течение ~ 12 секунд. Используя этот код:

#include <iostream>
#include <string>
#include <random>
#include <vector>
#include <chrono>

int main()
{
    std::mt19937 gen(0);
    std::uniform_int_distribution<> num(0, 9);
    std::uniform_int_distribution<> len(1, 38);
    std::uniform_int_distribution<> sign(0, 1);

    std::vector<std::string> str;

    for (int i = 0; i < 100000; ++i)
    {
        std::string s;
        int l = len(gen);
        if (sign(gen))
            s += '-';
        for (int u = 0; u < l; ++u)
            s += std::to_string(num(gen));
        str.emplace_back(s);
    }

    namespace sc = std::chrono;
    auto start =  sc::duration_cast<sc::microseconds>(sc::high_resolution_clock::now().time_since_epoch()).count();
    __int128_t b = 0;
    for (int u = 0; u < 200; ++u)
    {
        for (int i = 0; i < str.size(); ++i)
        {
            __int128_t a = atoint128_t(str[i]);
            b += a;
        }
    }
    auto time =  sc::duration_cast<sc::microseconds>(sc::high_resolution_clock::now().time_since_epoch()).count() - start;
    std::cout << time / 1000000. << 's' << std::endl;
}

Ответ 2

Добавление здесь "не столь наивной" реализации в чистом C, это все еще просто:

#include <stdio.h>
#include <inttypes.h>

__int128 atoi128(const char *s)
{
    while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '+') ++s;
    int sign = 1;
    if (*s == '-')
    {
        ++s;
        sign = -1;
    }
    size_t digits = 0;
    while (s[digits] >= '0' && s[digits] <= '9') ++digits;
    char scratch[digits];
    for (size_t i = 0; i < digits; ++i) scratch[i] = s[i] - '0';
    size_t scanstart = 0;

    __int128 result = 0;
    __int128 mask = 1;
    while (scanstart < digits)
    {
        if (scratch[digits-1] & 1) result |= mask;
        mask <<= 1;
        for (size_t i = digits-1; i > scanstart; --i)
        {
            scratch[i] >>= 1;
            if (scratch[i-1] & 1) scratch[i] |= 8;
        }
        scratch[scanstart] >>= 1;
        while (scanstart < digits && !scratch[scanstart]) ++scanstart;
        for (size_t i = scanstart; i < digits; ++i)
        {
            if (scratch[i] > 7) scratch[i] -= 3;
        }
    }

    return result * sign;
}


int main(int argc, char **argv)
{
    if (argc > 1)
    {
        __int128 x = atoi128(argv[1]);
        printf("%" PRIi64 "\n", (int64_t)x); // just for demo with smaller numbers
    }
}

Он читает число бит за битом, используя сдвинутое место для хранения BCD, см. Double dabble для алгоритма (здесь он отменяется). Это намного эффективнее, чем много умножений на 10 вообще. *)

Это зависит от VLA, без них вы можете заменить

char scratch[digits];

с

char *scratch = malloc(digits);
if (!scratch) return 0;

и добавьте

free(scratch);

в конце функции.

Конечно, приведенный выше код имеет те же ограничения, что и исходный atoi() (например, он будет генерировать "случайный" мусор при переполнении и не имеет возможности проверить это). Если вам нужны strtol() -стальные гарантии и проверку ошибок, расширьте его самостоятельно (не большая проблема, просто работайте).

*) Конечно, реализация двойной привязки в C всегда страдает от того факта, что вы не можете использовать "аппаратные носители", поэтому необходимы дополнительные операции маскировки и тестирования бит. С другой стороны, "наивное" умножение на 10 может быть очень эффективным, если платформа предоставляет инструкции умножения с шириной "закрыть" вашему целевому типу. Поэтому на вашей типичной платформе x86_64 (которая имеет инструкции для умножения 64-битных целых чисел) этот код, вероятно, намного медленнее, чем наивный десятичный метод. Но он значительно масштабируется для действительно огромных целых чисел (которые вы бы реализовали, например, используя массивы uintmax_t).

Ответ 3

Есть ли способ заставить этот код работать?

"Как насчет реализации собственного atoint128_t?" @Marian

Нельзя катить собственный atoint128_t().

Точки для рассмотрения.

  • Существует 0 или 1 более представимое отрицательное значение, чем положительные. Накопление значения с использованием отрицательных чисел дает больший диапазон.

  • Переполнение не определено для atoi(). Возможно, укажите ограниченное значение и установите errno? Обнаружение потенциала OF предотвращает UB.

  • __int128_t константы нуждаются в тщательном формировании кода.

  • Как обрабатывать необычный ввод? atoi() довольно свободен и имеет смысл много лет назад для скорости/размера, но в то же время в UB обычно требуется меньшее количество UB. Кандидаты: "", " ", "-", "z", "+123", "999..many...999", "the min int128", "locale_specific_space" + " 123" или даже нестроковые NULL.

  • Код для выполнения atoi() и atoint128_t() может варьироваться только по типу, диапазону и именам. Алгоритм тот же.

    #if 1
  #define int_t __int128_t
  #define int_MAX (((__int128_t)0x7FFFFFFFFFFFFFFF << 64) + 0xFFFFFFFFFFFFFFFF)
  #define int_MIN (-1 - int_MAX)
  #define int_atoi atoint128_t
#else
  #define int_t int
  #define int_MAX INT_MAX
  #define int_MIN INT_MIN
  #define int_atoi int_atoi
#endif

Пример кода: При необходимости. Использует функции C99 или более поздние negative/positive и %.

int_t int_atoi(const char *s) {
  if (s == NULL) {  // could omit this test
    errno = EINVAL;
    return 0;
  }
  while (isspace((unsigned char ) *s)) {  // skip same leading white space like atoi()
    s++;
  }
  char sign = *s;  // remember if the sign was `-` for later
  if (sign == '-' || sign == '+') {
    s++;
  }

  int_t sum = 0;
  while (isdigit((unsigned char)*s)) {
    int digit = *s - '0';
    if ((sum > int_MIN/10) || (sum == int_MIN/10 && digit <= -(int_MIN%10))) {
      sum = sum * 10 - digit;  // accumulate on the - side
    } else {
      sum = int_MIN;
      errno = ERANGE;
      break; // overflow
    }
    s++;
  }

  if (sign != '-') {
    if (sum < -int_MAX) {
      sum = int_MAX;
      errno = ERANGE;
    } else {
      sum = -sum;  // Make positive
    }
  }

  return sum;
}

Как @Lundin прокомментировал отсутствие обнаружения переполнения и т.д. Моделирование строки → int128 после strtol() - лучшая идея.

Для простоты рассмотрим __128_t strto__128_base10(const char *s, char *endptr);

Этот ответ на все готовые обрабатывает переполнение и флаги errno как strtol(). Просто нужно несколько изменений:

  bool digit_found = false;
  while (isdigit((unsigned char)*s)) { 
    digit_found = true;  

      // delete the `break` 
      // On overflow, continue looping to get to the end of the digits.
      // break;


  // after the `while()` loop:
  if (!digit_found) {  // optional test
    errno = EINVAL;
  }
  if (endptr) {
    *endptr = digit_found ? s : original_s;
  }

Полная функциональность long int strtol(const char *nptr, char **endptr, int base); также будет обрабатывать другие базы со специальным кодом, если base - 0 или 16. @chqrlie

Ответ 4

Вот простой способ реализации этого:

__int128_t atoint128_t(const char *s)
{
    const char *p = s;
    __int128_t val = 0;

    if (*p == '-' || *p == '+') {
        p++;
    }
    while (*p >= '0' && *p <= '9') {
        val = (10 * val) + (*p - '0');
        p++;
    }
    if (*s == '-') val = val * -1;
    return val;
}

Этот код проверяет каждый символ, чтобы увидеть, является ли он цифрой (с необязательным ведущим + или -), и если это умножит текущий результат на 10 и добавит значение, связанное с этой цифрой. Затем он инвертирует знак, если это необходимо.

Обратите внимание, что эта реализация не проверяет переполнение, что согласуется с поведением atoi.

EDIT:

Пересмотренная реализация, которая охватывает случай int128_MIN путем добавления или вычитания значения каждой цифры на основе знака и пропущенного пробела.

int myatoi(const char *s)
{
    const char *p = s;
    int neg = 0, val = 0;

    while ((*p == '\n') || (*p == '\t') || (*p == ' ') ||
           (*p == '\f') || (*p == '\r') || (*p == '\v')) {
        p++;
    }
    if ((*p == '-') || (*p == '+')) {
        if (*p == '-') {
            neg = 1;
        }
        p++;
    }
    while (*p >= '0' && *p <= '9') {
        if (neg) {
            val = (10 * val) - (*p - '0');
        } else {
            val = (10 * val) + (*p - '0');
        }
        p++;
    }
    return val;
}

Ответ 5

Стандарт C не поддерживает поддержку 128-битных целых чисел.

Тем не менее, они обычно поддерживаются современными компиляторами: gcc и clang поддерживают типы __int128_t и __uint128_t, но на удивление все еще сохраняют intmax_t и uintmax_t ограниченными до 64 бит.

Помимо основных арифметических операторов поддержка этих больших целых чисел, особенно в библиотеке C, не поддерживается: no scanf() или printf() спецификаторы преобразования и т.д.

Вот реализация strtoi128(), strtou128() и atoi128(), которая соответствует спецификациям C Standard atoi(), strtol() и strtoul().

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Change these typedefs for your local flavor of 128-bit integer types */
typedef __int128_t i128;
typedef __uint128_t u128;

static int strdigit__(char c) {
    /* This is ASCII / UTF-8 specific, would not work for EBCDIC */
    return (c >= '0' && c <= '9') ? c - '0'
        :  (c >= 'a' && c <= 'z') ? c - 'a' + 10
        :  (c >= 'A' && c <= 'Z') ? c - 'A' + 10
        :  255;
}

static u128 strtou128__(const char *p, char **endp, int base) {
    u128 v = 0;
    int digit;

    if (base == 0) {    /* handle octal and hexadecimal syntax */
        base = 10;
        if (*p == '0') {
            base = 8;
            if ((p[1] == 'x' || p[1] == 'X') && strdigit__(p[2]) < 16) {
                p += 2;
                base = 16;
            }
        }
    }
    if (base < 2 || base > 36) {
        errno = EINVAL;
    } else
    if ((digit = strdigit__(*p)) < base) {
        v = digit;
        /* convert to unsigned 128 bit with overflow control */
        while ((digit = strdigit__(*++p)) < base) {
            u128 v0 = v;
            v = v * base + digit;
            if (v < v0) {
                v = ~(u128)0;
                errno = ERANGE;
            }
        }
        if (endp) {
            *endp = (char *)p;
        }
    }
    return v;
}

u128 strtou128(const char *p, char **endp, int base) {
    if (endp) {
        *endp = (char *)p;
    }
    while (isspace((unsigned char)*p)) {
        p++;
    }
    if (*p == '-') {
        p++;
        return -strtou128__(p, endp, base);
    } else {
        if (*p == '+')
            p++;
        return strtou128__(p, endp, base);
    }
}

i128 strtoi128(const char *p, char **endp, int base) {
    u128 v;

    if (endp) {
        *endp = (char *)p;
    }
    while (isspace((unsigned char)*p)) {
        p++;
    }
    if (*p == '-') {
        p++;
        v = strtou128__(p, endp, base);
        if (v >= (u128)1 << 127) {
            if (v > (u128)1 << 127)
                errno = ERANGE;
            return -(i128)(((u128)1 << 127) - 1) - 1;
        }
        return -(i128)v;
    } else {
        if (*p == '+')
            p++;
        v = strtou128__(p, endp, base);
        if (v >= (u128)1 << 127) {
            errno = ERANGE;
            return (i128)(((u128)1 << 127) - 1);
        }
        return (i128)v;
    }
}

i128 atoi128(const char *p) {
    return strtoi128(p, (char**)NULL, 10);
}

char *utoa128(char *dest, u128 v, int base) {
    char buf[129];
    char *p = buf + 128;
    const char *digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    *p = '\0';
    if (base >= 2 && base <= 36) {
        while (v > (unsigned)base - 1) {
            *--p = digits[v % base];
            v /= base;
        }
        *--p = digits[v];
    }
    return strcpy(dest, p);
}

char *itoa128(char *buf, i128 v, int base) {
    char *p = buf;
    u128 uv = (u128)v;
    if (v < 0) {
        *p++ = '-';
        uv = -uv;
    }
    if (base == 10)
        utoa128(p, uv, 10);
    else
    if (base == 16)
        utoa128(p, uv, 16);
    else
        utoa128(p, uv, base);
    return buf;
}

static char *perrno(char *buf, int err) {
    switch (err) {
    case EINVAL:
        return strcpy(buf, "EINVAL");
    case ERANGE:
        return strcpy(buf, "ERANGE");
    default:
        sprintf(buf, "%d", err);
        return buf;
    }
}

int main(int argc, char *argv[]) {
    char buf[130];
    char xbuf[130];
    char ebuf[20];
    char *p1, *p2;
    i128 v, v1;
    u128 v2;
    int i;

    for (i = 1; i < argc; i++) {
        printf("%s:\n", argv[i]);
        errno = 0;
        v = atoi128(argv[i]);
        perrno(ebuf, errno);
        printf("  atoi128():   %s  0x%s  errno=%s\n",
               itoa128(buf, v, 10), utoa128(xbuf, v, 16), ebuf);
        errno = 0;
        v1 = strtoi128(argv[i], &p1, 0);
        perrno(ebuf, errno);
        printf("  strtoi128(): %s  0x%s  endptr:\"%s\"  errno=%s\n",
               itoa128(buf, v1, 10), utoa128(xbuf, v1, 16), p1, ebuf);
        errno = 0;
        v2 = strtou128(argv[i], &p2, 0);
        perrno(ebuf, errno);
        printf("  strtou128(): %s  0x%s  endptr:\"%s\"  errno=%s\n",
               utoa128(buf, v2, 10), utoa128(xbuf, v2, 16), p2, ebuf);
    }
    return 0;
}