S1 位运算与进制（20 分钟补丁）

这是什么： 直接对二进制的每一位做运算的六个符号，以及十进制和二进制怎么互相转换。

为什么现在补： L01–L07 从来没讲过位运算，但它是 CSP-J 的常客——CSP-J 2020 T1 优秀的拆分（P7071）本质就是一道二进制拆分题，CSP-J 2025 T3 异或和（P14359）直接考异或。

前置： 只需要 L01 的 int / long long。

读法： 这不是一节课，是一张速查卡。20 分钟看完，做完文末自测就算过。

一、最小可用模板

1.1 六个运算符

一个整数在计算机里就是一串二进制。位运算就是把两个数的二进制对齐，逐位计算。

竖着对齐算一遍就全明白了（6 是 110，3 是 011）：

    110   (6)          110   (6)          110   (6)
  & 011   (3)        | 011   (3)        ^ 011   (3)
  -----              -----              -----
    010   (2)          111   (7)          101   (5)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 6, b = 3;
    cout << (a & b) << endl;    // 2
    cout << (a | b) << endl;    // 7
    cout << (a ^ b) << endl;    // 5
    cout << (a << 1) << endl;   // 12
    cout << (a >> 1) << endl;   // 3
    return 0;
}

📝 << k 就是乘 2ᵏ，>> k 就是整除 2ᵏ。 需要算 2ᵏ 时，1 << k 比 pow(2, k) 又快又准（pow 返回 double，大数会丢精度）。

1.2 三个必背写法

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 22;                          // 22 的二进制是 10110

    // 写法 1：取出第 k 位（最低位算第 0 位）
    for (int k = 4; k >= 0; k--) {
        cout << ((n >> k) & 1);          // 输出 10110
    }
    cout << endl;

    // 写法 2：数一共有几个 1
    int cnt = 0;
    for (int t = n; t > 0; t >>= 1) {
        if (t & 1) cnt++;
    }
    cout << cnt << endl;                 // 3

    // 写法 3：编译器内置，效果同写法 2
    cout << __builtin_popcount(n) << endl;   // 3
    return 0;
}

⚠️ __builtin_popcount 只接受 int。long long 要用 __builtin_popcountll。

1.3 十进制 ↔︎ 二进制

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 十进制 -> 二进制：不断除以 2 取余，余数倒着读
    int n = 22;
    string s = "";
    while (n > 0) {
        s = char('0' + n % 2) + s;       // 新余数接在前面，天然就是正序
        n /= 2;
    }
    cout << s << endl;                   // 10110

    // 二进制 -> 十进制：从左往右，每读一位就 ×2 再加
    string t = "10110";
    int v = 0;
    for (int i = 0; i < (int)t.size(); i++) {
        v = v * 2 + (t[i] - '0');
    }
    cout << v << endl;                   // 22
    return 0;
}

📝 v = v * 2 + 当前位 这个套路换个数字就是任意进制转十进制：八进制写 * 8，十六进制写 * 16。

二、两个坑

⚠️ 坑 1：位运算的优先级比比较运算符还低。

if (n & 1 == 0)          // 你以为在判断"n 是偶数"

C++ 先算 1 == 0（得 0），再算 n & 0（永远是 0），所以这个 if 永远不成立。编译器一声不吭。

if ((n & 1) == 0) { /* n 是偶数 */ }    // 正确：位运算一律套括号

📝 只要写位运算，就给它套一层括号。 上面 1.1 的 cout << (a & b) 也是同理——不套括号会和 << 打架。

⚠️ 坑 2：1 << 31 会溢出。

1 是 int，int 最多装到约 2.1×10⁹，而 2³¹ ≈ 2.1×10⁹ 刚好越界。移 31 位以上必须写 1LL：

long long big = 1LL << 40;      // 对
// long long bad = 1 << 40;     // 错：右边先按 int 算，已经废了

这和 L01 乘方题里"ans 必须用 long long"是同一个毛病：赋给谁不重要，右边先按自己的类型算完。

三、配套真题

CSP-J 2020 T1 优秀的拆分（洛谷 P7071） —— 给定 n，把它拆成互不相同的 2 的正整数次幂之和，从大到小输出；拆不出来输出 -1。

这题就是"把 n 写成二进制，哪些位是 1 就输出对应的 2ᵏ"。有一个必须自己想明白的地方：什么时候输出 -1。

思路提示见 S8_真题分级提示.md，代码自己写。

四、30 秒自测

答不上来就回去重看对应小节。

1. 13 & 6 等于多少？13 ^ 6 呢？（提示：13 是 1101，6 是 0110）
2. 想判断 n 的第 3 位（从 0 数）是不是 1，这一行怎么写？
3. if (x & 1 == 0) 为什么永远不成立？那 if (x & 1 == 1) 呢？

以后学： 位运算还能做状态压缩（用一个整数的每一位表示"选没选"），那是 CSP-S / 提高级的内容，本次冲刺不需要。