Вычитание двух целых чисел по цифрам

Недавно мне была дана программирующая головоломка, на которую я не могу на всю жизнь найти удовлетворительный ответ: вычислите сумму двух произвольно больших целых чисел, заданных строками, где второе целое число может быть отрицательным. Это должно было быть сделано на Java без использования каких-либо классов BigInteger, BigNumber и т.д.

В псевдокоде мой первоначальный подход заключался в следующем:

  • Если первый символ второй строки равен "-", установите флаг вычитания.
  • Преобразование каждой строки в массив целых чисел, по одному для каждой цифры.
  • Расширьте кратчайший массив и левый блок с нулями, чтобы оба массива имели одинаковый размер.
  • Пронумеруйте каждый индекс массивов (от младшей значащей цифры до самой значащей цифры), выполнив сложение/вычитание и используя перенос для переноса переполнения на следующую цифру.
  • Проверьте перенос, чтобы добавить последние цифры.

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

Мой текущий алгоритм для шагов 4 и 5 выглядит следующим образом:

int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
    int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);
    newDigit += carry;
    if (newDigit >= 10) {
        carry = 1;
        newDigit -= 10;
    } else if (newDigit < 0) {
        carry = -1;
        newDigit += 10;
    } else {
        carry = 0;
    }
    result[i] = newDigit;
}
// Convert result back into a string.
String resultString = intArrayToString(result);
// Apply carry.
if(carry == 1) {
    return "1" + resultString;
} else if(carry == -1) {
    return "-" + resultString;
} else {
    return resultString;
}

Ответы

Ответ 1

Если знак отрицательный, а number2 больше числа 1, вы можете просто заменить эти целые массивы.

Вы можете попробовать что-то вроде этого:

boolean swap = false;
for(int j = 0; j < number1.length && negative; j++){
    if(number2[j] > number1[j]){
        swap = true;                
        int temp[] = number1;
        number1 = number2;
        number2 = temp;
        break;
    } else if(number1[j] > number2[j]){
        break;
    }
}

int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
    int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);

    newDigit += carry;
    if (newDigit >= 10) {
        carry = 1;
        newDigit -= 10;
    } else if (newDigit < 0) {
        carry = -1;
        newDigit += 10;
    } else {
        carry = 0;
    }
    result[i] = newDigit;
}

// Convert result back into a string.
String resultString = "";
for(int j = 0; j <result.length; j++){
    resultString += (result[j] + "");
}

// Apply carry.
if(carry == 1) {
    return "1" + resultString;
} else if(carry == -1 || swap) {//if swap is set sign is - 
    return "-" + resultString;
} else {
    return resultString;
}

Ответ 2

Если последний перенос равен -1, значит, вам нужно добавить -1 * 10^(number of digits) в ответ.

 01
-10
---
 91

И Carry = -1. Следовательно, вы должны добавить -100 в 91, чтобы получить фактический ответ.

Решение состоит в том, чтобы просто вычесть меньшее число из большего числа, а затем добавить знак соответствующим образом.

Ответ 3

Вы можете обернуть его с помощью:

if(A>=B):
    calculate A-B
else:
    calculate -(B-A)

Ответ 4

Удостоверьтесь, что при вычитании большее число находится в номере1, иначе вы получите нечетные ответы. При необходимости переключитесь на номер 1 и номер2 и учтите отрицательный результат при необходимости. В противном случае выглядит хорошо для меня.

Итак, например, 1 + -10 должно быть 10 - 1, а отрицательный результат - -9.

Ответ 5

Хорошо, вы могли бы просто переключить знак +/-.

Например, если num1 = 1, num2 = -10, вместо выполнения (1-10) и get -9, вы можете попробовать сделать - (10-1). потому что кажется, что ваш алгоритм может нормально работать, если num1 = 10 и num2 = -1.

Итак, в основном вы бы переключили num2 с num1, если он имеет большую величину, чем num1, и отрицает конечный результат.

* Хорошо, кто-то сделал код, пока я комментировал.