计算机科学与技术教与学

关于某加法程序的解释

2020-10-09  本文已影响0人  Bintou老师

2020年10月8日上午,给新生讲解二进制,留了一份作业,任务是理解下面加法程序,并回答问题。现在稍作解释。

问题描述

代码

//输入: 两个整数a和b
//输出: a与b的和
int add(int a, int b) {
    if (b == 0) return a;
    return add(a ^ b, (b & a) << 1);
}

问题

解答

首先,同学们先要理解二进制的异或操作与与操作。其次,要理解什么是递归。这是基础。

然后,要理解到a \wedge b 是不考虑进位时a + b的值。思考二进制规则:0+0 = 00 + 1 = 11 + 1 = 0(忽略进位),即两个不同的比特“加”就是1,否则就是0,这就是所谓的“异或”操作。

那么进位值是什么呢?当然就是“与”操作得到的值,即a \& b。为什么呢?因为仅当两个比特都是1才产生进位。并且进位是加到前一个比特去,所以,要移位,即:(b \& a) << 1

最后一个问题,递归为何会终止?add函数终止的条件就是调用它时,第二个参数为0。注意到,第一次递归调用add的最后一位必然为0,因为左移的作用。最后一个比特为0的数值与任何数相加都不会产生进位,所以,第二次递归调用时第二个参数尾巴上至少有两个0。如此不断做下去,递归必然终止。

后话

以上内容或者我讲解的二进制内容,如果大家理解不了,这并不要紧,新生理解不了肯定是我没讲好,解释不清。这不是什么迫切、关键的东西,并且也不难,很快大家就会学到。但是,为什么我在大家大学第一课还没开始的时候就讲解二进制呢?理由只有一个:我希望大家学习的心情比某些同学主动学习的心情更为迫切。虽然这些内容不难,但是真正懂得这些、理解这些的同学太少!共勉!

上一篇 下一篇

猜你喜欢

热点阅读