Solutions CS101

Appearance

P1100 高低位交换（橙色 普及-） ​

位运算, https://www.luogu.com.cn/problem/P1100

给出一个小于 232 的非负整数。这个数可以用一个 32 位的二进制数表示（不足 32 位用 0 补足）。我们称这个二进制数的前 16 位为“高位”，后 16 位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。

例如，数 1314520 用二进制表示为 00000000000101000000111011011000（添加了 11 个前导 0 补足为 32 位），其中前 16 位为高位，即 0000000000010100；后 16 位为低位，即 0000111011011000。将它的高低位进行交换，我们得到了一个新的二进制数 00001110110110000000000000010100。它即是十进制的 249036820。

输入格式

一个小于 232 的非负整数。

输出格式

将新的数输出。

输入输出样例 #1

输入 #1

1314520

输出 #1

249036820

这是一个经典的位运算问题。题目要求将一个 32 位无符号整数的高 16 位和低 16 位进行交换。

解题思路

  1. 数据类型选择： 由于输入的数最大可达到 232−1，在 C++ 中 int 类型（通常为 32 位带符号整数）会溢出。我们需要使用 unsigned int（无符号 32 位整数）或者 long long（64 位整数）来存储。
  2. 位运算原理：
    • 高位移到低位：将原数右移 16 位 (n >> 16)。这样原本在 [17-32] 位的数字就变成了 [1-16] 位。
    • 低位移到高位：将原数左移 16 位 (n << 16)。这样原本在 [1-16] 位的数字就变成了 [17-32] 位。由于是 32 位无符号操作，左移后高出的位会被自动舍弃（或者我们可以通过位掩码 0xFFFFFFFF 强制截断）。
    • 合并结果：将上述两个结果进行“按位或” (|) 操作即可得到交换后的新数。

代码实现

cpp
#include <iostream>

using namespace std;

int main() {
    // 使用 unsigned int 来处理 32 位无符号整数
    // 在绝大多数现代编译器中，unsigned int 正好是 32 位
    unsigned int n;
    
    // 输入这个数
    if (!(cin >> n)) return 0;

    // (n >> 16) 将高 16 位移动到低 16 位的位置
    // (n << 16) 将低 16 位移动到高 16 位的位置
    // 两者进行位或运算，合并成新的 32 位数
    unsigned int result = (n >> 16) | (n << 16);

    // 输出结果
    cout << result << endl;

    return 0;
}

逐步解析示例

以输入 1314520 为例：

  1. 二进制表示（32位）： 0000 0000 0001 0100 0000 1110 1101 1000
  2. 右移 16 位 (n >> 16)： 高位变低位，前面补 0： 0000 0000 0000 0000 0000 0000 0001 0100 (十进制为 20)
  3. 左移 16 位 (n << 16)： 低位变高位，后面补 0，原本的高位溢出丢弃： 0000 1110 1101 1000 0000 0000 0000 0000 (十进制为 249036800)
  4. 按位或 (|)： 0000 1110 1101 1000 0000 0000 0001 0100 结果为 249036800 + 20 = 249036820。

注意事项

  • 如果在某些老旧环境下 unsigned int 不是 32 位，可以使用 <cstdint> 头文件中的 uint32_t。
  • 如果使用 unsigned long long (64位)，代码应改为 ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16) 以确保只处理低 32 位。但在本题环境下，直接使用 unsigned int 是最简洁的做法。