MEDIUM-1：位级操作

公元3020年1月1日，距离地球能源完全枯竭还有三千六百五十天，为了解决能源危机，人类派出了数支星际舰队，去寻找传说中藏匿于茫茫星海的无尽能源。而你，是飞船格里姆号的唯一一名系统工程师，某天，你从休眠舱中惊醒，刺耳的警报声回荡在空旷的飞船里，于是你急忙来到主控室，查看飞船的系统日志：

【系统日志 - 星历 3024 年 7 月 21 日 4 时 17 分】 警告：飞船遭遇未知强磁暴打击。 警告：主控 AI “GLIMMER” 核心逻辑单元受损。 致命错误：高级语言编译器已脱机，标准库环境已销毁。

你是全舰唯一的系统工程师。目前飞船正在坠向恒星，你必须在倒计时结束前手动重启 GLIMMER 的四个核心模块。由于高级环境失效，你现在唯一能使用的武器，是计算机科学中最古老、最底层的魔法——位运算（Bitwise Operations）。

现在，拿起你的键盘，工程师。 飞船的存亡就在你的指尖。

要唤醒 GLIMMER，你必须先通过它的身份验证。GLIMMER 是一台极其古板的机器，它只认识 0 和 1，但写在舰长手册上的应急密码却是十进制人类语言。

十进制是我们熟悉的逢十进一，而计算机世界中，所有的信息都以二进制（逢二进一）存储。例如，十进制的 13 在二进制下表示为 1101。

【任务 1】

舰长手册上留下的密码是：211（十进制） 和 10110110（二进制）。

1. 请写出十进制 211 对应的二进制表示。
2. 请写出二进制 10110110 对应的十进制表示。
3. 在 C/C++ 中，如何快速判断一个十进制整数是奇数还是偶数？

引导区已启动，但飞船的能量分布完全紊乱。你需要通过重新拨动控制面板上的六种基础逻辑开关，将能量引流到正确的轨道。

在 C/C++ 中，我们有六个基本的位运算符：

【任务 2】

为了修复能量阵列，请完成下列题目（将正确的可执行代码提交至markdown文档中，并附上运行结果的截图）：

1. 阅读并推导以下 C/C++ 代码的输出结果，并简要解释你的计算结果：

   #include <stdio.h>
   
   int main() {
       unsigned char a = 12;  // 二进制: 00001100
       unsigned char b = 25;  // 二进制: 00011001
   
       unsigned char res1 = a & b;
       unsigned char res2 = a | b;
       unsigned char res3 = a ^ b;
       unsigned char res4 = (a << 2) | (b >> 1);
   
       printf("%d %d %d %d\n", res1, res2, res3, res4);
       return 0;
   }

2. 给定一个整数x（十进制），同时指定一个位数n，确定这个整数x的二进制表示上第n位是0还是1。例如：251的二进制表示是11111011，n=3，结果返回0。

3. 给定一个整数x（十进制），指定一个位数n，给定一个修正值t（0或者1），将整数x的二进制表示上的第n位改为修正值t。输出被修改后的整数。

4. 给定一个有符号32位整数x，找到其二进制表示上从右开始的第一个1，并输出该数，例如：x=10,二进制表示为1010,第一个1在第二位，所以输出二进制表示为10的数2。

5. 现在有两串无符号数a和b的二进制编码，并且有a<b，每个数字的大小在100位以内，现在问区间[a,b]内&的结果。

思考题：

1. 在接触了C语言这么长时间后，相信你已经对逻辑运算了如指掌了，那么你能说说看逻辑运算和位运算的区别和联系吗。思考并提交于markdown文档。

2. 位运算的定义很简单，但是再简单的定义也可能产生一些有用的性质（比如运算律）。查阅资料了解位运算有哪些性质。

3. 移位运算中，右移有两种，其中算数右移对应有符号数，逻辑右移对应无符号数，那么为什么会有这种区别呢。查阅资料理解整数的补码表示后回答于markdown文档。

   可以阅读《深入理解计算机系统》第二章

能量恢复了，你需要向地球发送求救信号。由于带宽受限，通信模块在发送两个数据包（字符串）前，必须进行“碰撞检测”：如果两个数据包中包含相同的字母，就会引起信号湮灭。

【系统提示】

英文字母只有 26 个，而一个 32 位的整型变量（int）有 32 个比特位。我们可以将整型变量当作一个检测字母是否出现过的数组。比如，如果字符串里有字母 'a'，就把整型的第 0 位置 变为1；有 'c'，就把第 2 位置变为 1……

【任务 3】编程题：字符串交集检测

给定两个仅由小写英文字母组成的字符串 s1 和 s2，请利用位运算，判断它们是否含有公共字符。要求空间复杂度严格为 $O(1)$，时间复杂度为 $O(N)$。

输入样例 1：s1 = “hello”, s2 = “world” -> 输出：1

输入样例 2：s1 = “abc”, s2 = “xyz” -> 输出：0

#include <stdio.h>

// 请补全以下代码
int hasCommonChar(const char *s1, const char *s2) {
    int mask1 = 0;
    int mask2 = 0;




    return 0;
}

求救信号已发出，现在，你即将面临一个极度危险的挑战：重启聚变反应堆。反应堆是一个 $N \times N$ 的网格矩阵。你需要将 $N$ 根控制棒插入网格中。为了防止控制棒之间的力场互相干涉导致爆炸，任何两根控制棒都不能处在同一行、同一列，或同一条斜线上。

是的，这是一个经典的“N皇后问题”。但 GLIMMER 的算力已经见底，你必须使用位运算来进行状态压缩，将时间复杂度压缩到极限！

【任务 4】给定反应堆的规模 $N$ ($1 \le N \le 15$)，请使用位运算实现求解控制棒摆放方案的总数

将正确的可执行代码提交至markdown文档中，并附上运行结果的截图

反应堆虽然成功重启，但核心数据链被熔断在狭窄的物理管道深处。GLIMMER无法直接连接核心，你必须投放一台微型维修探针机器人——代号 M.O.U.S.E.。

管道系统是一个 $4 \times 4$ 的封闭网格（共 16 个节点，编号 0~15）。M.O.U.S.E. 需要从管道起点（节点 0）穿过毁坏堵塞的管线，抵达被星际工程师们戏称为“奶酪”的核心硬件晶片（代号 C.H.E.E.S.E.，位于节点 15）。

由于探针的微型 CPU 内存极小，你不能使用任何传统的布尔数组来记录访问状态，所有的地图障碍和探索轨迹必须完全压缩进 int 变量的比特位中！

1. 障碍判断：一个 int 整数 walls 的第 $i$ 位为 1 表示节点 $i$ 遭遇熔毁堵塞（不可通行）。例如 walls = (1 << 5) | (1 << 10) 表示节点 5 和 10 是障碍。
2. 移动法则：每次只能向上下左右移动一格，不能斜走，不能穿墙，不能超出 0~15 的边界。
3. 状态压缩：使用一个 int visited 变量，其第 $p$ 位为 1 表示节点 $p$ 已经被探针访问过。更新访问状态：visited |= (1 << pos)；检查访问状态：visited & (1 << pos)。

【任务 5】编程题：广度优先搜索 (BFS) 与位运算寻路

请使用 C 语言补全以下 BFS 算法，求出 M.O.U.S.E. 抵达 C.H.E.E.S.E. 所需的最短步数。若无法到达，返回 -1。

#include <stdio.h>
#include <stdbool.h>

// 定义简单队列结构用于 BFS
typedef struct {
    int pos;   // 当前节点编号 (0~15)
    int dist;  // 到达当前节点的最短步数
} Node;

int minStepsToCheese(int walls) {
    int start = 0;
    int target = 15;

    // 如果起点或终点本身是墙，直接不可达
    if ((walls & (1 << start)) || (walls & (1 << target))) {
        return -1;
    }

    // BFS 队列与访问位图
    Node queue[16];
    int front = 0, rear = 0;
    int visited = 0;

    // 起点入队并标记已访问 (请使用位运算)
    queue[rear++] = (Node){start, 0};
    visited |= (1 << start);

    // 上、下、左、右四个方向的节点偏移量
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};

    //请在TO DO 和END OF TO DO 行之间补全代码：
    //TO DO

    //END OF TO DO

    return -1; // 无法到达
}

int main() {
    int walls = (1 << 5) | (1 << 10); // 5号和10号格子是墙
    int steps = minStepsToCheese(walls);
    printf("Minimum steps: %d\n", steps); // 应输出 6
    return 0;
}

测试用例：walls = (1 << 5) | (1 << 10)，起点 0，终点 15，期望输出：6

将正确的可执行代码提交至markdown文档中，并附上运行结果的截图

【系统日志 - 星历 3024 年 7 月 21 日 10 时 56 分 】 逻辑电路通道复苏，能量矩阵重构完成。 反应堆核心达到绝对平衡，GLIMMER 主控 AI 正式唤醒。

警告红光渐次熄灭，象征秩序的冷蓝光辉重新铺满驾驶舱。 舷窗外，那颗曾几乎吞噬一切的炽热恒星正在被远抛身后，引力的枷锁已被切断。

感谢你，工程师。在语言崩塌、荒芜延伸的绝境里，你用最底层的二进制操作，为这座钢铁孤岛重新打通了理性的神经网络。

引擎主推力已加载至 100%，曲率引擎开始震荡。 航线已锁定，前方是未知的深空，也是永恒的征途。

愿此行，终抵群星。

提交点这里

出题人：  Niko✔

QQ：2674884616

邮箱：2674884616@qq.com