将输入读入动态大小的int？

I need to read a huge number from the stdin, here is the code i have so far:

我需要从stdin读取一个大数字,这是我到目前为止的代码:

int main() {
    int x;
    int* n1;
    scanf("%d", &x); // I get the number of digits the integer will have

    n1 = malloc(x * sizeof(int)); // I resize the integer pointer
}

So my question is how can I read this possibly huge sized int from stdin?

所以我的问题是如何从stdin中读取这个可能很大的int?

4 个解决方案

#1

the most reliable method of handling very large numbers is to use the 'bignum.c', which is available at: http://www3.cs.stony*.edu/~skiena/392/programs/bignum.c

处理非常大数字的最可靠方法是使用'bignum.c',可在以下网址获得:http://www3.cs.stony*.edu/~skiena/392/programs/bignum.c

the referenced code is a complete program,. but the functions and struct are free to use.

引用的代码是一个完整的程序。但是函数和结构可以*使用。

where is what you would find there:

你会在那里找到什么:

/*  bignum.c
    Implementation of large integer arithmetic: addition, subtraction,
        multiplication, and division.

    begun: February 7, 2002
    by: Steven Skiena
*/

/*
Copyright 2003 by Steven S. Skiena; all rights reserved. 

Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.

This program appears in my book:

"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.

See our website www.programming-challenges.com for additional information.

This book can be ordered from Amazon.com at

http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/

*/


#include <stdio.h>

#define MAXDIGITS   100     /* maximum length bignum */ 

#define PLUS        1       /* positive sign bit */
#define MINUS       -1      /* negative sign bit */

typedef struct {
        char digits[MAXDIGITS];         /* represent the number */
    int signbit;            /* 1 if positive, -1 if negative */ 
        int lastdigit;          /* index of high-order digit */
} bignum;


print_bignum(bignum *n)
{
    int i;

    if (n->signbit == MINUS) printf("- ");
    for (i=n->lastdigit; i>=0; i--)
        printf("%c",'0'+ n->digits[i]);

    printf("\n");
}

int_to_bignum(int s, bignum *n)
{
    int i;              /* counter */
    int t;              /* int to work with */

    if (s >= 0) n->signbit = PLUS;
    else n->signbit = MINUS;

    for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;

    n->lastdigit = -1;

    t = abs(s);

    while (t > 0) {
        n->lastdigit ++;
        n->digits[ n->lastdigit ] = (t % 10);
        t = t / 10;
    }

    if (s == 0) n->lastdigit = 0;
}

initialize_bignum(bignum *n)
{
    int_to_bignum(0,n);
}


int max(int a, int b)
{
    if (a > b) return(a); else return(b);
}

/*  c = a +-/* b;   */

add_bignum(bignum *a, bignum *b, bignum *c)
{
    int carry;          /* carry digit */
    int i;              /* counter */

    initialize_bignum(c);

    if (a->signbit == b->signbit) c->signbit = a->signbit;
    else {
        if (a->signbit == MINUS) {
            a->signbit = PLUS;
            subtract_bignum(b,a,c);
            a->signbit = MINUS;
        } else {
                        b->signbit = PLUS;
                        subtract_bignum(a,b,c);
                        b->signbit = MINUS;
        }
        return;
    }

    c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
    carry = 0;

    for (i=0; i<=(c->lastdigit); i++) {
        c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
        carry = (carry + a->digits[i] + b->digits[i]) / 10;
    }

    zero_justify(c);
}


subtract_bignum(bignum *a, bignum *b, bignum *c)
{
    int borrow;         /* has anything been borrowed? */
    int v;              /* placeholder digit */
    int i;              /* counter */

    initialize_bignum(c);

    if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
                b->signbit = -1 * b->signbit;
                add_bignum(a,b,c);
                b->signbit = -1 * b->signbit;
        return;
        }

    if (compare_bignum(a,b) == PLUS) {
        subtract_bignum(b,a,c);
        c->signbit = MINUS;
        return;
    }

        c->lastdigit = max(a->lastdigit,b->lastdigit);
        borrow = 0;

        for (i=0; i<=(c->lastdigit); i++) {
        v = (a->digits[i] - borrow - b->digits[i]);
        if (a->digits[i] > 0)
            borrow = 0;
        if (v < 0) {
            v = v + 10;
            borrow = 1;
        }

                c->digits[i] = (char) v % 10;
        }

    zero_justify(c);
}

compare_bignum(bignum *a, bignum *b)
{
    int i;              /* counter */

    if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
    if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);

    if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
    if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);

    for (i = a->lastdigit; i>=0; i--) {
        if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
        if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
    }

    return(0);
}

zero_justify(bignum *n)
{
    while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
        n->lastdigit --;

        if ((n->lastdigit == 0) && (n->digits[0] == 0))
        n->signbit = PLUS;  /* hack to avoid -0 */
}


digit_shift(bignum *n, int d)       /* multiply n by 10^d */
{
    int i;              /* counter */

    if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;

    for (i=n->lastdigit; i>=0; i--)
        n->digits[i+d] = n->digits[i];

    for (i=0; i<d; i++) n->digits[i] = 0;

    n->lastdigit = n->lastdigit + d;
}



multiply_bignum(bignum *a, bignum *b, bignum *c)
{
    bignum row;         /* represent shifted row */
    bignum tmp;         /* placeholder bignum */
    int i,j;            /* counters */

    initialize_bignum(c);

    row = *a;

    for (i=0; i<=b->lastdigit; i++) {
        for (j=1; j<=b->digits[i]; j++) {
            add_bignum(c,&row,&tmp);
            *c = tmp;
        }
        digit_shift(&row,1);
    }

    c->signbit = a->signbit * b->signbit;

    zero_justify(c);
}


divide_bignum(bignum *a, bignum *b, bignum *c)
{
        bignum row;                     /* represent shifted row */
        bignum tmp;                     /* placeholder bignum */
    int asign, bsign;       /* temporary signs */
        int i,j;                        /* counters */

    initialize_bignum(c);

    c->signbit = a->signbit * b->signbit;

    asign = a->signbit;
    bsign = b->signbit;

    a->signbit = PLUS;
        b->signbit = PLUS;

    initialize_bignum(&row);
    initialize_bignum(&tmp);

    c->lastdigit = a->lastdigit;

    for (i=a->lastdigit; i>=0; i--) {
        digit_shift(&row,1);
        row.digits[0] = a->digits[i];
        c->digits[i] = 0;
        while (compare_bignum(&row,b) != PLUS) {
            c->digits[i] ++;
            subtract_bignum(&row,b,&tmp);
            row = tmp;
        }
    }

    zero_justify(c);

    a->signbit = asign;
    b->signbit = bsign;
}



main()
{
    int a,b;
    bignum n1,n2,n3,zero;

    while (scanf("%d %d\n",&a,&b) != EOF) {
        printf("a = %d    b = %d\n",a,b);
        int_to_bignum(a,&n1);
        int_to_bignum(b,&n2);

        add_bignum(&n1,&n2,&n3);
        printf("addition -- ");
        print_bignum(&n3);

        printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));

        subtract_bignum(&n1,&n2,&n3);
        printf("subtraction -- ");
        print_bignum(&n3);

                multiply_bignum(&n1,&n2,&n3);
        printf("multiplication -- ");
                print_bignum(&n3);

        int_to_bignum(0,&zero);
        if (compare_bignum(&zero, &n2) == 0)
            printf("division -- NaN \n");
                else {
            divide_bignum(&n1,&n2,&n3);
            printf("division -- ");
                    print_bignum(&n3);
        }
        printf("--------------------------\n");
    }
}

#2

There is no such thing as a "dynamic sized int" in C. As others have suggested, depending on your use case, reading the number as a string might be what you want. (If you use scanf for this, beware of buffer overflows.)

在C中没有“动态大小的int”这样的东西。正如其他人所建议的那样,根据你的用例,将数字作为字符串读取可能就是你想要的。 (如果你使用scanf,请注意缓冲区溢出。)

If you need to do arithmetic on the number, you might wish to use an existing library such as libgmp for this to benefit from an existing solution to the problem. You could also re-implement libgmp's functionality yourself, but unless you're doing this as a learning exercise, there's little reason to.

如果您需要对数字进行算术运算,您可能希望使用现有的库(例如libgmp)来从此问题的现有解决方案中受益。您也可以自己重新实现libgmp的功能,但除非您将此作为学习练习,否则没有理由这样做。

#3

int x;
int* n1;
int i;
scanf("%d", &x);

n1 = malloc(x * sizeof(int));

for(i = 0; i < x; ++i){
    scanf("%1d", &n1[i]);//Read (unsigned) one digit
}
for(i = 0; i < x; ++i){
    printf("%d", n1[i]);
}
puts("");

#4

The way you are designing it right now, you will have a pointer to int, in other words: an array of ints. The biggest integer type you can store you numbers in is long long (its size depends on the machine, on 64-bit machines it's generally 8 bytes).

你现在正在设计它的方式,你将有一个指向int的指针,换句话说:一个int数组。你可以存储数字的最大整数类型是长(它的大小取决于机器,在64位机器上它通常是8字节)。

You may also consider either storing the number in a string (after allocating a char*) or, as you wrote, in an array of ints, where each of the array elements would hold arbitrary number of digits (then I would suggest using getchar() and atoi() functions instead of scanf()).

您也可以考虑将数字存储在字符串中(在分配char *之后),或者如您所写,在一个int数组中,其中每个数组元素将包含任意数量的数字(然后我建议使用getchar( )和atoi()函数而不是scanf())。