微光工作室
CS-MEDIUM-01 位级操作
课前准备--进制转换
因为位级操作是建立在二进制的基础上的，而二进制不是我们日常直观接触的，所以在接触学习以及应用位级操作之前，你需要掌握十进制与二进制的相互转化。
要求
- 将CS_M_01文件中所有十进制数改写为二进制数（下载点这里）
- 你可能发现了：有一些小数在进行进制转换时会从原来的有限小数变成无限小数。我们称此为进制的表示不完全性。思考什么时候不同进制之间能完全转化，什么时候可能会出现一个进制没法完全表示另一个进制的数。
提交方式：在markdown文档中提交正确的代码和你的思考答案，并用截图展示进制转换的运行结果
Step 1.了解位运算
位运算是对整数（通常是二进制表示）进行的运算，操作对象是单个比特位。位运算直接作用于数值的二进制位，按位进行处理。 位运算相比常规加减乘除效率更高，能在算法实现、性能优化、状态压缩中起到重要作用 常见的位运算：
按位与（AND）：
&对应位置上的两个比特都为 1 时结果为 1，否则为 0。
- 例：
1010 & 1100 = 1000
- 例：
按位或（OR）：
|对应位置上的两个比特有一个为 1 时结果为 1，否则为 0。
- 例：
1010 | 1100 = 1110
- 例：
按位异或（XOR）：
^对应位置上的两个比特不同则结果为 1，相同则为 0。
- 例：
1010 ^ 1100 = 0110
- 例：
按位非（NOT）：
~对单个比特进行取反，0 变为 1，1 变为 0。
- 例：
~1010 = 0101
- 例：
左移（Left Shift）：
<<将二进制数的所有位向左移动指定的位数，左移相当于乘以2的幂。
- 例：
1010 << 1 = 10100（十进制是10 << 1 = 20）
- 例：
右移（Right Shift）：
>>算数右移：对有符号数进行的操作，将二进制数的所有位向右移动指定的位数，同时符号位会被拓展。
逻辑右移：对无符号数进行的操作，将二进制数的所有位向右移动指定的位数，相当于除以2的幂。
假设
x = -4，二进制表示为11111111111111111111111111111100（32位表示），算术右移1位后：x >> 1结果是11111111111111111111111111111110，即-2，符号位保持为1。
任务
在接触了C语言这么长时间后，相信你已经对逻辑运算了如指掌了，那么你能说说看逻辑运算和位运算的区别和联系吗。思考并提交于markdown文档。
位运算的定义很简单，但是再简单的定义也可能产生一些有用的性质（比如运算律）。查阅资料了解位运算有哪些性质。
移位运算中，右移有两种，其中算数右移对应有符号数，逻辑右移对应无符号数，那么为什么会有这种区别呢。查阅资料理解整数的补码表示后回答于markdown文档。
可以阅读《深入理解计算机系统》第二章
Step 2.位运算基本应用
了解了什么是位运算后，接下来你需要去了解一些位运算的基础运用，例如如何提取出一个整数二进制表示中最右侧的1，在你充分了解了这些基础运用后，完成以下这些小练习进一步巩固自己对位运算的理解并加强对位运算的运用能力。
给定一个整数
x（十进制），同时指定一个位数n，确定这个整数x的二进制表示上第n位是0还是1。例如：251的二进制表示是11111011，n=3，结果返回0。给定一个整数
x（十进制），指定一个位数n，给定一个修正值t（0或者1），将整数x的二进制表示上的第n位改为修正值t。输出被修改后的整数。给定一个有符号32位整数
x，找到其二进制表示上从右开始的第一个1，并输出该数，例如：x=10,二进制表示为1010,第一个1在第二位，所以输出二进制表示为10的数2。提示：阅读《深入理解计算机系统》第二章，补码表示下的有符号整数有什么性质？
给定一个数
n，接下来输入n个数，其中这n个数中有一个数只出现了一次，其余数都出现了两次。请你在O(n)时间内找到这个数并输出。现在有两串无符号数
a和b的二进制编码，并且有a<b，每个数字的大小在100位以内，现在问区间[a,b]内&的结果。n皇后问题：对于一个n*n的格子组，现在要求放置n个皇后，要求每个皇后制的位置所处的左右对角线以及同行同列上没有其他皇后。问最后有多少种可能。n是一个小于10的正整数。
这道题的常规算法效率较低，但是使用位运算的方法可以使效率大大提升，这也使得这道题成了位运算运用的经典题型
任务：
- 使用位运算完成上述题，并将正确的可执行代码提交至markdown文档中，同时附上截图展示运行结果。
提交方式：在markdown文档中提交正确的可执行的代码和截图展示运行成果
Step 3
在格里姆的活动室，大家非常喜欢玩数独游戏。每周末，爱好者会提前设计好一些数独题目，大家聚在一起比赛解题，看谁能最快填满数独格子。 不过，有时难度较高的题目让大家头疼不已，于是希望能开发一个自动数独求解器：只需输入当前数独盘面，系统就能自动算出一种合理的填法，帮助大家学习数独技巧，或验证自己的答案是否正确。 你作为活动区的数独爱好者，准备开发这样一个数独求解器，让大家在活动中能随时验证和学习数独解题方法。你的任务是：
✅ 重点说明实现一个程序，能自动填写并输出一个可行的数独解，如果无解则提示“无解”。
输入：
- 数独的初始状态，共九行，每行一串字符串(有空格)，其中数字代表在该行该位置上已经放置了的数字，
.代表没有放置任何量。
输出：
- 要求你输出最后的标准答案，依然采用字符串输出，共九行九列。
- 要求使用位运算的方法。
输入样例：
5 . . . . 7 . . .
. 2 . . 6 . . 8 .
. . 3 9 . . 2 . .
. 7 . 6 . . . 4 2
. . 9 . 4 . 1 . .
1 . . . . 9 . . 3
. . 1 . . 2 6 . .
. 6 . . 7 . . 5 .
. . . 4 . . . . 75 . . . . 7 . . .
. 2 . . 6 . . 8 .
. . 3 9 . . 2 . .
. 7 . 6 . . . 4 2
. . 9 . 4 . 1 . .
1 . . . . 9 . . 3
. . 1 . . 2 6 . .
. 6 . . 7 . . 5 .
. . . 4 . . . . 7输出样例
5 8 6 2 3 7 4 1 9
9 2 4 5 6 1 3 8 7
7 1 3 9 8 4 2 6 5
3 7 5 6 1 8 9 4 2
6 4 9 7 5 2 1 3 8
1 5 8 8 2 9 7 7 3
8 3 1 7 5 2 6 9 4
4 6 7 3 7 6 8 5 1
2 9 2 4 9 3 5 8 75 8 6 2 3 7 4 1 9
9 2 4 5 6 1 3 8 7
7 1 3 9 8 4 2 6 5
3 7 5 6 1 8 9 4 2
6 4 9 7 5 2 1 3 8
1 5 8 8 2 9 7 7 3
8 3 1 7 5 2 6 9 4
4 6 7 3 7 6 8 5 1
2 9 2 4 9 3 5 8 7- 提示：这题与n皇后问题的限制方式有什么区别，可以怎么实现呢。
本题提交方式
出题人联系方式
QQ：2979734778