4

我需要添加 2 个无符号数字 'a' 和 'b' 。

我找到了以下代码，使用位操作

unsigned int add (unsigned int a,unsigned int b)
{
    unsigned int carry, sum;
    if (b == 0)
    {
        return a;
    }

    sum = a ^ b; // xor takes sum
    carry = a & b; // collect carry;
    carry = carry << 1;
    return ( add (sum, carry) );
}

我不知道这段代码是如何添加两个数字的。

任何帮助/指导的人。

4

5 回答 5

6

逻辑：代码实现了一系列半加器，并通过递归将进位从其中一个传播到下一个。有关其工作原理的示例，请参见试运行。

考虑这两个值a=0011和b=0101。以 10 为基数，它们分别是a=3和b=5。

现在，a^b=0110（1仅当一位为1）而a&b=0001（1仅当两位为一位时，您可以进行进位的唯一情况）。

然后，您需要将进位移动到下一位，这就是您进行<<1操作的原因，制作carry=0010.

现在您需要添加0110并0010使用上述算法。这将变成添加0100和0100。which 将导致添加0000with 1000which 将导致添加1000with 0000which 将通过基本情况 ( b == 0) 结束。

以表格形式：

|   a  |   b  | a^b  |  a&b | carry|
------------------------------------
| 0011 | 0101 | 0110 | 0001 | 0010 |
| 0110 | 0010 | 0100 | 0010 | 0100 |
| 0100 | 0100 | 0000 | 0100 | 1000 |
| 0000 | 1000 | 1000 | 0000 | 0000 |
| 1000 | 0000 | ---- | ---- | ---- |

最后一行是基本情况。

于 2013-09-10T13:46:35.727 回答
3

问题中的位操作代码使用两个基本原则：半加法器和加法是可交换的事实。

一个半加器将两位相加，没有进位。如果恰好有一个输入为 1，则单个位相加结果为 1，如果输入相等，则为 0。这由xor代码中的按位表示。

即使在这样做之后，您也需要处理进位。如果两个位都为 1，则从位位置执行的进位为 1，否则为 0。这由 bitwise 的组合表示，and随后shift将进位移动到需要添加的位位置。

递归调用 add 应用进位，使用加法是可交换的事实。进位是与初始添加一起逐位添加还是在后续步骤中批量添加都没有关系。

添加进位可能会导致新的进位。这是通过继续递归调用来处理的，直到 add 没有进位。

必须达到递归基本情况零进位，因为在零进位的情况下加零不会导致进位。如果k在一次进位加法中进位的最低有效位全为零，k+1则下一个进位的最低有效位必须为零。

于 2013-09-10T14:01:56.833 回答
3

请记住这一点：

2003 标准 C++ 5.3.1c7：

无符号量的负数是通过从 2^n 中减去其值来计算的，其中 n 是提升操作数中的位数。

a+b = a - (-b)将在符合 2003 标准（顺便说一下 C++11）的 C++ 编译器中工作。

当然，我会赞成一个符合早期标准的答案（例如，C++99 where -unsignedis undefined）。

于 2013-09-10T13:45:11.223 回答
1

要理解为什么该函数实际上确实添加了两个数字，查看真值表以添加两位是有帮助的：

a = 0, b = 0 -> a + b = 00
a = 0, b = 1 -> a + b = 01
a = 1, b = 0 -> a + b = 01
a = 1, b = 1 - > a + b = 10

您会看到，低位是两个输入位的 XOR，而高位是两个输入位的 AND，因此最终结果由 (a XOR b) OR ((a AND B) << 1) 表示。由于此函数添加了 32 位数字，因此您不能再简单地对结果进行 OR，因为在组合 XOR 和 AND 运算的结果时，一些额外的进位位可能出现在较高的数字中，这就是您必须递归应用该函数的原因。

顺便说一句，这几乎是在硬件中完成数字相加的方式。

于 2013-09-10T13:59:47.337 回答
0

这是硬件实现加法的方式。位加法的结果是位的异或（^C++ 中的运算符）；这就是你得到的sum。但这没有考虑低位的任何进位。进位是位（&运算符）的和，它为您提供 的初始值carry。但是第 n 位的进位是第 n + 1 位的进位，所以我们左移，将第 n 位移动到第 n + 1 位，然后将其相加。

我们使用递归来添加它，因为如果在添加进位之前的结果（在位级别）是1，并且进位是1，那么也会有一个进位。

递归结束的原因有点微妙（当然，硬件版本不递归，而是添加了额外的逻辑）。这通过考虑原始值最容易评估：

a   b   carry_in  sum carry_out

0   0       0      0      0
1   0       0      1      0
0   1       0      1      0
1   1       0      0      1
0   0       1      0      0
1   0       1      1      1
0   1       1      1      1
1   1       1      0      1

（“sum”列是 的结果a ^ b，没有进位。）

在第一次递归调用中，b 的第 0 位将为 0（因为它表示低位的进位进位，并且没有一个 - 或者因为<<，它将第 n 位的进位输出移动到第 n 位的进位进位 + 1）。当然，第 0 位的进位为 0。所以对于第 0 位在第一次递归调用中，只能出现前两行。这意味着不会有进位输出，并且对于下一次递归，只有前两行与位 0 和 1 相关。换句话说，每个递归有效地从传播的进位中消除了一个集合位，结果传播的进位进位最终必须变为 0。由于它作为参数 b 传播，因此参数 b 最终必须变为 0。

于 2013-09-10T14:23:57.830 回答