异或移位变换、无符号整数与线性映射
目录
* 一、原程序
* 二、代码目的与解决的问题
* 三、变量、函数与类型含义
* 四、完整代码逐行注解
* 五、程序执行流程
* 六、核心性质一：异或移位为什么可逆
* 七、核心性质二：为什么命中数不超过 1
* 八、核心性质三：无符号整数的边界与回绕
* 九、核心性质四：概率为什么是二的负整数次幂
* 十、核心性质五：如何快速计算多次变换
* 十一、六个小问逐问解析
* 十二、辅助验证代码
* 十三、复杂度与程序改进
* 十四、最终答案
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、原程序
二、代码目的与解决的问题
程序读入目标值 target\text{target}target 和区间端点 start,end\text{start},\text{end}start,end，在闭区间
[start,end][\text{start},\text{end}] [start,end]
内依次枚举整数 iii。
如果某个 iii 满足
h(i)=target,h(i)=\text{target}, h(i)=target,
程序就输出
i mod 13,i\bmod 13, imod13,
并把命中数量加 111。枚举结束后，程序输出总命中数 count\text{count}count。
函数 hhh 由三次异或移位操作组成：
x ^=x≪2,x\mathrel{\hat{\ }}=x\ll2, x ^=x≪2,
x ^=x≫7,x\mathrel{\hat{\ }}=x\gg7, x ^=x≫7,
x ^=x≪1.x\mathrel{\hat{\ }}=x\ll1. x ^=x≪1.
这里的 ^ 表示按位异或，<< 表示左移，>> 表示右移。
函数 kkk 没有在主程序中被调用，只在后面的小问中用于研究方程
h(x)=k(x)h(x)=k(x) h(x)=k(x)
成立的概率。
三、变量、函数与类型含义
名称 类型 含义 target unsigned 希望函数 hhh 得到的目标值 start unsigned 枚举区间左端点 end unsigned 枚举区间右端点 i unsigned long long 当前枚举的整数 count int 满足 h(i)=targeth(i)=\text{target}h(i)=target 的整数个数 h(x) unsigned 三次异或移位组成的变换 k(x) unsigned 另一种异或移位线性变换
在常见的运行环境中：
sizeof(unsigned)=4,\operatorname{sizeof}(\texttt{unsigned})=4, sizeof(unsigned)=4,
所以 unsigned 通常是 323232 位无符号整数，取值范围为
0≤x≤232−1=4294967295.0\le x\le 2^{32}-1=4294967295. 0≤x≤232−1=4294967295.
unsigned long long 通常是 646464 位无符号整数，能够表示 2322^{32}232，所以枚举变量越过 UINT_MAX 后不会立刻回到 000。
四、完整代码逐行注解
五、程序执行流程
程序的执行顺序如下。
1. 读入 target\text{target}target、start\text{start}start 和 end\text{end}end。
2. 令 count=0\text{count}=0count=0。
3. 从 start\text{start}start 到 end\text{end}end 枚举 iii。
4. 计算 h(i)h(i)h(i)。
5. 如果 h(i)=targeth(i)=\text{target}h(i)=target，输出 i mod 13i\bmod13imod13，并令 count\text{count}count 加 111。
6. 枚举结束后输出 count\text{count}count。
可以写成下面的数据流：
六、核心性质一：异或移位为什么可逆
6.1 X ^= X << S 的逐位关系
设原数的第 jjj 个二进制位为 xjx_jxj ，变换结果的第 jjj 个二进制位为 yjy_jyj 。执行
后，有
yj={xj,0≤j<s,xj⊕xj−s,j≥s.y_j= \begin{cases} x_j, & 0\le j<s,\\ x_j\oplus x_{j-s}, & j\ge s. \end{cases} yj ={xj ,xj ⊕xj−s , 0≤j<s,j≥s.
其中 ⊕\oplus⊕ 表示异或。
最低的 sss 位没有受到左移部分影响，所以能够直接得到：
xj=yj,0≤j<s.x_j=y_j,\qquad 0\le j<s. xj =yj ,0≤j<s.
恢复低 sss 位后，就能继续恢复下一组：
xj=yj⊕xj−s,j≥s.x_j=y_j\oplus x_{j-s},\qquad j\ge s. xj =yj ⊕xj−s ,j≥s.
因此可以从低位向高位逐位恢复原数。
6.2 一个完整的 8 位例子
使用 888 位无符号整数，令 s=2s=2s=2，原数为
左移两位后，高位超出 888 位的部分丢弃：
异或得到：
所以结果为
现在只根据 yyy 恢复 xxx。从右向左每两位分为一组：
最低一组不受左移部分影响：
恢复下一组：
继续恢复：
从高到低重新组合：
原数被唯一恢复，因此这个变换是可逆的。
6.3 有限次异或消去
对于固定字长 www，也可以使用有限次异或移位恢复。恢复
y=x⊕(x≪s)y=x\oplus(x\ll s) y=x⊕(x≪s)
时，可以执行：
循环中的位移量依次为
s,2s,4s,8s,…s,2s,4s,8s,\ldots s,2s,4s,8s,…
超过字长后，继续左移已经不会贡献有效位，所以循环结束。
前面的 888 位例子可以直接恢复：
6.4 X ^= X >> S 为什么也可逆
设
右移不会影响最高的 sss 位，所以可以先恢复最高的 sss 位，再从高位向低位逐组恢复。
对应的逆函数为：
6.5 函数 HHH 为什么可逆
函数 hhh 依次进行了：
1. 左移 222 位异或；
2. 右移 777 位异或；
3. 左移 111 位异或。
每一步都是双射。双射的复合仍然是双射，所以 hhh 是全部 323232 位无符号整数集合上的双射。
若要从目标值 y=h(x)y=h(x)y=h(x) 恢复 xxx，必须按照相反顺序撤销：
七、核心性质二：为什么命中数不超过 1
因为 hhh 是双射，所以对于任意 unsigned target，方程
h(x)=targeth(x)=\text{target} h(x)=target
在全部 323232 位无符号整数中恰好有一个解。
证明如下。
假设存在两个不同的整数 x1≠x2x_1\ne x_2x1 =x2 ，同时满足
h(x1)=h(x2)=target.h(x_1)=h(x_2)=\text{target}. h(x1 )=h(x2 )=target.
由于 hhh 可逆，在等式两边同时执行 h−1h^{-1}h−1，得到
x1=h−1(target)=x2,x_1=h^{-1}(\text{target})=x_2, x1 =h−1(target)=x2 ,
这与 x1≠x2x_1\ne x_2x1 =x2 矛盾。
因此全集中只有一个原像。闭区间 [start,end][\text{start},\text{end}][start,end] 只是全集的一个子集，所以区间内的命中数只可能为
0或1.0\quad\text{或}\quad1. 0或1.
也就是说：
count≤1.\text{count}\le1. count≤1.
八、核心性质三：无符号整数的边界与回绕
8.1 -1 读入 UNSIGNED 后的值
在常见的 323232 位 unsigned 环境中，负数转换为无符号整数时按模 2322^{32}232 处理。因此
−1≡232−1(mod232),-1\equiv2^{32}-1\pmod{2^{32}}, −1≡232−1(mod232),
所以读入 -1 后，end 的值为
4294967295.4294967295. 4294967295.
于是输入
实际枚举的区间是
[1,4294967295].[1,4294967295]. [1,4294967295].
8.2 为什么原程序使用 UNSIGNED LONG LONG I
当 i=4294967295i=4294967295i=4294967295 时，如果 iii 是 646464 位无符号整数，那么执行 i++ 后得到
4294967296.4294967296. 4294967296.
此时
4294967296>4294967295,4294967296>4294967295, 4294967296>4294967295,
循环条件失败，程序结束。
8.3 改成 UNSIGNED INT I 会发生什么
若循环变量只有 323232 位，那么最大值加 111 会按模 2322^{32}232 回绕：
(232−1)+1≡0(mod232).(2^{32}-1)+1\equiv0\pmod{2^{32}}. (232−1)+1≡0(mod232).
于是：
当 end=4294967295 时，任意 323232 位无符号整数都满足
i≤end.i\le\text{end}. i≤end.
所以循环会从 000 再次开始，无法正常结束。
九、核心性质四：概率为什么是二的负整数次幂
9.1 异或与移位是 GF(2)GF(2)GF(2) 上的线性运算
一个 323232 位无符号整数可以看成一个 323232 维二进制向量：
x=(x0,x1,…,x31),xi∈{0,1}.x=(x_0,x_1,\ldots,x_{31}),\qquad x_i\in\{0,1\}. x=(x0 ,x1 ,…,x31 ),xi ∈{0,1}.
异或就是二进制域 GF(2)GF(2)GF(2) 上的加法。左移和右移只是把各位移动到新的位置并在空位补 000，因此也是线性变换。
所以存在两个 32×3232\times3232×32 的二进制矩阵 H,KH,KH,K，使得
h(x)=Hx,h(x)=Hx, h(x)=Hx,
k(x)=Kx.k(x)=Kx. k(x)=Kx.
9.2 把函数相等转化为齐次方程
条件
h(x)=k(x)h(x)=k(x) h(x)=k(x)
等价于
Hx=Kx.Hx=Kx. Hx=Kx.
在 GF(2)GF(2)GF(2) 中，减法与加法相同，因此
(H−K)x=0(H-K)x=0 (H−K)x=0
也可以写成
(H⊕K)x=0.(H\oplus K)x=0. (H⊕K)x=0.
这变成了一个 323232 元齐次线性方程组。
9.3 如何得到矩阵的秩
令 eje_jej 表示只有第 jjj 位为 111 的单位向量。线性变换矩阵的第 jjj 列就是
h(ej)⊕k(ej).h(e_j)\oplus k(e_j). h(ej )⊕k(ej ).
对 j=0,1,…,31j=0,1,\ldots,31j=0,1,…,31 依次计算这些列，再进行二进制高斯消元，得到
rank(H−K)=30.\operatorname{rank}(H-K)=30. rank(H−K)=30.
根据秩—零度定理，零空间维数为
32−30=2.32-30=2. 32−30=2.
因此方程共有
22=42^2=4 22=4
个解。
四个实际解为：
将它们分别代入，都满足 h(x)=k(x)h(x)=k(x)h(x)=k(x)。
9.4 概率计算
全部 323232 位无符号整数共有
2322^{32} 232
个，其中恰有 444 个满足 h(x)=k(x)h(x)=k(x)h(x)=k(x)，所以精确概率为
4232=1230≈9.313×10−10.\frac{4}{2^{32}} =\frac{1}{2^{30}} \approx9.313\times10^{-10}. 2324 =2301 ≈9.313×10−10.
题目给出的选项为 000、117\frac1{17}171 、13\frac1331 、111。精确概率并不等于 000，但它与 000 的距离最小，因此选择 A。
十、核心性质五：如何快速计算多次变换
设函数 hhh 对应的线性变换矩阵为 HHH。连续执行两次 hhh 得到
h(h(x))=H(Hx)=H2x.h(h(x))=H(Hx)=H^2x. h(h(x))=H(Hx)=H2x.
连续执行 nnn 次得到
hn(x)=Hnx.h^n(x)=H^nx. hn(x)=Hnx.
如果直接循环执行 nnn 次，关于 nnn 的时间复杂度为
O(nP(w)),O(nP(w)), O(nP(w)),
其中 P(w)P(w)P(w) 表示对 www 位变换进行一次处理的成本。
可以对变换矩阵使用二进制快速幂：
每轮都把 nnn 除以 222，循环轮数为
Θ(logn).\Theta(\log n). Θ(logn).
因此总时间为
O(P(w)logn).O(P(w)\log n). O(P(w)logn).
题目只比较关于 nnn 的渐进次数，所以选择
O(logn).O(\log n). O(logn).
十一、六个小问逐问解析
第（1）问
判断：输入
时，程序不会输出任何数字。
结论：错误。
end 的类型是 unsigned，所以 -1 转换后为
232−1=4294967295.2^{32}-1=4294967295. 232−1=4294967295.
函数 hhh 是双射，因此方程
h(x)=2024h(x)=2024 h(x)=2024
在全部 323232 位无符号整数中有唯一解。使用逆函数计算得到
x=861247625.x=861247625. x=861247625.
核验：
h(861247625)=2024.h(861247625)=2024. h(861247625)=2024.
并且
1≤861247625≤4294967295,1\le861247625\le4294967295, 1≤861247625≤4294967295,
所以它位于枚举区间内。程序最终会输出
861247625 mod 13=4,861247625\bmod13=4, 861247625mod13=4,
并输出命中数 111。
易错点：程序需要枚举约 2322^{32}232 个数，实际运行非常慢。“短时间内看不到输出”不等于“数学上不会输出”。
第（2）问
判断：把循环变量 i 改为 unsigned int 后，程序可能无法结束。
结论：正确。
当
end=232−1\text{end}=2^{32}-1 end=232−1
时，unsigned int i 到达最大值后执行 i++，会回绕到 000：
(232−1)+1≡0(mod232).(2^{32}-1)+1\equiv0\pmod{2^{32}}. (232−1)+1≡0(mod232).
因为所有 323232 位无符号整数都不大于 end，循环条件始终成立，程序无法正常退出。
易错点：不要把无符号溢出理解成得到 2322^{32}232；这个值超出 323232 位范围，实际结果会按模 2322^{32}232 回到 000。
第（3）问
判断：对所有合法输入，输出的 count 不可能超过 111。
结论：正确。
关键证据是 hhh 的三步异或移位均可逆，因此 hhh 是双射。对于固定 target，全集中只有一个原像。任意枚举区间最多包含这个原像一次，所以
count∈{0,1}.\text{count}\in\{0,1\}. count∈{0,1}.
易错点：不能只凭样例或少量枚举猜测“一般不会重复”，必须用可逆性证明不会重复。
第（4）问
问题：均匀随机选择一个 unsigned x，h(x)=k(x)h(x)=k(x)h(x)=k(x) 的概率最接近哪个选项？
选项：
* A：000
* B：117\frac1{17}171
* C：13\frac1331
* D：111
结论：A。
hhh 与 kkk 都是 GF(2)GF(2)GF(2) 上的线性变换。方程
h(x)=k(x)h(x)=k(x) h(x)=k(x)
对应矩阵秩为 303030 的齐次线性方程组，所以解空间维数为 222，共有 444 个解。精确概率为
4232=2−30.\frac4{2^{32}}=2^{-30}. 2324 =2−30.
该概率约为 9.313×10−109.313\times10^{-10}9.313×10−10，最接近 000。
易错点：答案 A 表示“给定选项中最接近 000”，并不表示精确概率等于 000。
第（5）问
问题：计算 hn(x)h^n(x)hn(x) 时，关于 nnn 的最小渐进次数是哪一项？
选项：
* A：O(1)O(1)O(1)
* B：O(logn)O(\log n)O(logn)
* C：O(log2n)O(\log^2 n)O(log2n)
* D：O(n)O(n)O(n)
结论：B。
把 hhh 看成固定线性变换 HHH，连续执行 nnn 次就是计算
Hnx.H^nx. Hnx.
使用变换快速幂，每轮将指数减半，需要 Θ(logn)\Theta(\log n)Θ(logn) 轮，因此总时间可表示为
O(P(w)logn).O(P(w)\log n). O(P(w)logn).
只看关于 nnn 的次数，就是 O(logn)O(\log n)O(logn)。
易错点：O(logn)O(\log n)O(logn) 是关于迭代次数 nnn 的结论；每次矩阵或线性变换合成本身仍有与字长 www 有关的成本。
第（6）问
问题：输入
时，第一个输出的数是哪一个？
选项：
* A：333
* B：555
* C：777
* D：111111
结论：D。
程序寻找满足
h(x)=100h(x)=100 h(x)=100
的整数。由于 hhh 是双射，解唯一。逆转三次异或移位可得
x=1711328604.x=1711328604. x=1711328604.
核验：
h(1711328604)=100.h(1711328604)=100. h(1711328604)=100.
程序输出的是 xxx 除以 131313 的余数：
1711328604 mod 13=11.1711328604\bmod13=11. 1711328604mod13=11.
所以选择 D。
易错点：程序输出的不是原像 171132860417113286041711328604，也不是函数值 100100100，而是原像对 131313 取模后的结果。
十二、辅助验证代码
下面的代码可以直接验证可逆性、第（1）问和第（6）问的数值结论。
输出为：
下面的代码用二进制高斯消元计算 h(x)=k(x)h(x)=k(x)h(x)=k(x) 的方程秩。
十三、复杂度与程序改进
13.1 原程序复杂度
设枚举区间长度为
L=end−start+1.L=\text{end}-\text{start}+1. L=end−start+1.
函数 hhh 只执行固定次数的位运算，每次调用为 O(1)O(1)O(1)，所以原程序的时间复杂度为
O(L).O(L). O(L).
程序只使用常数个变量，空间复杂度为
O(1).O(1). O(1).
当区间覆盖整个 323232 位无符号整数范围时，LLL 接近 2322^{32}232，直接枚举的实际运行时间很长。
13.2 利用可逆性改进查找
既然 hhh 是双射，可以直接计算
x=h−1(target).x=h^{-1}(\text{target}). x=h−1(target).
然后判断
start≤x≤end.\text{start}\le x\le\text{end}. start≤x≤end.
如果成立，输出 x mod 13x\bmod13xmod13 和 111；否则输出 000。固定为 323232 位时，逆变换只需要常数次位运算，因此时间复杂度可降为
O(1).O(1). O(1).
改进后的程序如下：
十四、最终答案
小问 答案 核心依据 第（1）问 错误 -1 转为 UINT_MAX，202420242024 的唯一原像位于区间内 第（2）问 正确 323232 位循环变量在 UINT_MAX+1 后回绕为 000 第（3）问 正确 hhh 是双射，固定目标值最多有一个原像 第（4）问 A 精确概率为 2−302^{-30}2−30，最接近 000 第（5）问 B 对线性变换使用快速幂，需要 O(logn)O(\log n)O(logn) 轮 第（6）问 D h−1(100)=1711328604h^{-1}(100)=1711328604h−1(100)=1711328604，且
1711328604 mod 13=111711328604\bmod13=111711328604mod13=11
最终答案为：
