Почему бы не использовать комплимент двоих для вычитания в произвольной точности целого числа? - PullRequest
Новая
       58

Почему бы не использовать комплимент двоих для вычитания в произвольной точности целого числа?

0 голосов
/ 26 апреля 2020
Класс BigInteger

Java использует следующий код для вычитания небольшого числа из большего числа: 

    private static int[] subtract(int[] big, int[] little) {
        int bigIndex = big.length;
        int result[] = new int[bigIndex];
        int littleIndex = little.length;
        long difference = 0;

        // Subtract common parts of both numbers
        while (littleIndex > 0) {
            difference = (big[--bigIndex] & LONG_MASK) -
                         (little[--littleIndex] & LONG_MASK) +
                         (difference >> 32);
            result[bigIndex] = (int)difference;
        }

        // Subtract remainder of longer number while borrow propagates
        boolean borrow = (difference >> 32 != 0);
        while (bigIndex > 0 && borrow)
            borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);

        // Copy remainder of longer number
        while (bigIndex > 0)
            result[--bigIndex] = big[bigIndex];

        return result;
    }

Мой вопрос: не будет ли гораздо проще просто выполнить * 1004? * на little без изменения значения знака и добавления его к big? Будет ли это особенно медленно и если да, то почему?

1 Ответ

1 голос
/ 26 апреля 2020

Представление дополнения 2 для n -битных целых чисел фактически является соглашением, что целое число без знака b, равное или большее Math.pow(2,n-1), не представляет сохраненное значение, а вместо этого значение b-(Math.pow(2,n-1)+1), которое является отрицательным , Поскольку компьютеры теперь выполняют арифметику обтекания c (то есть a+b фактически вычисляет (a+b) % Math.pow(2, n), basi c арифметика c дает правильный результат в этом соглашении.

Если вы теперь go для BigIntegers Вы хотите этого избежать. Вам не нужно максимальное целочисленное значение Math.pow(2,n-1)-1, выше которого числа внезапно становятся отрицательными. И вам не нужно переносить арифметику c, вам нужна действительная целочисленная арифматика c. Дополняющие представления двух связаны с указанным диапазоном c доступных целых чисел.

Большие целые числа хранятся в строке «цифр», где цифры над самой старшей, как говорят, равны нулю. Теоретически вы можете найти некоторые творческий способ хранения целых чисел, определяя, что все биты выше самого старшего сохраненного бита должны быть равны самому верхнему сохраненному биту и что все отрицательные числа -b затем сохраняются как Infinity-b или что-то еще, но это сильно усложнит ситуацию во многих отношениях Таким образом, гораздо проще использовать хранилище знаков и величин, даже если оно может Мне нужно немного больше памяти.

...