前言

這本書說自己是計算機專業數學入門之入門,成為讀者攻讀其他經典著作的墊腳石，但個人以為足矣替換掉本校內不知所云的、抽象的、讓學生考完后馬上全忘的那些課程。本書的 GitHub 倉庫在這里。

該筆記并非單純的整理歸納，而是記錄陸爻齊在書中找到的對自己很有感觸的部分。

閑話少說，下面是筆記正文。

第一章 整數與二進制

1.1 二進制

基本性質

首先，有兩條基本的性質

1. 偶數二進制最末尾的比特是 0;奇數二進制最末尾的比特是 1；
2. 在一個二進制數末尾增加一個 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的異或、與及移位操作。

思考

這里又是思考：要理解這個加法算法只需要地正確回答出以下三個問題:

1. a ∧ b 得到的是什么?
2. (b&a) << 1 得到的是什么?
3. 該算法為什么會終止?

陸爻齊的回答是，

1. a ^ b 得到的是 a 和 b 相加后，移位之后且還沒計算進位的部分。異或操作是 10 和 01 得 1，11 或 00 得 0，1 與 0 相加，那位不用進位，留 1；而 0 + 0 或 1 + 1，則會在原地留 0，這正好符合異或操作的結果。
2. (b&a) << 1 得到進位的部分，a&b 的與操作就可以得到 1 + 1 的位，<< 1 是移位操作，根據上文，二進制乘 2，靠后面加個 0， 故向左移一位。
3. 算法之所以會終止，是因為從右向左，每次執行完進位操作一定能保證該位以右不會有可進位的位，如設第 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 的某次方

兩個思路

1. 若 v 為 2 的某次方，必表現為 100……0 的形式，那么用 while 循環從右至左判斷，是否只有最后（最左）為 1 則是；
2. 若 v 為 2 的某次方，必在減 1 后，為 111……11 的形式，那么用相同位數的 111……11 與之異或，若最后得 0，則是；

小結

CINTA 第一章下來，我想我還是更優先看看 CSAPP 或許更好些，不過其中部分內容真是有意思，從二進制的角度看待加、乘、除，別有一番風味。另外也慶幸不是學校的專業課，不然又是一門備考時令人頭疼的科目力