13

问题：

考虑将两个 n 位二进制整数相加的问题，存储在两个 n 元素数组 A 和 B 中。两个整数的和应以二进制形式存储在 (n + 1) 元素数组 C 中。说明问题正式并编写用于添加两个整数的伪代码。

解决方案：

  1. C ← [1 ... n + 1] ▹ C 是零填充的。
  2. 对于 i ← 1 到 n
  3. 求和 ← A[i] + B[i] + C[i]
  4. C[i] ← 总和 % 2
  5. C[i + 1] ← sum / 2 ▹ 整数除法。
  6. 输出 C

问题：

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

你能用真实的例子解释一下上述解决方案吗？谢谢。

4

3 回答 3

20

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)

于 2011-04-10T05:56:46.930 回答
5
  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]得到 sum % 2 因为总和A[i] + B[i] + C[i]可能大于 1，但 1 是最适合该数字的。其余的总和（如果有的话）将被放入进位位。这让我们...
  3. C[i+1]被分配sum / 2，因为sum / 2是套利金额。A[i] + B[i] + C[i]当我们执行for时，它将在下一次迭代中使用i = i + 1。
于 2011-04-10T05:57:39.807 回答
5

您可以像添加以 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

最后我们添加第 3 位：(1+0+1)%2 给出答案：

101
 +
 011
 ---
1000
于 2011-04-10T05:59:39.660 回答