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);
}
问题
-
得到的是什么？
-
得到的是什么？
-
该算法为什么会终止？
解答
首先，同学们先要理解二进制的异或操作与与操作。其次，要理解什么是递归。这是基础。
然后，要理解到 是不考虑进位时
的值。思考二进制规则：
，
，
（忽略进位），即两个不同的比特“加”就是
，否则就是
，这就是所谓的“异或”操作。
那么进位值是什么呢？当然就是“与”操作得到的值，即。为什么呢？因为仅当两个比特都是
才产生进位。并且进位是加到前一个比特去，所以，要移位，即：
。
最后一个问题，递归为何会终止？add函数终止的条件就是调用它时，第二个参数为。注意到，第一次递归调用
add的最后一位必然为，因为左移的作用。最后一个比特为
的数值与任何数相加都不会产生进位，所以，第二次递归调用时第二个参数尾巴上至少有两个
。如此不断做下去，递归必然终止。
后话
以上内容或者我讲解的二进制内容，如果大家理解不了，这并不要紧，新生理解不了肯定是我没讲好，解释不清。这不是什么迫切、关键的东西，并且也不难，很快大家就会学到。但是，为什么我在大家大学第一课还没开始的时候就讲解二进制呢？理由只有一个：我希望大家学习的心情比某些同学主动学习的心情更为迫切。虽然这些内容不难，但是真正懂得这些、理解这些的同学太少！共勉！
网友评论