前言
这本书说自己是计算机专业数学入门之入门,成为读者攻读其他经典著作的垫脚石,但个人以为足矣替换掉本校内不知所云的、抽象的、让学生考完后马上全忘的那些课程。本书的 GitHub 仓库在这里。
该笔记并非单纯的整理归纳,而是记录陆爻齐在书中找到的对自己很有感触的部分。
闲话少说,下面是笔记正文。
第一章 整数与二进制
1.1 二进制
基本性质
首先,有两条基本的性质
- 偶数二进制最末尾的比特是 0;奇数二进制最末尾的比特是 1;
- 在一个二进制数末尾增加一个 0 等同于在十进制中对这个数乘 2。
反过来说,对一个十进制数进行乘 2 操作等同于对其二进制表达左移一个比特。
显然,比如 2 的二进制表示为 0010,3 为 0011, 4即 2*2 为0100。
思考
随后提出思考:请问,你认为对一个十进制数进行除 2 等于对其二进制表达右移一个比特吗?
陆爻齐的回答是:是的,对 3,出 2 得 1.5,0011 右移一个比特得 0001.1,正好为 1.5。对 2, 除 2 得 1,0010 右移一个比特得 0001,正好为1。
性质
接着在基于“考虑任意自然数 n,所谓 2 的 n 次方 (2^n) 只是不断对 1 乘 n 次 2”给出了两条性质
3、给定任意自然数 n, 十进制数 2^n 的二进制数表达就是在 1 后加 n 个 0;
4、给定任意自然数 n, 十进制数 2^n − 1 的二进制数表达就是 n 个 1;
结合一点例子就能认同,4 是 2 的 2 次方,即 1 后加 2 个 0,即 0100。1 是 2 的 0 次方,为 1 后加 0 个 0,即 0001。4 减 1 得 3,0011,就是 2 的 1 次方和 0 次方相加所得, 0011 = 0010 + 0001;2^2 - 1 = 2^1 + 2^0。
思考
接下来是作者给的思考,请将以上计算过程的结论归纳成一个定理,并证明。你可以使用任何的证明方法。
请问,以上“硬”算的方法能否推广为一种证明方法?
陆爻齐认为,可以归纳为,对任意自然数 n+1(n>=0),有\(2^{(n+1)} = \sum_0^n 2^n\)
位置计数法
如此,便引入了位置计数法,即对任意整数 b,有 \(b=\sum_{i=0}^{n-1}b_i2^i\),其中\(b_i\in\{0,1\}\)
显然,取 10,即 1010,可以视为 \(1010 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0\),换句话 10 = 18 + 04 + 12 + 01。
加法与乘法
加法
加法,大家都能想到 a+b,但要是不准用 + 呢?
于是有下面这个加法的算法,C++ 实现如下
// 输入:两个整数a和b的和
// 输出:a与b的和
int add (int a, int b) {
// cout << a << " " << b << endl;
if (b == 0) return a;
return add(a^b, (a&b)<<1);
}
作者想表达计算机的本质是bit的异或、与及移位操作。
思考
这里又是思考:要理解这个加法算法只需要地正确回答出以下三个问题:
- a ∧ b 得到的是什么?
- (b&a) << 1 得到的是什么?
- 该算法为什么会终止?
陆爻齐的回答是,
- a ^ b 得到的是 a 和 b 相加后,移位之后且还没计算进位的部分。异或操作是 10 和 01 得 1,11 或 00 得 0,1 与 0 相加,那位不用进位,留 1;而 0 + 0 或 1 + 1,则会在原地留 0,这正好符合异或操作的结果。
- (b&a) << 1 得到进位的部分,a&b 的与操作就可以得到 1 + 1 的位,<< 1 是移位操作,根据上文,二进制乘 2,靠后面加个 0, 故向左移一位。
- 算法之所以会终止,是因为从右向左,每次执行完进位操作一定能保证该位以右不会有可进位的位,如设第 1 位要进位,那么进位后第一位就确认为 1 或 0,但进位后可能导致下一位需要进位,若此时第二位要进位,那么就处理进位并确认第二位为 1 或 0,以此类推,处理至尽。因处理的数字是有限位数字,故算法一定能终止。
乘法
作者介绍了一种朴素乘法,即 a*b 的本质,是 b 个 a 相加。下面作者以此为例,从正确性、效率、优化三个角度分析该算法。
显然,这种不断加的乘法时间复杂度为O(n)。
然后是重点,递归版的“简单乘法”,C++ 实现如下。
int multiply(int a, int b) {
// cout << a << " " << b << endl;
if (b == 0) return 0;
if (is_even(b)) {
return 2 * multiply(a, b >> 1);
}
else {
return 2 * multiply(a, b >> 1) + a;
}
}
其实这个程序可以这么理解,返 0 不用说,如果 b 是偶数,比如 0b100 是 8,a 随便取个数,比如 3,即 0b11,用 100 * 11 相当于 2 * (10 * 11),也等于 2 * ( 2 * ( 1 * 11)),最后省个 1,也就加个 a,综上。
换个复杂点的例子,让 b 为 1010,那就可以看为 (12^4 + 02^3 + 12^2 + 02^1) * 3 。
同时作者还补充,在附录 A 有更高效的乘法实现。
除法
定理
首先得有个除法定理,对任意给定的整数 a 和 b,其中 b > 0,存在唯一的整数对 q(商)和 r(余数),使得 a = qb + r 且 0 ≤ r < b。
然后,介绍了下良序原则和单射、满射、一一映射等概念,不过感觉在下面没啥用。
然后是除法的实现,朴素除法与朴素乘法类似,是不断减去除数,至被除数比除数小时,相减次数为“商”,剩下的被除数为“余数”。
简单除法
而简单除法的 C++ 实现如下
std::pair<int, int> m_divide(int a, int b) {
// cout << a << " " << b << endl;
if (a == 0) {
return pair<int, int>(0, 0);
}
std::pair<int, int> result = m_divide(a >> 1, b);
result.first <<= 1; result.second <<= 1;
if (a & 1) {
result.second += 1;
}
if (result.second >= b) {
result.first += 1;
result.second -= b;
}
return result;
}
某种程度就是那个简单除法的逆运算捏,但我觉得我也不是那么明白,只能感受到,这是在不断对背除数除二,然后从左至右确认“商”,最后消除还不明白如何产生的误差来确认“余数”。
第一章 习题
嘛,又不是正式上课,就选两道做做罢
1 判断奇偶的函数,c语言实现
判断奇数
int func (int a) { if (a & 1) return True; return False; }
判断偶数
int func (int a) { if (a & 1) return False; return True; }
思想是,奇数的二进制表示中,最右位总为 1,只要 & 上 1,就只会保留最右位,1 则奇数,0 则偶数。
2 判断 v 是否为 2 的某次方
两个思路
- 若 v 为 2 的某次方,必表现为 100……0 的形式,那么用 while 循环从右至左判断,是否只有最后(最左)为 1 则是;
- 若 v 为 2 的某次方,必在减 1 后,为 111……11 的形式,那么用相同位数的 111……11 与之异或,若最后得 0,则是;
小结
CINTA 第一章下来,我想我还是更优先看看 CSAPP 或许更好些,不过其中部分内容真是有意思,从二进制的角度看待加、乘、除,别有一番风味。另外也庆幸不是学校的专业课,不然又是一门备考时令人头疼的科目力
标签:11,含加,return,二进制,int,CINTA,除法,进位 From: https://www.cnblogs.com/luyaoqi/p/18286979