请解释一下下面

Question

问题的问题的解决方案：

考虑添加两个n位二进制整数，存储在两个正元件阵列A和B的两个整数的总和应该是问题以二进制形式存储在（n + 1） - 元素数组C中。正式说明问题并编写用于添加两个整数的伪代码。

解决方案：

1. Ç←[1 ... N + 1]▹C是零填充。
2. 对于i←1到n
3. 做总和←A [I] + B [1] + C [i]于
4. C [I]←总和％2
5. C [I + 1]←总和/ 2▹整数除法。
6. C输出

问题：

1. 我认为C [i]为A [1] + B [i]于为什么要补充总和←A [I] + B [我] + C [i]在步骤3？
2. 为什么总和％2（为什么需要在步骤4中使用的模？）
3. 为什么总和/ 2（为什么需要使用部门在步骤5？）

请您上面有真正的解决办法解释例？谢谢。

Answer 1

C既是解决方案又是进位。对于一个真实的例子，让我们添加11 + 3，我会以二进制写在括号小数点）

A = 1011 (11) + B = 0011 (3) [C starts as 00000 (0)] 
    ^   ^     ^

的^ S标志的第一个位置，我们向左走，因为我们读到左到右，但数学从右到左。另外，我们分割整数，所以3/2 = 1，而不是1.5。现在的步骤。

1. sum = 1+1+0 = 10 (2), c[1] = 2 % 2 = 0, c[2] = 2/2 = 1 
2. sum = 1+1+1 = 11 (3), c[2] = 3 % 2 = 1, c[3] = 3/2 = 1 
3. sum = 0+0+1 = 01 (1), c[3] = 1 % 2 = 1, c[4] = 1/2 = 0 
4. sum = 1+0+0 = 01 (1), c[4] = 1 % 2 = 1, c[5] = 1/2 = 0 
^  ^^^       ^
i  A B C, all at position i   note that we store the carry for the NEXT step 

结果：C = 01110（14）

Answer 2

1. 您添加C[i]以及因为C[i]可能包含来自当你在前面的迭代添加A[i-1] + B[i-1] + C[i-1]进位。例如，如果我们做1 + 1，我们的第一次迭代sum = 1 + 1 + 0 = 2，但由于这是二进制的，我们必须携带1并将其放在C[1]上，并将其余部分（2 % 2 = 0）放入C[0]。这给了我们10
2. C[i]得到总和％2，因为A[i] + B[i] + C[i]的总和可能大于1，但1是最适合那个数字的。其余的数额（如果有的话）将被放入进位位。这使我们...
3. C[i+1]得到分配sum/2，因为sum/2是进项金额。当我们为i = i + 1做A[i] + B[i] + C[i]时，它将在下一次迭代中使用。

Answer 3

您可以考虑添加二进制数字的方式与您添加10位数字的方式相同：每个数字都有一个“添加”步骤和一个“携带”步骤。

那么，让我们一次一个地拿数学。假设我们正在添加：

 
101 
+ 
011 

第一步，我们从最右边开始。 （在你的例子中，这对应于i = 1）。我们添加（1 + 1）％2，这给了我们0.真正发生在这里的是什么？ 1 + 1是2，二进制数是两位数（“10”）。我们只能写低位数字（“0”），所以表达总和“mod 2”实际上只是说“现在不用担心结转金额”。所以，我们有：

 
101 
+ 
011 
--- 
    0 (carrying a 1) 

现在我们贯彻 “携带1” 做整数除法（ “总和/ 2”），并暂时将其存储：

 
101 
+ 
011 
--- 
10 

现在我们准备添加第二个数字：（0 + 1）％2 - 但我们必须在继承1中添加我们一直在追踪的内容，因此我们取（0 + 1 + 1）％2产生：

 
101 
+ 
011 
--- 
00 

同样我们需要保持tr进位的ACK，给我们（0 + 1 + 1）= 1：

 
101 
+ 
011 
--- 
100 

最后，我们添加了第三位：（1 + 0 + 1）％2给出了答案：

 
101 
+ 
011 
--- 
1000