这就是 + 运算符在 C 中的实现方式吗？

小开

当您添加两位时，结果如下: (真值表)

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 |    0      | 0
0 | 1 |    1      | 0
1 | 0 |    1      | 0
1 | 1 |    0      | 1

所以如果你做位 x 运算，你可以得到不需要进位的和。如果你按位计算，你就可以得到进位。

将此观察扩展到多位数字 a和 b

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
= a^b + ((a&b) << 1)

一旦 b是 0:

a+0 = a

所以算法归结为:

Add(a, b)
if b == 0
return a;
else
carry_bits = a & b;
sum_bits = a ^ b;
return Add(sum_bits, carry_bits << 1);

如果你去掉递归，把它转换成一个循环

Add(a, b)
while(b != 0) {
carry_bits = a & b;
sum_bits = a ^ b;


a = sum_bits;
b = carrry_bits << 1;  // In next loop, add carry bits to a
}
return a;

考虑到上述算法，代码的解释应该更简单:

int t = (x & y) << 1;

进位。如果两个操作数右边的1位都是1，那么进位就是1。

y ^= x;  // x is used now

没有进位的加法(进位被忽略)

x = t;

重用 x 来设置它进行

while(x)

当有更多的进位时重复

递归实现(更容易理解)应该是:

int add(int x, int y) {
return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

这个函数似乎演示了 + 在背景

没有。整数加法转换为指令加法。这只是演示了一个使用按位 xor 和 and 的替代实现。

小开

为了显得迂腐，C 规范没有指定增加 怎么做。

但是实际上，小于或等于 CPU 单词大小的整数类型的 +操作符被直接转换成 CPU 的加法指令，较大的整数类型被转换成多个加法指令，还有一些额外的位来处理溢出。

CPU 内部使用逻辑电路来实现加法，而不使用循环、位移或任何与 C 工作方式非常相似的东西。

小开

几乎所有能够运行已编译 C 代码的现代处理器都内置了对整数加法的支持。您发布的代码是一种聪明的方法，可以在不执行整数加法操作码的情况下执行整数加法，但它不是通常执行整数加法的方式。实际上，函数链接可能使用某种形式的整数加法来调整堆栈指针。

您发布的代码依赖于这样一种观察: 当添加 x 和 y 时，您可以将它们分解为它们共有的位和对 x 或 y 之一唯一的位。

表达式 x & y(按位 AND)给出 x 和 y 的公共位。表达式 x ^ y(按位排斥 OR)给出了对 x 或 y 之一唯一的位。

x + y的和可以重写为它们共有位的两倍(因为 x 和 y 都贡献了那些位)加上对 x 或 y 唯一的位的和。

(x & y) << 1是它们共有位的两倍(左移1有效地乘以2)。

x ^ y是对 x 或 y 之一唯一的位。

因此，如果我们用第一个值替换 x，用第二个值替换 y，求和应该是不变的。您可以将第一个值视为位加法的载体，将第二个值视为位加法的低阶位。

这个过程一直持续到 x 为零，此时 y 保持总和。

小开

这个函数似乎演示了 + 如何在后台实际工作

不，这被翻译成原生的 add指令，它实际上使用的是硬件加法器，在 ALU中。

如果你想知道计算机如何加法，这里有一个基本的加法器。

计算机中的一切都是通过逻辑门完成的，逻辑门主要由晶体管构成。完整的加法器里有半加法器。

有关逻辑门和加法器的基本教程，请参阅这个。视频非常有帮助，虽然很长。

在这个视频中，显示了一个基本的半加法器。如果你想要一个简短的描述，这就是它:

半加法器的两位加法。可能的组合如下:

加0和0 = 0

加1和0 = 1

加1和1 = 10(二进制)

那么半加法器是如何工作的呢？它由三个逻辑门组成，分别是 and，xor和 nand。如果两个输入都是负的，那么 nand 给出一个正电流，这意味着解决了0和0的情况。xor给出一个正的输出，其中一个输入是正的，另一个是负的，这意味着它解决了1和0的问题。只有当两个输入都为正时，and才会给出正的输出，这样就解决了1和1的问题。所以基本上，我们现在得到了半加法器。但是我们仍然只能添加部分。

现在我们要做全加法器了。完全加法器包括一次又一次地调用半加法器。现在这个有一个携带。当我们把1和1加起来，我们得到一个进位1。全加法器所做的就是，它从半加法器获取进位，存储它，并将它作为另一个参数传递给半加法器。

如果你不知道如何传递进位，你基本上先用半加法器加上位，然后再加上和和和进位。现在你已经加上了进位，加上了两个位。所以你一遍又一遍地这样做，直到你必须添加的位结束，然后你得到你的结果。

惊讶吗？事情就是这样发生的。这看起来像是一个漫长的过程，但是计算机可以在几分之一纳秒内完成，或者更具体地说，在半个时钟周期内完成。有时甚至在一个单一的时钟周期内执行。基本上，计算机有 ALU(CPU的主要组成部分)、内存、总线等。.

如果你想学习计算机硬件，从逻辑门，内存和 ALU，并模拟一台计算机，你可以看到这个课程，从中我学到了这一切: 从第一原则构建现代计算机

它是免费的，如果你不想要一个电子证书。课程的第二部分将于今年春季开课

小开

如果代码分解对其他人有帮助，那么就以 x=2, y=6为例:

x不等于零，因此开始向 y中添加:

while(2) {

因为

        x: 0 0 1 0  //2
y: 0 1 1 0  //6
x&y: 0 0 1 0  //2

因为 << 1将所有位移到左边:

      x&y: 0 0 1 0  //2
(x&y) <<1: 0 1 0 0  //4

总之，将结果 4隐藏在 t中，并使用

int t = (x & y) <<1;

现在应用按位异或(XOR) y^=x:

        x: 0 0 1 0  //2
y: 0 1 1 0  //6
y^=x: 0 1 0 0  //4

最后，通过重新设置 x=t和返回到 while循环的开始:

x = t;

当 t=0(或者，在循环的开始，x=0) ，以

return y;

小开

我的问题是: + 操作符是作为贴在 MOST 实现上的代码实现的吗？

让我们回答实际的问题。所有运算符都由编译器实现为某种内部数据结构，经过某些转换后最终转换为代码。你不能说什么代码将被一个单一的添加生成，因为几乎没有现实世界的编译器生成代码的个别语句。

编译器可以自由地生成任何代码，只要它的行为是好像，实际操作是根据标准执行的。但实际发生的情况可能完全不同。

举个简单的例子:

static int
foo(int a, int b)
{
return a + b;
}
[...]
int a = foo(1, 17);
int b = foo(x, x);
some_other_function(a, b);

这里不需要生成任何加法指令，编译器完全可以将其转换为:

some_other_function(18, x * 2);

或者，编译器可能注意到您在一行中调用函数 foo几次，这是一个简单的算术，它将为函数生成向量指令。或者加法的结果稍后用于数组索引，并且将使用 lea指令。

您不能简单地讨论操作符是如何实现的，因为它几乎从不单独使用。

小开

C 使用抽象机器来描述 C 代码的功能。因此没有指定它是如何工作的。例如，有些 c“编译器”实际上将 c 编译成一个脚本语言。

但是，在大多数 C 实现中，小于计算机整数大小的两个整数之间的 +将被转换成汇编指令(经过许多步骤)。汇编指令将被翻译成机器代码并嵌入到可执行文件中。汇编语言是一种从机器代码中“移除一步”的语言，其目的是比一堆打包的二进制文件更容易阅读。

该机器代码(经过许多步骤)然后由目标硬件平台进行解释，其中由 CPU 上的指令解码器进行解释。该指令解码器接收指令，并将其转换为信号，沿“控制线”发送。这些信号将数据从寄存器和内存路由到 CPU，这些数据通常在一个算术逻辑单元中被加在一起。

算术逻辑单元可能有单独的加法器和乘法器，或者可能将它们混合在一起。

算术逻辑单元有一堆晶体管，它们执行加法运算，然后产生输出。所述输出通过指令解码器产生的信号进行路由，并存储在存储器或寄存器中。

晶体管在算术逻辑单元和指令解码器(以及我忽略的部分)中的布局被蚀刻在工厂的芯片上。蚀刻模式通常是通过编译一种硬件描述语言来产生的，该语言抽象出什么与什么相连以及它们如何操作，并生成晶体管和互连线。

硬件描述语言可以包含移位和循环，这些移位和循环不描述发生的事情 迟早的事(像一个接一个) ，而是 在太空中——它描述硬件不同部分之间的连接。所述代码可能看起来非常模糊地像您在上面发布的代码。

上面的修饰覆盖了许多零件和图层，并且含有不准确的地方。这既是因为我自己的能力不足(我既写过硬件也写过编译器，但两者都不是专家) ，也因为完整的细节需要一两个职业生涯，而不是一个 SO 职位。

这里是一个关于8位加法器的 SO 帖子。给你是一个非 SO 的帖子，你会注意到一些加法器只是在 HDL 中使用 operator+！(HDL 本身能够理解 +并为您生成较低级别的加法器代码)。

小开

您找到的代码试图解释非常原始的计算机硬件 也许吧如何实现“添加”指令。我说“可能”是因为我可以保证任何 CPU 不使用这个方法，我将解释原因。

在正常生活中，你使用十进制数并且你已经学会了如何加法: 要加两个数，你要加最小的两位数。如果结果小于10，则写下结果并继续到下一个数字位置。如果结果是10或更多，你写下结果 -10，进入下一个数字，买你记得再加1。例如: 23 + 37，加3 + 7 = 10，写下0，记住下一个位置再加1。在10的位置，加上(2 + 3) + 1 = 6，然后写下来。结果是60。

你可以对二进制数做同样的事情。区别在于，唯一的数字是0和1，所以唯一可能的和是0,1,2。对于32位数字，您将处理一个数字位置后，其他。这就是真正原始的计算机硬件所能做到的。

这个代码的工作原理不同。你知道两个二进制数字的和是2如果两个数字都是1。所以如果两个数字都是1，那么在下一个二进制位置再加1，然后写下0。这就是 t 的计算过程: 它找到所有二进制数字都是1(即 &)的位置，并将它们移动到下一个数字位置(< < 1)。然后做加法: 0 + 0 = 0,0 + 1 = 1,1 + 0 = 1,1 + 1是2，但我们写下0。这就是独占或操作员的工作。

但所有的1，你必须处理在下一个数字位置没有处理。他们仍然需要被添加。这就是代码执行循环的原因: 在下一次迭代中，所有额外的1都会被添加。

为什么没有处理器这样做呢？因为它是一个循环，处理器不喜欢循环，而且速度很慢。它很慢，因为在最坏的情况下，需要32次迭代: 如果将1加到数字0xffffff (321-bit) ，那么第一次迭代将清除 y 的位0，并将 x 设置为2。第二次迭代清除 y 的第1位并将 x 设置为4。诸如此类。需要32次迭代才能得到结果。然而，每次迭代都必须处理 x 和 y 的所有位，这需要很多硬件。

原始处理器的处理速度和十进制算法一样快，从最低位到最高位。它也需要32个步骤，但是每个步骤只处理前一个位位置的两位加一个值，因此实现起来要容易得多。即使是在原始计算机中，也可以不用实现循环就能完成这项工作。

一个现代、快速和复杂的 CPU 将使用“条件和加法器”。特别是如果位数很高，例如64位加法器，它节省了很多时间。

一个64位的加法器由两部分组成: 首先，一个32位的加法器为最低的32位。那个32位加法器产生一个和和和一个“进位”(一个指示器，一个1必须添加到下一个位位置)。其次，两个32位的加法器，一个加 x + y，另一个加 x + y + 1。所有三个加法器并行工作。然后，当第一个加法器产生它的进位时，CPU 只需选择两个结果 x + y 或 x + y + 1中的哪一个是正确的，就得到了完整的结果。所以64位加法器只比32位加法器长一点点，而不是两倍。

32位加法器部分再次实现为条件和加法器，使用多个16位加法器，16位加法器是条件和加法器，等等。

小开

仅仅出于兴趣，在 Atmega328P 处理器上，使用 avr-g + + 编译器，下面的代码通过减去 -1来实现加1:

volatile char x;
int main ()
{
x = x + 1;
}

生成的代码:

00000090 <main>:
volatile char x;
int main ()
{
x = x + 1;
90:   80 91 00 01     lds r24, 0x0100
94:   8f 5f           subi    r24, 0xFF   ; 255
96:   80 93 00 01     sts 0x0100, r24
}
9a:   80 e0           ldi r24, 0x00   ; 0
9c:   90 e0           ldi r25, 0x00   ; 0
9e:   08 95           ret

特别要注意的是，添加是通过 subi指令(从 register 中减去常量)完成的，在本例中，其中0xFF 实际上是 -1。

另外值得注意的是，这个特殊的处理器没有 addi指令，这意味着设计人员认为，编译器编写人员可以充分地处理减去补语的操作。

这是否利用了两者的互补性或其他与实现相关的特性？

可以公平地说，编译器编写人员会尝试以最有效的方式实现所需的效果(将一个数字添加到另一个数字中) ，这对于特定的架构来说是可能的。如果这需要减去补数，那就这样吧。