第 2 页

关于本页的补码部分，此番重新理解了一下，似是透彻理解，见如下笔记，

补码的理解

第 3 页

这里的 0x3F 3F 3F 3F 经过验证，发现是符合作者所说的特性的。这里是有一点绕的，要两个条件结合在一起。

• 整数的两倍不超过 0x7F 7F 7F 7F，而 0x7F 7F 7F 7F 这个数恰是 int 这个有符号的 32 最大整数。
• 整数的每 8 位都是相同的。

0x3F 3F 3F 3F 正是满足上面两个条件的最大正整数。

按：这里书上写的内容都是正确的，但是理解起来是需要花费一定的时间的。

第 4 页

经过我的实验，发现对于书中所说的算数右移是高位用符号位填充，那么，我的疑问是，unsigned int 类型是如何呢？实验结果如下，环境是 MSVC2022，无符号的 int 类型是使用逻辑右移，即高位补 0。有符号的 int 是使用符号位进行补充，也就是说，是算数右移。

CH0101

对于其正确性的证明如下，

书中的公式 $a^{2^i} = (a^{2^{i-1}})^2$ 是用来递推的，也就是代码的这一行，

a = (long long) a * a % p;

可供测试的代码如下，

#include <iostream>

using namespace std;

int power(int a, int b, int p) {  // calculate(a ^ b) mod p
    int ans = 1 % p;
    for (; b; b >>= 1) {
        if (b & 1) {  // 如果当前的这一位取出来是 1 才进行里面的操作
            ans = (long long)ans * a % p;
        }
        a = (long long)a * a % p;  // 每一次更新的是单独的那一项，由递推公式推出来的
    }
    return ans;
}

int main(int argc, char const *argv[]) {
    freopen("./liyuds_cases/CH0101.txt", "r", stdin);
    int a;
    int b;
    int p;
    while (cin >> a && cin >> b && cin >> p) {
        cout << a << ", " << b << ",  " << p << endl;
        int cur_ans = power(a, b, p);
        cout << cur_ans << endl;
    }

    return 0;
}

测试用例如下，