Переполнение и переполнение BigIntegers в C#

Question

У меня есть следующий фрагмент кода, который я пытаюсь понять.

Класс BigInteger (пользовательский, а не стандартный) имеет следующие члены:

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

Конструктор выглядит следующим образом:

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

По сути, класс Big Integer помогает манипулировать большими целыми числами. Конструктор используется для присвоения длинного значения объекту Big Integer. Я понимаю, что переменная с именем value копируется в массив данных uint[] (максимально допустимое количество цифр - maxLength).

Я не могу полностью понять, как была сделана проверка на переполнение и переполнение. Я понимаю, что условия if(tempVal > 0) и другие if(tempVal < 0), но почему самый высокий индекс массива данных имеет значение 0x80000000 в случае как переполнения, так и переполнения? (почему не 0xFFFFFFFF в случае переполнения / недостаточного заполнения? Если число будет даже на 1 больше / меньше максимально допустимого значения, это приведет к переполнению / недостаточному заполнению)

Кроме того, не передается ли длинное значение конструктору, ограничивает общий размер BigInteger (чье максимальное значение может тогда быть таким же, как максимальное значение длинной переменной)?

Answer 1

Для int в C# бит в 0x80000000 (то есть самый старший бит) является знаковым битом. Другими словами, если оно содержит 1, то число является отрицательным. Int, содержащий биты 0xffffffff, будет интерпретирован как содержащий -1. Во время целочисленной арифметики число, переносимое в этот бит, будет представлять собой условие переполнения, которое, по-видимому, лежит в основе проверки.

Аналогично, бит знака содержит 0 для любого положительного числа, поэтому, если вы ожидаете, что число будет отрицательным, но этот бит содержит 0, то вы знаете, что в этот бит должно было произойти некоторое переполнение. На самом деле, как представлены отрицательные числа, каждый бит слева от фактического числа установлен на 1. Например, 3 представлен как 0x00000003 (все слева - 0), а -3 представлен как 0xfffffffd (все до слева 1).

Код будет в основном заполнять весь массив с тем же соглашением. Сохраните в нем положительное число, и оно заполнит первые пару элементов, оставив все остальное обнуленным. Передайте отрицательное число, и оно поместит число в первую пару элементов, а затем заполнит почти весь массив 0xffffffff, тем самым сохранив соглашение о том, что самый левый бит (т.е. самый левый бит последнего элемента массив) является знаковым битом. Заполнение всего массива после числа с помощью -0xffffffff происходит потому, что оператор смещения вправо в C# сохраняет бит знака: если он смещает вправо отрицательное число, он заполняет все влево 1, а не 0.

Таким образом, способ думать об этих тестах состоит в том, что они проверяют правильность знакового бита массива (крайний левый бит последнего элемента).

Между прочим, я не верю, что есть какое-либо условие исключения, поэтому я подозреваю, что эти тесты могли быть вставлены в целях отладки во время написания кода, а затем оставлены.

Мое чтение кода состоит в том, что вы правы, когда предлагаете передать длинное значение в конструктор, что ограничивает общий размер значения, хранящегося в BigInteger. Тем не менее, вы только показали код для конструктора. Я предполагаю, что класс содержит другие методы (например, для выполнения арифметики), которые могут привести к тому, что большие значения будут помещены в BigInteger. Например, позволяет ли он умножить два BigInteger?