这就是运算符在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实现上的代码实现？这是否利用了两个的补充或其他与实现相关的特性？

Answer 1

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

不可以。这被转换为本机add机器指令，它实际上在ALU中使用硬件加法器。

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

计算机中的一切都是用逻辑门完成的，逻辑门主要由晶体管构成。全加器中有半加器。

有关逻辑门和加法器的基本教程，请参见。这段视频非常有用，虽然很长。

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

半加法器加上两位。可能的组合有：

• 加0和0=0

那么半加法器是如何工作的呢？它由三个逻辑门组成，和，异或和与非门。如果两个输入都为负，nand提供正电流，这意味着这解决了0和0的情况。异或给出一个正输出，一个输入为正，另一个为负，这意味着它解决了1和0的问题。只有当两个输入都为正时，和才提供正输出，从而解决了1和1的问题。基本上，我们现在有了半加法器。但我们仍然只能添加一些。

现在我们制作全加法器。全加器由一次又一次地调用半加器组成。现在这有一个携带。当我们加1和1时，我们得到一个进位1。所以全加器所做的是，它从半加器获取进位，存储它，并将它作为另一个参数传递给半加器。

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

惊讶吗？这就是它实际发生的方式。它看起来像一个漫长的过程，但计算机在几分之一纳秒内完成，或者更具体地说，在半个时钟周期内完成。有时甚至在一个时钟周期内执行。基本上，计算机有ALU（CPU的主要部分）、内存、总线等。

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

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

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，则进位为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);
}

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

不。通常（几乎总是）整数加法转换为机器指令加法。这只是演示了一个使用按位异或和的替代实现。

Answer 3

为了显得迂腐，C规范没有指定如何实现加法。

但实际上，小于或等于CPU字长的整数类型上的运算符会直接转换为CPU的加法指令，而较大的整数类型会转换为多个加法指令，并带有一些额外的位来处理溢出。

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