洛谷 P1100 高低位交换

// P1100 高低位交换 —— 正解：一行，而那一行里每一个字都是被题面逼出来的
//
//   把 32 位的 x 拆成「高 16 位 H」和「低 16 位 L」，要的是「L H」这个新数：
//
//       x      =  H H H H  L L L L        (每个字母是 4 个二进制位)
//       x >> 16=  0 0 0 0  H H H H        <- 高的那一半挪到低位
//       x << 16=  L L L L  0 0 0 0        <- 低的那一半挪到高位（★ 高出去的 H 被截掉了）
//       或起来  =  L L L L  H H H H        <- 就是答案
//
// ★★ 三件必须想清楚的事（题面一句都没明说，但三句都在数据范围里）：
//   ① **必须是无符号。** 题面写「小于 2³² 的非负整数」⇒ x 可以到 4294967295，
//      `int` 存不下（[p1100Int.cpp](/sol/p1100/) 演示读进去会变成什么）。
//   ② **必须正好是 32 位。** 用 `long long` 的话 `x << 16` **不会被截掉**，
//      那半个 H 会留在第 32~47 位上（[p1100Ll.cpp](/sol/p1100/)）。
//      ⇒ ★ 「截断」在这道题里不是副作用，**它就是算法的一部分**。
//   ③ **输出也要按无符号打。** 答案可以 ≥ 2³¹（[p1100Sd.cpp](/sol/p1100/)）。
//
// ★ 顺带：这里的 `|` 换成 `+` 或 `^` 都对（两半不重叠），见 p1100Add.cpp —— 那是能证的恒等。
#include <cstdio>
using namespace std;

int main() {
    unsigned x;
    if (scanf("%u", &x) != 1) return 0;
    printf("%u\n", (x >> 16) | (x << 16));
    return 0;
}

// P1100 ✗ 错法二：用 long long —— 「怕不够就开大点」，而这道题开大了正好坏事
//
// ★★★ 这一版是这一页最值得看的一个：它的动机完全正确（`unsigned` 记不住的话就用 64 位嘛），
//   可这道题要的**恰恰是那次截断**：
//
//       x = 1314520 时
//         正解（32 位）：(x << 16) 高出去的部分被丢掉 ⇒ 0000 1110 1101 1000 0000 0000 0001 0100
//         这一版（64 位）：(x << 16) 一位都没丢 ⇒ 结果 = x × 65536 + (x >> 16)，一个 37 位的数
//
// ★ 触发线又是一个精确的整数：**x ≥ 2¹⁶ = 65536**（`x << 16` 只有在 x ≥ 65536 时才会溢出 32 位）。
//   ⇒ ★★ 官方那唯一一组样例（1314520）**一测就死** —— 它是这一页三个错法里唯一被样例挡住的。
#include <cstdio>
using namespace std;

int main() {
    long long x;
    if (scanf("%lld", &x) != 1) return 0;
    printf("%lld\n", (x >> 16) | (x << 16));    // ⚠ 少了「只留低 32 位」这一步
    return 0;
}

// P1100 ★★★ 把输入空间**整个**跑一遍：42.9 亿个 x，本机一秒多
//   ./p1100All            人话版
//   ./p1100All csv        给 check:viz 用
//
// ★★★ 为什么这一页可以不靠对拍：这道题的输入是**一个** 32 位整数 ⇒ 输入空间正好 2³² = 4294967296 个。
//   而每个版本都是一个纯函数（读一个数、打一个数），于是
//   「这个写法对不对」这个问题**可以被穷举掉，不需要任何概率论**。
//   ⇒ [「输入空间小的时候，算一遍比对拍又快又充分」](/sol/p1002/)的又一次 ——
//     ★ 而这一次「小」是 42.9 亿，它照样只要一秒多。
//
// 里面同时干了两件事（[第 19 章 P2240](/sol/p2240/) 那条规矩）：
//   ① 报三个真错法的**第一个反例**和**反例总数**；
//   ② 给两个「看着像 bug、其实恒等」的写法（`|`→`+`、`|`→`^`）做自检 ——
//      **报「0 个反例」之前，先证明这段枚举代码是活的**，而上面那三列就是它的活证。
#include <cstdio>
#include <chrono>
using namespace std;

int main(int argc, char** argv) {
    bool csv = (argc > 1 && argv[1][0] == 'c');
    auto t0 = std::chrono::steady_clock::now();

    unsigned long long badInt = 0, badLl = 0, badSd = 0, badAdd = 0, badXor = 0;
    unsigned firstInt = 0, firstLl = 0, firstSd = 0;
    bool hasInt = false, hasLl = false, hasSd = false;

    unsigned x = 0;
    do {
        unsigned ok = (x >> 16) | (x << 16);                    // 正解

        /* ✗ 用 int 读：C++11 起越界的 cin >> int 会把变量置成 INT_MAX */
        unsigned u = (x >= 2147483648u) ? 2147483647u : x;
        unsigned vInt = (u >> 16) | (u << 16);

        /* ✗ 用 long long：左移不截断 */
        unsigned long long vLl = ((unsigned long long)x >> 16) | ((unsigned long long)x << 16);

        /* ✗ 类型全对，输出打成有符号 */
        long long vSd = (long long)(int)ok;

        /* ★ 两个「其实恒等」的写法 */
        unsigned vAdd = (x >> 16) + (x << 16);
        unsigned vXor = (x >> 16) ^ (x << 16);

        if (vInt != ok) { badInt++; if (!hasInt) { hasInt = true; firstInt = x; } }
        if (vLl != (unsigned long long)ok) { badLl++; if (!hasLl) { hasLl = true; firstLl = x; } }
        if (vSd != (long long)ok) { badSd++; if (!hasSd) { hasSd = true; firstSd = x; } }
        if (vAdd != ok) badAdd++;
        if (vXor != ok) badXor++;
        x++;
    } while (x != 0);

    double sec = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();

    if (csv) {
        printf("space,4294967296\n");
        printf("badInt,%llu\nfirstInt,%u\n", badInt, firstInt);
        printf("badLl,%llu\nfirstLl,%u\n", badLl, firstLl);
        printf("badSd,%llu\nfirstSd,%u\n", badSd, firstSd);
        printf("badAdd,%llu\nbadXor,%llu\n", badAdd, badXor);
        printf("fastEnough,%d\n", sec < 60.0 ? 1 : 0);
        return 0;
    }

    printf("P1100 的输入空间只有 2^32 = 4294967296 个数 —— 这里把它们全跑了一遍（%.2f 秒）\n\n", sec);
    printf("  ✗ 用 int 读       第一个反例 x = %-10u   反例共 %llu 个（正好一半）\n", firstInt, badInt);
    printf("  ✗ 用 long long    第一个反例 x = %-10u   反例共 %llu 个（= 2^32 - 65536）\n", firstLl, badLl);
    printf("  ✗ 输出打成有符号  第一个反例 x = %-10u   反例共 %llu 个（正好一半）\n", firstSd, badSd);
    printf("\n  ★ 把 | 换成 +：反例 %llu 个；换成 ^：反例 %llu 个（两半不重叠 ⇒ 三个运算等价）\n", badAdd, badXor);
    printf("  ⇒ 上面那三行不是零，所以这两个零不是「代码没在跑」。\n");
    return 0;
}