请向我解释下面问题的解决方案

Question

问题:

考虑添加两个n位二进制整数的问题,存储在两个n元素数组A和B中.两个整数之和应以二进制形式存储在(n + 1) - 元素数组C中.说明问题正式并写入伪代码以添加两个整数.

解:

1. C←[1 ... n + 1]▹C为零填充.
2. 因为我←1到n
3. 总和←A [i] + B [i] + C [i]
4. C [i]←sum%2
5. C [i + 1]←sum /2▹整数除法.
6. 输出C.

题:

1. 我认为C [i]是A [i] + B [i]你为什么要在步骤3中加上总和←A [i] + B [i] + C [i]？
2. 为什么总和%2(为什么需要在步骤4中使用模数？)
3. 为什么sum/2(为什么需要在步骤5中使用除法？)

能用真实的例子解释上面的解决方案吗？谢谢.

Answer 1

C既是解决方案又是进位.对于一个真实的例子,让我们添加11 + 3.我将用二进制写入parens中的十进制数)

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是持有金额.这将在未来的迭代中使用时,我们做A[i] + B[i] + C[i]了i = i + 1.

Answer 3

您可以想到添加二进制数字的方式与添加基数10的方式相同：每个数字都有一个“加”步骤和一个“进位”步骤要执行。

因此，让我们一次进行一次数学运算。假设我们要添加：

101
+
011

第一步，我们从最右边开始。（在您的示例中，这对应于i = 1）。我们加上（1 + 1）％2，得到0。这到底是怎么回事？1 + 1是2，其二进制形式是两位数字（“ 10”）。我们只能写低位数字（“ 0”），所以表达和“ mod 2”实际上只是说“现在不用担心结转和”。所以我们有：

101
+
011
---
  0（携带1）

现在，我们通过进行整数除法（“ sum / 2”）并临时存储来实现“携带1”：

101
+
011
---
 10

现在我们准备添加第二个数字：（0 + 1）％2-但我们必须添加一直跟踪的结转1，所以我们取（0 + 1 + 1）％2产生：

101
+
011
---
 00

再次，我们需要跟踪进位，给我们（0 + 1 + 1）= 1：

101
+
011
---
100

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

 101
 +
 011
 ---
1000