C语言 如何在预先确定结果不会大于_MAX的情况下将数字加到一个数上?

xqkwcwgp  于 2022-12-11  发布在  其他
关注(0)|答案(3)|浏览(149)

我正在使用旧的x = x * 10 + (c - '0')方法逐个字符地将数字字符串转换为数字。我知道atoi、strtol等...
问题是我想确保x永远不会超过该类型所能处理的最大可能值。但我确实也想支持小于UINT_MAX的任意最大值,但如果再添加1个字符,它仍然会溢出。
我想到的唯一解决方案是要么使x比我想支持的最大类型大一个类型,但这听起来不太好。
此外,由于这不是您通常的加法,因此涉及到更多的数学运算,并测试UINT_MAX / 10 > (double) (x + (c - '0') / 10)是否错误。
我在这方面没有经验,我希望有一些很酷的数学或比特移位技巧,以确保将数字c附加到数字x不会大于max(这通常是允许的最大类型大小,如UINT_MAX或ULONG_MAX等...)

#include <stdio.h>
#include <limits.h>

int main() {
    max = UINT_MAX;
    unsigned int x;
    char *str = "65536";
    int i;

    for (i = 0; str[i] != '\0', i++) {
        if (/* ??? test if adding new digit will exceed max ??? */) {
            x = x * 10 + (str[i] - '0');
        }
        else
            break;
    } 

    printf("x = %ud\n", x);

    return 0;
}

谢谢你,谢谢你

v440hwme

v440hwme1#

//  Will multiplying x by 10 and adding digit d overflow "unsigned int"?
_Bool WillItOverflow(unsigned int x, unsigned int d)
{
    if (x > UINT_MAX/10)
        return 1;
    else if (x == UINT_MAX/10 && d > UINT_MAX - UINT_MAX/10*10)
        return 1;
    else
        return 0;
}

证明如下:code style中的文本是code的值(例如,37/10是3);其它数学运算是普通的真实的运算(37/10是3.7)。

  • 因为整数除法会截断,所以UINT_MAX/10 =(UINT_MAXr)/10,其中 rUINT_MAX模10的余数。
  • 如果xUINT_MAX/10,则x〉= UINT_MAX/10 + 1 =(UINT_MAX-r)/10 + 1,所以10·x〉= UINT_MAX-r+10,所以10·x〉= UINT_MAX + 1。
  • 如果x = UINT_MAX/10,则10·x + d = 10·((UINT_MAXr)/10)+d = UINT_MAXr+ d,它明显大于UINT_MAX当且仅当dr
  • 否则,xUINT_MAX/10,所以xUINT_MAX/10 −1,所以10·x + d ≤ 10·((UINT_MAXr)/10)−10 + d = UINT_MAXr−10 + d,并且−r−10+ d是非正的,因为d〈10。所以10·x + dUINT_MAX
ycggw6v2

ycggw6v22#

如果使用gcc编译器,则可以使用内置函数:

int main() {
    unsigned int x = 0, tmp, tmp2;
    char *str = "4294967296";
    while(*str)
    {
        if(!__builtin_umul_overflow (x, 10, &tmp) && !__builtin_uadd_overflow(tmp, *str++ - '0', &tmp2)) 
        {
            x = tmp2;
        }
        else
            break;
    } 
    printf("x = %u\n", x);
}

这些函数编译非常高效的汇编代码:https://godbolt.org/z/xM1959bcd

wgxvkvu9

wgxvkvu93#

没有标准的方法可以在整数溢出发生后对其进行检测,但您可以在尝试添加下一个数字之前执行简单的数学运算来检测它:

#include <limits.h>
#include <stdio.h>

int main() {
    unsigned int x = 0;
    const char *str = "655360000000";
    int i;
    char cc;

    for (i = 0; (cc = str[i]) >= '0' && cc <= '9'; i++) {
        if (x < UINT_MAX / 10
        ||  (x == UINT_MAX / 10 && cc - '0' <= UINT_MAX % 10)) {
            x = x * 10 + (cc - '0');
        } else {
            /* number is too large */
            x = UINT_MAX;
            break;
        }
    } 
    printf("x = %u\n", x);
    return 0;
}

此方法适用于所有整数类型。
但是请注意,unsigned类型不会 overflow,无符号类型的算术是以最大值加1为模定义的。因此,您可以使用一个更简单的sloppy方法(尽管不推荐):

#include <limits.h>
#include <stdio.h>

int main() {
    unsigned int x = 0;
    const char *str = "655360000000";
    int i;
    char cc;

    for (i = 0; (cc = str[i]) >= '0' && cc <= '9'; i++) {
        unsigned int x0 = x;
        x = x * 10 + (cc - '0');
        if (x < x0) {
            /* number is too large */
            x = UINT_MAX;
            break;
        }
    }
    printf("x = %u\n", x);
    return 0;
}

相关问题