按位數減去兩個整數

我最近被給了一個編程難題，我不能爲我的生活找到一個滿意的答案：計算由字符串給出的兩個任意大整數的總和，其中第二個整數可能爲負數。這將在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; 
}

來源

2014-01-21 DanielGibbs

你能舉一個例子輸入和一個錯誤的輸出例子嗎？ –

當然。當number1是'1'而number2是'-10'時，我當前的算法給出了-91'。 – DanielGibbs

在紙上試一下簡單的例子：11-3。我們會這樣做：3 + 8 =（1）1，所以寫8，保留一個。然後進行+ 1 = 1，無事可做。你的算法正在做非常不同的事情。 – PMF

如果符號爲負，數字2比NUMBER1大，你可以簡單地掉那些整數數組。

你可以嘗試這樣的事情：

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; 
}

來源

2014-01-21 06:42:58 chathux

如果最後提的是-1，那麼就意味着你必須添加-1 * 10^(number of digits)答案。

01 
-10 
--- 
91

And Carry = -1。因此，你必須添加-100到91才能得到實際的答案。

解決方法是簡單地從較大的數字中減去較小的數字，然後相應地添加符號。

來源

2014-01-21 05:56:15

沒錯，但我該如何做數位數字？我不能對整個數字進行操作，因爲它的長度是任意的。 – DanielGibbs

您可以通過比較數字來檢查哪個數字更大。如果數字的位數相同，則比較數位。用'1'和'-10'做的 –

確保在做減法運算時，較大的數字在number1中，否則您會得到奇怪的答案。如果需要，切換編號1和編號2並根據需要考慮負數。否則對我來說看起來沒問題。

因此，例如1 + -10應該是10 - 1，而結果的負值-9。

來源

2014-01-21 05:57:16 ansible

看起來很容易。想象一下，如果（A> = b）和B是-ve，數字是'12352432'和'-345231234' – Baby

你可以把它包：

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

來源

2014-01-21 05:59:02 ElKamina

，我們需要執行ADD（A，B）。 –

那麼你可能只是切換+/-號。

例如，如果num1 = 1，num2 = -10，而不是做（1-10）並得到-9, ，您可以嘗試 - （10-1）來代替。因爲看起來你的算法可以正常運行，如果num1 = 10，並且num2 = -1。

所以基本上你會用num1切換num2，如果它的幅度大於num1，並且否定最終結果。

* 好的，有人在我評論時做了代碼。

來源

2014-01-21 06:45:31 rtyusolf

按位數減去兩個整數

回答

相關問題