题目回顾
麦森数是指形如 2^p - 1 的数（p 为素数）。题目要求：
- 输出
2^p - 1的位数 - 输出
2^p - 1的最后 500 位
本代码涉及的知识点
| 序号 | 知识点 | 对应函数 | 核心要点 |
|---|---|---|---|
| 1 | 快速幂 | Pow() | 二分思想、指数二进制拆分 |
| 2 | 位数公式 | main() | floor(p × log10(2)) + 1 |
| 3 | 位运算 | Pow() | & 1 判奇偶、>>= 1 右移除 2 |
知识点逐个讲解
一、快速幂（二分幂）—— Pow()
string Pow(string Base, long long Exp) {
string Res = "1";
while (Exp > 0) {
if (Exp & 1) // 如果当前指数是奇数
Res = Cal(Res, Base);
Base = Cal(Base, Base); // 底数自乘
Exp >>= 1; // 指数右移一位（相当于 / 2）
}
return Res;
}核心原理：
把指数拆成二进制，例如 2^13 = 2^(1101₂) = 2^8 × 2^4 × 2^1
| 步骤 | Exp（二进制） | Exp & 1 | 操作 | Base |
|---|---|---|---|---|
| 1 | 1101 | 1（奇） | Res ×= Base | Base² |
| 2 | 110 | 0（偶） | 跳过 | Base⁴ |
| 3 | 11 | 1（奇） | Res ×= Base⁴ | Base⁸ |
| 4 | 1 | 1（奇） | Res ×= Base⁸ | Base¹⁶ |
| 结束 | 0 | — | 返回 Res = Base¹³ | — |
为什么快？
普通做法算 2^13 要乘 13 次。快速幂只需 4 轮循环、最多 4 次乘法，2^3000000 也只需要约 22 次。时间复杂度从 O(n) 降到 O(log n)。
二、位运算 —— Pow() 中的两个运算符
快速幂里用了两个位运算，它们是性能的关键：
if (Exp & 1) // ① 按位与 —— 判断奇偶
Exp >>= 1; // ② 右移 —— 整除 2① & 按位与 —— 判奇偶
| 运算 | 等价写法 | 原理 |
|---|---|---|
Exp & 1 | Exp % 2 == 1 | 任何数的二进制最低位是 1 则为奇数，0 则为偶数 |
13 的二进制：1101
1 的二进制：0001
13 & 1 = 0001 = 1（奇）
12 的二进制：1100
1 的二进制：0001
12 & 1 = 0000 = 0（偶）② >>= 右移 —— 整除 2
| 运算 | 等价写法 | 原理 |
|---|---|---|
Exp >>= 1 | Exp /= 2 | 二进制整体右移一位，相当于除以 2 |
13 的二进制：1101 → 右移一位 → 110 = 6
6 的二进制： 110 → 右移一位 → 11 = 3
3 的二进制： 11 → 右移一位 → 1 = 1
1 的二进制： 1 → 右移一位 → 0（循环结束）为什么要用位运算而不是 % 和 /？
CPU 执行位运算只需要 1 个时钟周期，而除法和取模需要几十个周期。在循环体里反复执行时，位运算的优势非常明显。这是算法竞赛中最基础也最重要的常数级优化。
三、位数公式
int digit = floor(p * log10(2)) + 1;推导过程：
已知 2^p - 1 和 2^p 位数相同（减 1 不会退位，p=1 除外）。
设 k = 2^p，位数 d 满足：
10^(d-1) ≤ k < 10^d
d-1 ≤ log10(k) < d
d = floor(log10(k)) + 1又 log10(2^p) = p × log10(2)，代入得：
位数 = floor(p × log10(2)) + 1
举例验证：
p = 1279 时：1279 × 0.30103 ≈ 385.02，floor 取 385，+1 = 386 位。
p = 3 时：3 × 0.30103 ≈ 0.903，floor 取 0，+1 = 1 位（2³ - 1 = 7，√）。
常见踩坑指南
🔴 坑 1：快速幂写成普通循环
如果 p = 3000000，普通循环算 2^p 需要 300 万次乘法，绝对超时。快速幂只需约 log₂(3000000) ≈ 22 次。
🔴 坑 2：位数公式忘了 +1
log10(2^p) 是小数，floor 后必须 +1。漏掉这一步，位数永远少 1。
🟡 坑 3：位运算优先级
Exp & 1 == 1 会先算 1 == 1 得 true，再算 Exp & true，结果完全错。正确的写法是 (Exp & 1) 加括号，或者直接 if (Exp & 1)。
总结
三个知识点环环相扣：
快速幂提供整体框架 → 位运算在每一轮里高效判断和推进 → 位数公式在最后给出答案的规模
吃透这三个点，不仅这道题能过，刷其他涉及大指数、大数的题（快速幂取模、矩阵快速幂）也都能举一反三。