nal*_*zok 80 c operators bitwise-operators
当了解如何原始的运营商,如+,-,*并/用C实现,我发现从下面的代码片段一个有趣的答案.
// replaces the + operator
int add(int x, int y) {
while(x) {
int t = (x & y) <<1;
y ^= x;
x = t;
}
return y;
}
似乎此函数演示了如何+在后台实际工作.但是,理解它对我来说太困惑了.我相信这样的操作是使用编译器生成的汇编指令很长时间完成的!
我的问题是:+运算符是否作为MOST实现上发布的代码实现？这是否利用了两个补码或其他依赖于实现的功能？如果有人能解释它是如何工作的,我会非常感激.
嗯...也许这个问题在SO上有点偏离主题,但我认为通过这些运算符来看是有点好的.
orl*_*rlp 184
为了迂腐,C规范没有规定如何实现添加.
但实际上,+小于或等于CPU字大小的整数类型的运算符会直接转换为CPU的加法指令,较大的整数类型会转换为多个加法指令,并带有一些额外的位来处理溢出.
CPU内部使用逻辑电路来实现添加,并且不使用循环,位移或任何与C工作方式非常相似的东西.
Moh*_*ain 77
当你添加两位时,结果如下:(真值表)
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
因此,如果你按位xor,你可以得到总和没有携带.如果你按位进行,你就可以得到进位.
扩展这个观察的多位数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和和的替代实现.
Ash*_*uja 25
似乎这个函数演示了+实际上如何在后台运行
不会.这被转换为原生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,并模拟一台计算机,你可以看到这门课程,我从中学到了这一点:从第一原理构建现代计算机
如果您不想要电子证书,它是免费的.该课程的第二部分将于今年春季上映
Yak*_*ont 15
C使用抽象机器来描述C代码的作用.所以它没有具体说明.例如,有C"编译器"实际上将C编译成脚本语言.
但是,在大多数C实现中,+小于机器整数大小的两个整数之间将被转换为汇编指令(在许多步骤之后).汇编指令将被转换为机器代码并嵌入您的可执行文件中.汇编是一种从机器代码"一步删除"的语言,旨在比一堆打包的二进制文件更容易阅读.
然后由目标硬件平台解释该机器代码(在许多步骤之后),其由CPU上的指令解码器解释.该指令解码器接收指令,并将其转换为信号以沿"控制线"发送.这些信号通过CPU从寄存器和存储器路由数据,其中值通常在算术逻辑单元中相加.
算术逻辑单元可能具有单独的加法器和乘法器,或者可能将它们混合在一起.
算术逻辑单元具有一串执行加法运算的晶体管,然后产生输出.所述输出通过从指令解码器产生的信号被路由,并存储在存储器或寄存器中.
算术逻辑单元和指令解码器(以及我已经掩盖的部分)中的所述晶体管的布局被蚀刻到工厂的芯片中.蚀刻图案通常通过编译硬件描述语言来产生,该语言抽象了与其操作的内容和方式相关的内容以及生成晶体管和互连线.
硬件描述语言可以包含转变和循环不描述事情发生的时间(如一个又一个的),而是在空间 -它描述了硬件的不同部分之间的连接.所述代码可能看起来非常模糊,就像您上面发布的代码一样.
以上掩盖了许多部分和层次,并包含不准确之处.这既是我自己的无能(我既写了硬件和编译器,但也不是专家),因为全部细节需要一两个职业,而不是SO职位.
这是关于8位加法器的SO帖子. 这是一篇非SO帖子,你会注意到operator+HDL中使用的一些加法器!(HDL本身可以理解+并为您生成较低级别的加法器代码).
Tom*_*zes 14
几乎任何可以运行编译的C代码的现代处理器都将内置支持整数加法.您发布的代码是一种在不执行整数添加操作码的情况下执行整数加法的聪明方法,但通常不执行整数加法的方式.实际上,函数链接可能使用某种形式的整数加法来调整堆栈指针.
您发布的代码依赖于以下观察:添加x和y时,您可以将其分解为它们共有的位以及x或y中唯一的位.
表达式x & y(按位AND)给出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保持总和.
gna*_*729 14
您找到的代码试图解释非常原始的计算机硬件如何实现"添加"指令.我说"可能"因为我可以保证任何 CPU 都不使用这种方法,我会解释原因.
在正常生活中,您使用十进制数字并且您已经学会了如何添加它们:要添加两个数字,您可以添加最低的两位数字.如果结果小于10,则记下结果并继续下一个数字位置.如果结果是10或更多,你写下结果减10,继续下一个数字,买你记得再加1.例如:23 + 37,你加3 + 7 = 10,你记下0并记得为下一个位置再加1.在10s位置,添加(2 + 3)+ 1 = 6并将其写下来.结果是60.
你可以用二进制数做同样的事情.不同之处在于,唯一的数字是0和1,因此唯一可能的总和是0,1,2.对于32位数字,您将处理另一个数字位置.这就是真正原始的计算机硬件将如何做到这一点.
此代码的工作方式不同 如果两个数字都是1,你知道两个二进制数字的总和是2.所以如果两个数字都是1,那么你将在下一个二进制位置再加1个并写下0.这就是t的计算:它找到所有的位置两个二进制数字都是1(即&)并将它们移动到下一个数字位置(<< 1).然后它执行加法:0 + 0 = 0,0 + 1 = 1,1 + 0 = 1,1 + 1是2,但我们写下0.这就是excludive或运算符所做的.
但是你在下一个数字位置必须处理的所有1都没有得到处理.他们仍然需要添加.这就是代码执行循环的原因:在下一次迭代中,添加了所有额外的1.
为什么没有处理器这样做？因为它是一个循环,而处理器不喜欢循环,而且它很慢.它很慢,因为在最坏的情况下,需要32次迭代:如果你将数字加到0xffffffff(32个1位),那么第一次迭代清除y的第0位并将x设置为2.第二次迭代清除第1位y并将x设置为4.依此类推.需要32次迭代才能得到结果.但是,每次迭代都必须处理x和y的所有位,这需要大量的硬件.
原始处理器可以像从最低位置到最高位置一样快速地执行十进制算术.它还需要32个步骤,但每个步骤只处理两位加上前一位位置的一个值,因此实现起来要容易得多.即使在原始计算机中,也可以在不必实现循环的情况下完成此操作.
现代,快速和复杂的CPU将使用"条件和加法器".特别是如果位数高,例如64位加法器,则节省了大量时间.
64位加法器由两部分组成:首先,最低32位的32位加法器.该32位加法器产生一个和,以及一个"进位"(指示1必须将1加到下一位位置).第二,高32位的两个32位加法器:一个加x + y,另一个加x + y + 1.所有三个加法器并行工作.然后,当第一个加法器产生进位时,CPU只选择两个结果中的哪一个x + y或x + y + 1是正确的,你就得到了完整的结果.因此,64位加法器只需要比32位加法器长一点点,而不是两倍长.
32位加法器部分再次实现为条件和加法器,使用多个16位加法器,16位加法器是条件和加法器,依此类推.
Art*_*Art 13
我的问题是:+运算符是否作为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将使用该指令.
您根本无法讨论如何实现运算符,因为它几乎从不单独使用.
use*_*828 11
如果代码细分可以帮助其他人,请举例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.最后,t+y通过重置x=t并返回while循环的开头来总结:
x = t;
当t=0(或在循环开始时x=0)完成
return y;
Nic*_*mon 11
出于兴趣,在Atmega328P处理器上,使用avr-g ++编译器,以下代码通过减去-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
特别注意,add是由subi指令完成的(从寄存器中减去常量),其中0xFF实际上是-1.
同样令人感兴趣的是,这个特定的处理器没有addi指令,这意味着设计人员认为编译器编写者可以充分地处理补码的减法.
这是否利用了两个补码或其他依赖于实现的功能？
可能公平地说,编译器编写者会尝试以特别架构可能的最有效方式实现想要的效果(向另一个添加一个数字).如果这需要减去补数,那就这样吧.