这是C语言中加号运算符的实现方式吗？

Question

当理解C语言中原始运算符如+, -, *和/的实现方式时，我从一个有趣的回答中发现了以下代码片段。

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

这个函数似乎展示了+在后台是如何工作的。然而，对我来说太难理解了。我一直以为这样的操作是由编译器生成的汇编指令来完成的!

+运算符是否像MOST实现中发布的代码一样实现？这是否利用了二进制补码或其他与实现相关的特性？

- nalzok

---

我猜大多数实现会使用本地的add机器指令，这个指令几乎所有的CPU都有，并且作为硬件加法器实现，在几个时钟周期内完成运算。 - MikeCAT

“+”运算符很可能利用了实现定义的特性，这些特性被称为“机器语言”和“CPU”。你有什么问题吗？如果你想了解表达式是如何转换为机器码的，请阅读关于编译器构建的文章。 - too honest for this site

大多数加法操作将被编译为一些机器码的加指令变体（或组合）。你的代码在任何现实场景下都是复杂和无用的，但它可以用来教授有关二进制操作的知识。 - Anders Marzi Tornblad

虽然这并不是C语言的实现方式（请参见下面的答案），但它非常接近涉及电路在最低层级别上执行加法的方式。试着用纸和笔计算小的二进制值（比如3或4位字节），看看它是怎么工作的。现在想象一下电路是如何通过电脉冲来执行相同的操作的。再想象一下并行处理所有位，而不是循环处理。现在你已经准备好构建一个1940年代的计算机了:D - Jon Hanna

除非你能生产出一款没有加法指令的CPU，否则在任何实现中都不会以那种方式实现。你发布的代码说明了CPU在硬件上的操作。 - user207421

Answer 1

严格来说，C规范并没有规定加法应该如何实现。

但实际上，在CPU字长不大于整型大小的情况下，整型加法运算符+会被直接翻译成CPU的加法指令；对于更大的整数类型，则会被翻译成多个加法指令以处理溢出位。

CPU内部使用逻辑电路来实现加法，而不是使用循环、位移或任何类似于C语言的操作。

- orlp

---

这个回答非常优秀，因为它表达得非常清晰简明。我并不觉得它过于学究，仅仅是对问题的恰到好处的解释。 - Jeremy Anderson

实际上，CPU逻辑电路可以从硬件描述语言(HDL)中编译出来。你可能会使用循环和位移等方式生成一个加法器，这与原帖的建议有些相似，但仅局限于某种程度。 这些循环和位移将描述硬件的布局以及它们之间的连接方式。然而，在顶级硬件中，有人可能会展开这些循环和位移，甚至为像加法器这样的性能关键部分手动设计电路，而不再使用HDL。 - Yakk - Adam Nevraumont

一个线性加法器电路可以完全展开循环（32次）并在硬件中执行，它所做的正是那段C代码的功能。 - usr

@usr 不仅展开，而且每个“步骤”都同时发生。 - OrangeDog

一个简单的硬件加法器会像这个C代码一样，通过进位进行传递，从而限制并行性。高性能加法器可能会使用进位预测电路来减少这种情况。 - plugwash

Answer 2

当你将两个位相加时，以下是结果：（真值表）

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

如果进行按位异或操作，您可以获得没有进位的和。如果进行按位与操作，则可以获得进位位。

将此观察扩展到多比特数 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。

y ^= x;  // x is used now

无进位加法（忽略进位位）

x = t;

将 x 重复利用，以设置它为 carry。

while(x)

只要有更多进位位，就重复执行

---

一个递归实现（更易理解）是：

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

这个函数似乎展示了+在后台的实际工作方式

不是。通常（几乎总是）整数加法会被翻译成机器指令 add。这只是演示了一种使用位异或和与的替代实现。

- Mohit Jain

---

我认为这是最好的答案，其它回答只是说明通常会被翻译成单一指令，但这个答案不仅如此，还解释了给定函数的作用。 - Nick Sweeting

@NickSweeting 谢谢。这个问题可能有两种解释方式，我认为被接受的答案正确地解释了 OP 想要问的内容。 - Mohit Jain

Answer 3

似乎这个函数展示了+在后台是如何工作的。

不是，这被翻译为本地的add机器指令，实际上使用了ALU中的硬件加法器。

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

计算机中的所有操作都是使用逻辑门完成的，这些门大多由晶体管组成。全加器中包含半加器。

有关逻辑门和加法器的基本教程，请参见this。该视频非常有帮助，但很长。

在那个视频中，展示了一个基本的半加器。如果您需要简要描述，这就是它：

半加器将给定的两个位相加。可能的组合为： - 添加0和0= 0 - 添加1和0= 1 - 添加1和1= 10（二进制）

现在半加器是如何工作的呢？它由三个逻辑门组成，即“与”门、 “异或” 门和 “与非” 门。当两个输入都为负时，“与非” 门输出正电流，这意味着它解决了 0 和 0 的情况。当一个输入为正、另一个输入为负时，“异或” 门输出正电流，这意味着它解决了 1 和 0 的问题。只有当两个输入都为正时，“与” 门才会输出正电流，这解决了 1 和 1 的问题。所以，我们现在已经得到了半加器。但我们仍然只能相加位。

现在我们制作全加器。全加器由一次次调用半加器构成。现在这有一个进位。当我们相加 1 和 1 时，我们得到一个进位 1。因此，全加器的作用是从半加器中获取进位、存储并将其作为另一个参数传递给半加器。

如果你对如何通过进位感到困惑，你首先要使用半加器添加比特，然后再将和与进位相加。这样，你就已经将进位与两个比特相加了。所以你需要一遍又一遍地重复这个过程，直到需要相加的比特用完为止，然后你就得到了结果。

惊讶吗？其实就是这样。看起来像是一个长过程，但计算机可以在纳秒的时间内完成，更具体地说，在半个时钟周期内完成。有时甚至在单个时钟周期内执行。基本上，计算机有ALU（CPU的主要组成部分）、存储器、总线等。

如果你想学习计算机硬件，包括逻辑门、存储器和ALU，并模拟计算机，你可以参加这个课程，我就是从中学到了所有这些：Build a Modern Computer from First Principles。

如果你不需要电子证书，它是免费的。该课程的第二部分将于今年春季推出。

- Box Box Box Box

---

几毫秒？为了一次加法？ - JAB

两个寄存器值的加法通常在一个时钟周期内完成。 - Cody Gray

尝试一些纳秒的分数。如果我没记错，最近英特尔处理器上的寄存器加操作需要一个时钟周期，所以在几个GHz的时钟速度下......而这还不包括流水线、超标量执行等因素。 - jamesqf

这个连锁进位加法器会增加太多的延迟，因此在硬件中甚至没有这种实现方式。 - pipe

涟漪进位加法器已经几十年没有被CPU使用了，因为它太慢了。相反，它们使用更复杂的加法器，在一个时钟周期内就能完成任务（甚至在一些英特尔双时钟ALU中只需要半个周期）。 （好吧，大多数CPU都不使用它。低端嵌入式CPU可能仍然会使用它来降低晶体管计数。） - Mark

Answer 4

C使用抽象机器来描述C代码的执行过程，具体实现没有被明确说明。例如，有一些C“编译器”可以将C代码编译成脚本语言。

但是，在大多数C实现中，两个整数相加并且小于机器整数大小，会被翻译成一个汇编指令（经过多个步骤）。该汇编指令将被转换成机器码并嵌入您的可执行文件中。汇编语言是一种“距离二进制代码只有一步之遥”的语言，旨在比一堆紧密打包的二进制代码更易读。

那么这些机器码（经过多个步骤）会被目标硬件平台解释，它们会被CPU上的指令解码器进行解释。这个指令解码器接收该指令，并将其转换为要沿着“控制线”发送的信号。这些信号将数据从寄存器和内存中传递到CPU中，在其中将值相加并在算术逻辑单元中输出。

算术逻辑单元可能有单独的加法器和乘法器，也可能混合在一起。

算术逻辑单元有一堆进行加法操作的晶体管，然后产生输出。该输出通过指令解码器生成的信号进行路由，并存储在内存或寄存器中。

算术逻辑单元和指令解码器中晶体管的布局（以及我忽略的部分）被镭刻到芯片上。该镭刻图案通常是通过编译硬件描述语言产生的，该语言将连接在一起的抽象内容和操作方式转换为晶体管和互连线。

硬件描述语言可以包含不描述时间发生情况（比如一个接着一个）但同时描述发生在空间中的移位和循环。这些代码可能看起来非常模糊，与您以上发布的代码很相似。

以上省略了许多部分和层次，并且存在不准确之处。这既是因为我的不足（我曾经写过硬件和编译器，但对于两者都不是专家），也因为全面细节需要耗费一两个职业生涯，而不是SO贴子所能容纳。

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

- Yakk - Adam Nevraumont

Answer 5

几乎所有可以运行编译后的C代码的现代处理器都具有内置的整数加法支持。您发布的代码是一种聪明的整数加法执行方式，但这不是常规的整数加法执行方式。事实上，函数链接可能使用某种形式的整数加法来调整堆栈指针。

您发布的代码依赖于以下观察结果：当添加x和y时，您可以将其分解为它们共同拥有的位和仅限于x或y之一的位。

表达式x＆y（按位与）给出x和y共同拥有的位数。表达式x ^ y（按位异或）给出仅限于x或y中一个的位数。

总和x + y可重写为两倍于它们共同拥有的位数之和（因为x和y都会贡献这些位数），再加上x或y唯一的位数。

(x＆y) << 1是它们共同拥有的位数的两倍（左移1相当于乘以2）。

x ^ y是仅限于x或y之一的位数。

因此，如果我们将第一个值替换为x，将第二个值替换为y，则总和应该保持不变。您可以认为第一个值是按位加法的进位，而第二个值是按位加法的低阶位。

此过程一直进行，直到x为零为止，此时y保存总和。

- Tom Karzes

Answer 6

你找到的代码尝试解释非常原始的计算机硬件如何执行“加法”指令。我说“尝试”是因为我可以保证没有任何CPU使用这种方法，我会解释原因。

在日常生活中，您使用十进制数字并学习如何将它们相加：要添加两个数字，请添加最低两位数字。如果结果小于10，则写下结果并继续下一位数字位置。如果结果大于等于10，则写下结果减去10，继续下一个数字位置，但记得再加1。例如：23 + 37，您添加3 + 7 = 10，您写下0并记得为下一个位置添加1。在10s位置上，您添加（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添加到数字0xffffffff（32个1位），则第一次迭代会清除y的位0并将x设置为2。第二次迭代会清除y的位1并将x设置为4。依此类推。需要32次迭代才能得到结果。但是，每次迭代都必须处理x和y的所有位，这需要大量的硬件。

一种原始的处理器会像你进行十进制算术运算一样快，从最低位到最高位依次进行。它也需要32个步骤，但每个步骤仅处理两个比特和前一个比特位置的一个值，因此更容易实现。即使在原始计算机中，人们也可以承受这样做而无需实现循环。

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

一个64位的加法器由两部分组成：首先，一个32位的加法器用于最低的32位。那个32位的加法器产生一个总和和一个“进位”（指示必须添加1到下一个比特位置）。其次，为高32位提供两个32位的加法器：一个加x+y，另一个加x+y+1。所有三个加法器都是并行工作的。然后当第一个加法器产生它的进位时，CPU只需选择哪一个结果x+y或x+y+1是正确的，这样你就得到了完整的结果。因此，一个64位加法器只比一个32位加法器慢一点点，而不是两倍长。

32位加法器部件再次作为条件求和加法器实现，使用多个16位加法器，而16位加法器则是条件求和加法器，以此类推。

- gnasher729

Answer 7

我的问题是：在大多数实现中，加号运算符是否被实现为发布的代码？让我们回答实际问题。所有运算符都由编译器作为一些内部数据结构实现，经过一些转换后最终被翻译成代码。你不能说单个加法会生成什么代码，因为几乎没有真实世界的编译器会为单个语句生成代码。只要行为符合标准，编译器可以自由地生成任何代码。但实际发生的事情可能完全不同。一个简单的例子：

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指令。

你无法单独讨论操作符的实现，因为它几乎永远不会单独使用。

- Art

Answer 8

仅出于兴趣，在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指令（从寄存器中减去常量）完成的，其中0xFF在这种情况下实际上等于-1。

还值得注意的是，这个特定的处理器没有addi指令，这意味着设计者认为通过编译器写手执行补码的减法运算已经足够。

这是否利用了二进制补码或其他实现相关特性？

可以说编译器编写者通常会尝试以该体系结构最有效的方式实现所需的效果（将一个数加到另一个数上）。如果需要执行补码的减法，则这样做。

- Nick Gammon

Answer 9

如果代码出现问题，以下示例可能对其他人有所帮助：x=2, y=6：

---

x 不为零，因此开始将其加到 y 中：

while(2) {

x & y = 2 的原因是

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

2 <<1 = 4的原因是<< 1将所有位向左移动：

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

总之，将结果4存储在t中。

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

现在使用按位异或运算符 ^= 来实现：y^=x。

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

所以，x = 2，y = 4。最后，通过重新设置x = t并回到while循环的开头，将t + y相加：

x = t;

当t=0时（或者，在循环开始时，x=0），使用以下代码结束：

return y;

- user1717828

---

已经有一个很好的解释说明了为什么我们要存储进位标志位，所以我发表这个答案来展示代码是如何工作的。 - user1717828