百度笔试题：位运算实现两个整数加法

有这样一道百度笔试题：请利用位运算实现两个整数的加法运算，请用代码实现，并作简要说明。

【知识点】 数据的表示与运算

【解  析】  本题考查考生对全加器的理解，以及对C语言中各种位运算的运用能力。

（ 1 ）全加器用来实现两个本位数加上低位进位生成一个本位和及一位向高位的进位。第 i 位的加法运算是第 i 位的加数 x _i 、 y _i 和低位 i -1 位的进位 C _{i -1} 三者相加，得到第 i 位的和 z _i ，以及第 i 位的进位输出 C _i 。在计算机中，全加器是用逻辑门电路实现 . ， z _i 和 C _i 的逻辑表达式如下：

z _i = x _i Å y _i Å C _i-1

C _i = x _i y _i + x _i C _i-1 +y _i C _i-1

（2）两个n位整数的加法运算可以用n个全加器实现，有串行进位加法器和并行进位加法器两种。串行进位加法器中进位按串行方式传递，高位进位依赖于低位进位，所以串行进位加法器速度慢。并行进位加法器中，用先行进位部件并行产生各个进位，并可以同时生成各位的和。计算机内部采用并行进位加法器。

（3）ALU的核心部件是加法器，加法器除了产生加法结果外，还提供多种标志信息。这些标志信息在运算电路中产生后，被记录到程序状态字寄存器（或标志寄存器）中，以便在分支指令中被用来作为检测条件。例如，Intel x86处理器中有标志寄存器EFLAGS，其中与运算有关的主要标志信息有：OF溢出标志位反映运算结果是否溢出；SF符号标志位反映运算结果是否为负数；CF进位标志位反映是否产生进位或借位；ZF零标志位反映运算结果是否为零。

（4）计算机中的位运算分为按位逻辑运算和移位运算。按位逻辑运算又分为逻辑与、或、非、异或等。移位运算分算术移位和逻辑移位。移位时，移出的位全部丢弃，需要注意的就是移出的空位补入什么数。如果是左移，规定补入的数全部是0；如果是右移，若是带符号整数，则补入的全是原数的最高位，即原数的符号位，即高位补符；若是无符号整数，则补入全部是0，即高位补0。

【答 案】

用C语言实现时，其中的一种实现代码如下：

typedef struct {

int z;

unsignedchar  flag;

} result;

void add(int x, int y, result *sum)

{

unsigned int      a,b, c, d, c1=0, z=0, p, i;

unsigned char    flag = 0;

unsignedchar   of, sf, zf, cf;

p = 0x00000001;

// p用于提取出数据的某位

for (i=0; i<32; i++)

{    c = c1<<1;         //第i-1位的进位

a = x&p;   //第i位的一个加数

b = y&p;   //第i位的另一个加数

c1= a&b | a&c | b&c;  //第i位的进位

d = a^b^c;   //第i位的结果

z = z | d;      //当前部分和

p = p<<1;

};

sum->z = z;

of = (c^c1) >>28;

// 溢出标志位OF，c^c1的结果在最高位

sf = d>>29;    // 符号标志位SF

cf = c1>>30;  //进位标志位CF

zf = z == 0;    //零标志位ZF

sum->flag = of | sf | cf | zf;

//低4位依次是OF、SF、CF和ZF标志位

}

本文已收录于《横扫Offer--程序员招聘真题详解700题》一书，开点工作室著，清华大学出版社。更多程序员笔试面试真题的精彩详解请参见该书。

为保证书稿质量，作者及出版社在编写完成后经过反复多次的审核、校对和修改，力求为读者奉献一本内容详实、严谨、准确、精美的实用宝典，因此上市时间有所延后，望各位读者谅解。该书目前样书已经印刷完成，预计8月下旬各大网上书店开始发售。我们将会在第一时间通知该书的上市购买信息，并将举行评论送书活动，以感谢各位读者的支持。详细情况请持续关注微信公众账号“开点工作室”。