int128_t类型的atoi()函数

17
我如何在支持int128_t的情况下使用argv值?我知道有关<cstdlib>暴露的atoi()和函数族,但不知为何找不到适用于int128_t固定宽度整数的函数。这可能是因为这种类型不受C或C++标准支持,但有没有什么方法使此代码正常工作?
#include <iostream>

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

几乎所有发布的答案对我来说都足够好,但我会选择这个对我的当前代码来说是一种快速解决方案的答案,所以请您也看看其他答案。

intmax_t的大小是多少? - Antti Haapala -- Слава Україні
3
你考虑实现自己的 atoint128_t 吗?一旦 128 位整数成为标准的一部分,你就可以将你的实现切换到调用标准函数的包装器。 - Marian
1
我怀疑现成的函数可能不存在。尝试编写自己的实现吧。快速的谷歌搜索揭示了这个链接:https://github.com/apache/orc/blob/master/c%2B%2B/src/Int128.cc#L355 - 此外,你可以查看一些已经存在的大整数库。虽然我不太喜欢推荐使用库,但你可能想要查看一些。 - Freakyy
@AnttiHaapala,intmax_t 的大小为 8,而 __int128_t 的大小为 16 - Abhinav Gauniyal
5
由于atoi()函数没有使用错误处理,其设计已经不太好了。如果存在“long long long”类型,你想要的是strtolll函数。 - Lundin
显示剩余3条评论
5个回答

5
这里有一种简单的实现方式:

以下是需要翻译的内容:

__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的行为一致。
编辑:
修订后的实现方式覆盖了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;
}

角落案例UB与int128_MIN。通常的UB是可以接受的,但仍然是UB。 - chux - Reinstate Monica
1
@chux 好发现。已经修订以处理 int128_MIN - dbush
@chqrlie 谢谢。我也加上了。 - dbush
@dbush: isspace((unsigned char)*p)比6个测试的包更有效率。 - chqrlie

4

下面是C++实现代码:

#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");
}

如果您想测试它,可以使用此处的流操作符 性能 我进行了一些性能测试。我生成了10万个在__int128_t完整支持范围内均匀分布的随机数。然后我将每个数字转换了2000次。所有这些(2亿)转换在约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;
}

3
@Jonas,如果你创建一个包含C字符串的第二个向量,那么分解就很容易了。尽管如此,如果目标CPU支持至少64位数字的乘法运算,实际性能可能会相当好,而我的方法受到无法在C中使用“硬件进位”的限制,因此需要花费时间来检查单个位。因此,对于“仅”128位,你的“天真”方法很有可能更快。不过随着数字变得越来越大——你懂的 ;) - user2371524
2
@Jonas,我会把这个加到我的答案里,这样看起来就不像是在试图“诋毁”那种天真的方法。 - user2371524
1
你应该检查整数溢出。 - nwellnhof
1
边界情况:当转换最小的__int128_t"-170141183460469231731687303715884105728"时,即使最终结果在范围内,res += c - '0';也会导致有符号整数溢出。这种未定义行为通常是期望的,但它并没有被定义。 - chux - Reinstate Monica
2
我很难过看到这段代码获得比精心打磨的 C 语言版本更多的投票。我猜 Java 或 JavaScript 版本会更受欢迎。 - chqrlie
显示剩余6条评论

3
在这里添加一个“不太幼稚”的纯 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暂存空间,参见双倍打法算法(这里是反向的)。这比通常情况下进行多次乘以10要高效得多。*)

这依赖于可变长度数组(VLA),如果没有它们,您可以替换为

char scratch[digits];

使用

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

并添加一个

free(scratch);

在函数的末尾。

当然,上面的代码与原始的 atoi() 有着相同的限制 (例如,溢出时会产生“随机”的垃圾,并且没有检查这种情况的方法)。如果您需要 strtol()-风格的保证和错误检查,请自行扩展它们(这不是一个大问题,只需要一些工作)。


*)当然,在C语言中实现双倍打乱总是受到硬件进位无法使用的影响,因此需要多个比特掩码和测试操作。另一方面,“朴素地”乘以10可能非常高效,只要平台提供的乘法指令的宽度“接近”您的目标类型即可。因此,在您典型的 x86_64 平台上(具有用于乘法64位整数的指令),这段代码可能比朴素的十进制方法慢得多。但对于真正的巨大整数(例如使用uintmax_t 数组实现的整数),它的缩放性更好。


如果可变长度数组不可用,alloca()也是一种选择。如果char scratch[digits];可接受,那么char *scratch = alloca( digits );也是可以接受的。 - Andrew Henle
1
据我所知,alloca()不在任何标准中。如果它可用,那么可变长度数组(VLAs)可能也可用,只要不是C89编译器。 - user2371524
@FelixPalmen 我现在看到了 while() 结尾处的 '+',但是这段代码现在可以通过 "+++123" 的测试,而 aoti() 函数却不行。 - chux - Reinstate Monica
@FelixPalmen 顺便说一下:处理 最小值 或者这里并不太难。 - chux - Reinstate Monica
跳过语句不正确:您应该跳过所有与 isspace() 匹配的字符,而不应跳过多个 + 符号或 + 后面的空格或 - - chqrlie
显示剩余7条评论

3
有没有办法让这段代码运行起来?
“那么实现自己的atoint128_t怎么样?”@Marian
自己编写atoint128_t()并不太难。
需要考虑以下几点。
  1. There is 0 or 1 more representable negative value than positive values. Accumulating the value using negative numbers provides more range.

  2. Overflow is not defined for atoi(). Perhaps provide a capped value and set errno? Detecting potential OF prevents UB.

  3. __int128_t constants need careful code to form correctly.

  4. How to handle unusual input? atoi() is fairly loose and made sense years ago for speed/size, yet less UB is usually desired these days. Candidate cases: "", " ", "-", "z", "+123", "999..many...999", "the min int128", "locale_specific_space" + " 123" or even non-string NULL.

  5. Code to do atoi() and atoint128_t() need only vary on the type, range, and names. The algorithm is the same.

    #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 或更高版本的 负数/正数% 功能。

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);

这个答案已经处理了溢出并像strtol()一样标识出错误信息 errno。只需要进行几个小修改即可。

  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); 功能也可以在 base016 时使用特殊代码处理其他进制。 @chqrlie


2

C标准不要求支持128位整数。

然而,现代编译器通常支持它们:包括gccclang都支持类型__int128_t__uint128_t,但令人惊讶的是,它们仍将intmax_tuintmax_t限制为64位。

除了基本算术运算符外,对于这些大整数的支持并不多,特别是在C库中:没有scanf()printf()转换说明符等。

下面是strtoi128()strtou128()atoi128()的实现,这些函数与C标准的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;
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接