Overflow and Underflow BigIntegers in C#

Question

I have the following piece of code which i'm trying to comprehend.

The Big Integer class (custom, not the standard class) has the following members:

    private const int maxLength = 2000;
    private uint[] data = null;             // stores bytes from the Big Integer
    public int dataLength;                 // number of actual chars used

The constructor is as follows:

public BigInteger(long value)
    {
            data = new uint[maxLength];
            long tempVal = value;

            // copy bytes from long to BigInteger without any assumption of
            // the length of the long datatype

            dataLength = 0;
            while(value != 0 && dataLength < maxLength)
            {
                    data[dataLength] = (uint)(value & 0xFFFFFFFF);
                    value >>= 32;
                    dataLength++;
            }

            if(tempVal > 0)         // overflow check for +ve value
            {
                    if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
                            throw(new ArithmeticException("Positive overflow in constructor."));
            }
            else if(tempVal < 0)    // underflow check for -ve value
            {
                    if(value != -1 || (data[dataLength-1] & 0x80000000) == 0)
                            throw(new ArithmeticException("Negative underflow in constructor."));
            }

Essentially, the BigInteger class aids in manipulating large integers. The constructor is used to assign a long value to a Big Integer object. I understand that the variable named value is copied to the uint[] data array (the maximum number of digits allowed being maxLength).

I'm not able to completely understand how the check for underflow and overflow has been made. I understand the conditions if(tempVal > 0) and else if(tempVal < 0) but why is the highest array index of data anded with 0x80000000 in case of both underflow and overflow? (why not 0xFFFFFFFF in the case of overflow/underflow? If the number is even 1 more/less than the maximum number allowed, it will result in an overflow/underflow)

Also, doesn't passing a long value to the constructor limit the overall size of the BigInteger (whose maximum value can then be the same as the maximum value of a long variable)?

Answer 1

For an int in C#, the bit at 0x80000000 (ie. the most significant bit) is the sign bit. In other words if it contains 1, then the number is negative. An int that contained bits 0xffffffff would be interpreted as containing -1. During integer arithmetic, a number carrying over into this bit would represent an overflow condition, which is presumably what the check is based on.

Similarly, the sign bit contains 0 for any positive number, so if you're expecting the number to be negative, but this bit contains 0, then you know that some overflow must have occurred into this bit. In fact, the way negative numbers are represented, every bit to the left of the actual number is set to 1. For example, 3 is represented as 0x00000003 (everything to the left is 0) while -3 is represented as 0xfffffffd (everything to the left is 1).

The code will basically populate the entire array with the same convention. Store a positive number in it, and it'll fill the first couple of elements, leaving everything else zero'd out. Pass a negative number in, and it'll put the number in the first couple of elements, then fill up almost the entire array with 0xffffffff, thus preserving the convention that the very leftmost bit (ie. the leftmost bit of the last element of the array) is the sign bit. The filling the entire array, after the number, with -0xffffffff, happens because the right-shift operator in C# preserves the sign bit: If it's right-shifting a negative number, it fills everything to the left with 1's not 0's.

So the way to think of those tests is that they are checking that the sign bit of the array (the leftmost bit of the last element) is correct.

By the way, I don't believe there's any way either exception condition would be triggered, so I suspect those tests may have been put in for debugging purposes while the code was being written, and then got left in.

My reading of the code is that you are correct when you suggest that passing the long value to the constructor limits the overall size of the value stored in the BigInteger. However, you've only shown the code for the constructor. I'd surmise that the class contains other methods (eg. to do arithmetic) that could cause larger values to be placed into the BigInteger. For example, does it allow two BigIntegers to be multiplied?