+运算符如何在C中工作?

当理解如何在C中实现+-*/等基本运算符时,我从一个有趣的答案中找到以下代码片段。

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

似乎这个函数演示了+实际上在后台工作的方式。 但是,我理解它太困惑了。 我相信这样的操作是使用编译器生成的汇编指令很长一段时间完成的!

我的问题是: +操作符是否作为在MOST实现上发布的代码实现? 这是否利用了二进制补码或其他实现相关功能? 如果有人能解释它是如何工作的,我会非常感激。

嗯......也许这个问题有点偏离主题,但我认为通过这些运营商来看看有点不错。


为了迂回,C规范没有规定如何实现添加。

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

CPU在内部使用逻辑电路来实现加法,并且不使用循环,位移或与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

所以,如果你按位异或,你可以得到没有进位的总和。 如果你按位进行,你可以得到进位。

扩展这个观察多位数字ab

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

一旦b0

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和和的替代实现。


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

不可以。这被翻译成ALU生的add机器指令,它实际上是使用硬件加法器。

如果你想知道电脑如何添加,这里是一个基本的加法器。

计算机中的所有东西都是使用逻辑门完成的,逻辑门主要由晶体管组成。 全加器在其中有半加器。

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

在该视频中,显示了一个基本的半加器。 如果你想简要说明,就是这样:

半加法器添加了两个给定的位。 可能的组合是:

  • 加0和0 = 0
  • 加1并且0 = 1
  • 加1和1 = 10(二进制)
  • 那么现在半加器如何工作呢? 那么它由三个逻辑门组成,即andxornand 。 如果两个输入都是负数,则nand给出正电流,这意味着这解决了0和0的情况。 xor给出正输出,其中一个输入为正,另一个为负,这意味着它解决了1和0的问题and给出了仅当两个输入是正正的输出,让所以基本上解决了1和1的问题,我们现在已经得到了我们的半加器。 但我们仍然只能添加比特。

    现在我们做我们的全加器。 全加器由反复调用半加器组成。 现在这有一个进展。 当我们加1和1时,我们得到一个进位1.那么全加器的作用是,它从半加器获取进位,存储它,并将它作为另一个参数传递给半加器。

    如果你感到困惑,你怎么能通过进位,你基本上首先使用半加器添加比特,然后添加总和和进位。 所以现在你已经用两位加上了进位。 所以你一次又一次地这样做,直到你必须添加的部分结束,然后你得到结果。

    惊讶吗? 这是实际发生的情况。 它看起来像一个漫长的过程,但计算机可以在半纳秒内完成,或者在半个时钟周期内完成更具体的操作。 有时甚至在一个时钟周期内执行。 基本上,计算机具有ALUCPU的主要部分),内存,总线等。

    如果你想学习计算机硬件,逻辑门,存储器和ALU,并模拟计算机,你可以看到这门课,从中我学到了这些:从第一原理构建现代计算机

    如果你不想要电子证书,这是免费的。 课程的第二部分将在今年春季上演

    链接地址: http://www.djcxy.com/p/9987.html

    上一篇: How does the + operator work in C?

    下一篇: How does the bitwise complement (~) operator work?