big integers in c++

Question

I know this question has probably been asked in this forum many times and in the web as well. I am asked to create an implementation of a big integer in c++, however there is a constraint that one of my constructor should take an int as an argument... so I am guessing there will be more than one non-default constructor... so my question is, what would be the easiest way to do this??

Answer 1

Why reinvent the wheel? Use the GNU MP library.

[EDIT] Smells like homework. So when you have a BigBit class, then do this:

1. Clear all bits
2. Write a loop which goes over all bits on the int argument of the constructor
3. For each bit in the int argument which is != 0, set the bit in the BigBit vector.

Answer 2

C++ BigInt class
C++ Big Integer Library
to write big int for example :

typedef struct {
    int high, low;
} BiggerInt;

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

Answer 3

The question, then, seems to be "how do I turn an integer into a list of bits"? Put another way, what's the base-2 representation of an integer?

As this is supposed to be homework, let me talk around the problem by thinking in base-10; the appropriate changes should be obvious with some thought.

Given a base 10 number, it's pretty easy to figure out what the rightmost digit is: It's just the remainder when dividing by 10. E.g. if n=1234, then it's rightmost digit is n%10 = 4. To get the next rightmost digit, we divide by 10 (getting 123), and repeat the process. So:

1234/10=123; 1234%10 = 4
123/10=12  ; 123%10 = 3
12/10=1    ; 12%10 = 2
1/10=0     ; 1%10 = 1

So now we've gotten the answers [4,3,2,1]. If we reverse them, we have the base-10 digits of our number: [1, 2, 3, 4].