异或移位变换、无符号整数与线性映射

目录

• 一、原程序
• 二、代码目的与解决的问题
• 三、变量、函数与类型含义
• 四、完整代码逐行注解
• 五、程序执行流程
• 六、核心性质一：异或移位为什么可逆
• 七、核心性质二：为什么命中数不超过 1
• 八、核心性质三：无符号整数的边界与回绕
• 九、核心性质四：概率为什么是二的负整数次幂
• 十、核心性质五：如何快速计算多次变换
• 十一、六个小问逐问解析
• 十二、辅助验证代码
• 十三、复杂度与程序改进
• 十四、最终答案

---

一、原程序

#include <bits/stdc++.h>
using namespace std;

unsigned h(unsigned x) {
    x ^= x << 2;
    x ^= x >> 7;
    x ^= x << 1;
    return x;
}

unsigned k(unsigned x) {
    return (x >> 3) ^ (x >> 1) ^ x ^ (x << 4) ^ (x << 2);
}

int main() {
    unsigned target, start, end;
    cin >> target >> start >> end;
    int count = 0;
    for (unsigned long long i = start; i <= end; i++) {
        if (h(i) == target) {
            cout << i % 13 << " ";
            count++;
        }
    }
    cout << endl << count << endl;
    return 0;
}

二、代码目的与解决的问题

程序读入目标值 $\text{target}$ 和区间端点 $\text{start},\text{end}$，在闭区间

$$[\text{start},\text{end}]$$

内依次枚举整数 $i$。

如果某个 $i$ 满足

$$h(i)=\text{target},$$

程序就输出

$$i\bmod 13,$$

并把命中数量加 $1$。枚举结束后，程序输出总命中数 $\text{count}$。

函数 $h$ 由三次异或移位操作组成：

$$x\mathrel{\hat{\ }}=x\ll2,$$

$$x\mathrel{\hat{\ }}=x\gg7,$$

$$x\mathrel{\hat{\ }}=x\ll1.$$

这里的 ^ 表示按位异或，<< 表示左移，>> 表示右移。

函数 $k$ 没有在主程序中被调用，只在后面的小问中用于研究方程

$$h(x)=k(x)$$

成立的概率。

三、变量、函数与类型含义

名称	类型	含义
target	unsigned	希望函数 $h$ 得到的目标值
start	unsigned	枚举区间左端点
end	unsigned	枚举区间右端点
i	unsigned long long	当前枚举的整数
count	int	满足 $h(i)=\text{target}$ 的整数个数
h(x)	unsigned	三次异或移位组成的变换
k(x)	unsigned	另一种异或移位线性变换

在常见的运行环境中：

$$\operatorname{sizeof}(\texttt{unsigned})=4,$$

所以 unsigned 通常是 $32$ 位无符号整数，取值范围为

$$0\le x\le 2^{32}-1=4294967295.$$

unsigned long long 通常是 $64$ 位无符号整数，能够表示 $2^{32}$，所以枚举变量越过 UINT_MAX 后不会立刻回到 $0$。

四、完整代码逐行注解

#include <bits/stdc++.h>                 // 引入常用标准库
using namespace std;

// 对一个 32 位无符号整数进行三次异或移位变换
unsigned h(unsigned x) {
    x ^= x << 2;                         // x = x ^ (x << 2)
    x ^= x >> 7;                         // x = x ^ (x >> 7)
    x ^= x << 1;                         // x = x ^ (x << 1)
    return x;                            // 返回变换后的 32 位结果
}

// 另一个 32 位线性变换，只在问题分析中与 h 比较
unsigned k(unsigned x) {
    return (x >> 3) ^ (x >> 1) ^ x
           ^ (x << 4) ^ (x << 2);
}

int main() {
    unsigned target, start, end;
    cin >> target >> start >> end;       // 读入目标值与闭区间端点

    int count = 0;                       // 当前还没有找到满足条件的数

    // i 使用 64 位类型，避免 i=UINT_MAX 后自增回到 0
    for (unsigned long long i = start; i <= end; i++) {
        // 调用 h 时，i 会转换为 32 位 unsigned。
        // 因为循环中 i<=end<=UINT_MAX，所以不会丢失有效位。
        if (h(i) == target) {
            cout << i % 13 << " ";       // 输出原像除以 13 的余数
            count++;                     // 记录命中数量
        }
    }

    cout << endl << count << endl;       // 换行后输出命中总数
    return 0;
}

五、程序执行流程

程序的执行顺序如下。

1. 读入 $\text{target}$、$\text{start}$ 和 $\text{end}$。

2. 令 $\text{count}=0$。

3. 从 $\text{start}$ 到 $\text{end}$ 枚举 $i$。

4. 计算 $h(i)$。

5. 如果 $h(i)=\text{target}$，输出 $i\bmod13$，并令 $\text{count}$ 加 $1$。

6. 枚举结束后输出 $\text{count}$。

可以写成下面的数据流：

输入 target、start、end
          ↓
在 [start,end] 内枚举 i
          ↓
       计算 h(i)
          ↓
h(i) 是否等于 target？
    ↙ 否          ↘ 是
继续枚举      输出 i%13，count++
          ↓
       输出 count

六、核心性质一：异或移位为什么可逆

6.1 x ^= x << s 的逐位关系

设原数的第 $j$ 个二进制位为 $x_j$，变换结果的第 $j$ 个二进制位为 $y_j$。执行

y = x ^ (x << s);

后，有

$$y_j= \begin{cases} x_j, & 0\le j<s,\\ x_j\oplus x_{j-s}, & j\ge s. \end{cases}$$

其中 $\oplus$ 表示异或。

最低的 $s$ 位没有受到左移部分影响，所以能够直接得到：

$$x_j=y_j,\qquad 0\le j<s.$$

恢复低 $s$ 位后，就能继续恢复下一组：

$$x_j=y_j\oplus x_{j-s},\qquad j\ge s.$$

因此可以从低位向高位逐位恢复原数。

6.2 一个完整的 8 位例子

使用 $8$ 位无符号整数，令 $s=2$，原数为

x = 00101101

左移两位后，高位超出 $8$ 位的部分丢弃：

x << 2 = 10110100

异或得到：

  00101101
^ 10110100
------------
  10011001

所以结果为

y = 10011001

现在只根据 $y$ 恢复 $x$。从右向左每两位分为一组：

y = 10 01 10 01

最低一组不受左移部分影响：

x 的最低一组 = 01

恢复下一组：

10 ^ 01 = 11

继续恢复：

01 ^ 11 = 10
10 ^ 10 = 00

从高到低重新组合：

x = 00 10 11 01
  = 00101101

原数被唯一恢复，因此这个变换是可逆的。

6.3 有限次异或消去

对于固定字长 $w$，也可以使用有限次异或移位恢复。恢复

$$y=x\oplus(x\ll s)$$

时，可以执行：

uint32_t undoLeft(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x << shift;
    }
    return x;
}

循环中的位移量依次为

$$s,2s,4s,8s,\ldots$$

超过字长后，继续左移已经不会贡献有效位，所以循环结束。

前面的 $8$ 位例子可以直接恢复：

初始 x = 10011001

x ^= x << 2：
  10011001
^ 01100100
------------
  11111101

x ^= x << 4：
  11111101
^ 11010000
------------
  00101101

6.4 x ^= x >> s 为什么也可逆

设

y = x ^ (x >> s);

右移不会影响最高的 $s$ 位，所以可以先恢复最高的 $s$ 位，再从高位向低位逐组恢复。

对应的逆函数为：

uint32_t undoRight(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x >> shift;
    }
    return x;
}

6.5 函数 $h$ 为什么可逆

函数 $h$ 依次进行了：

1. 左移 $2$ 位异或；

2. 右移 $7$ 位异或；

3. 左移 $1$ 位异或。

每一步都是双射。双射的复合仍然是双射，所以 $h$ 是全部 $32$ 位无符号整数集合上的双射。

若要从目标值 $y=h(x)$ 恢复 $x$，必须按照相反顺序撤销：

uint32_t inverseH(uint32_t y) {
    y = undoLeft(y, 1);   // 撤销最后一步 x ^= x << 1
    y = undoRight(y, 7);  // 撤销中间一步 x ^= x >> 7
    y = undoLeft(y, 2);   // 撤销第一步 x ^= x << 2
    return y;
}

七、核心性质二：为什么命中数不超过 1

因为 $h$ 是双射，所以对于任意 unsigned target，方程

$$h(x)=\text{target}$$

在全部 $32$ 位无符号整数中恰好有一个解。

证明如下。

假设存在两个不同的整数 $x_1\ne x_2$，同时满足

$$h(x_1)=h(x_2)=\text{target}.$$

由于 $h$ 可逆，在等式两边同时执行 $h^{-1}$，得到

$$x_1=h^{-1}(\text{target})=x_2,$$

这与 $x_1\ne x_2$ 矛盾。

因此全集中只有一个原像。闭区间 $[\text{start},\text{end}]$ 只是全集的一个子集，所以区间内的命中数只可能为

$$0\quad\text{或}\quad1.$$

也就是说：

$$\text{count}\le1.$$

八、核心性质三：无符号整数的边界与回绕

8.1 -1 读入 unsigned 后的值

在常见的 $32$ 位 unsigned 环境中，负数转换为无符号整数时按模 $2^{32}$ 处理。因此

$$-1\equiv2^{32}-1\pmod{2^{32}},$$

所以读入 -1 后，end 的值为

$$4294967295.$$

于是输入

2024 1 -1

实际枚举的区间是

$$[1,4294967295].$$

8.2 为什么原程序使用 unsigned long long i

当 $i=4294967295$ 时，如果 $i$ 是 $64$ 位无符号整数，那么执行 i++ 后得到

$$4294967296.$$

此时

$$4294967296>4294967295,$$

循环条件失败，程序结束。

8.3 改成 unsigned int i 会发生什么

若循环变量只有 $32$ 位，那么最大值加 $1$ 会按模 $2^{32}$ 回绕：

$$(2^{32}-1)+1\equiv0\pmod{2^{32}}.$$

于是：

4294967295 + 1 → 0

当 end=4294967295 时，任意 $32$ 位无符号整数都满足

$$i\le\text{end}.$$

所以循环会从 $0$ 再次开始，无法正常结束。

九、核心性质四：概率为什么是二的负整数次幂

9.1 异或与移位是 $GF(2)$ 上的线性运算

一个 $32$ 位无符号整数可以看成一个 $32$ 维二进制向量：

$$x=(x_0,x_1,\ldots,x_{31}),\qquad x_i\in\{0,1\}.$$

异或就是二进制域 $GF(2)$ 上的加法。左移和右移只是把各位移动到新的位置并在空位补 $0$，因此也是线性变换。

所以存在两个 $32\times32$ 的二进制矩阵 $H,K$，使得

$$h(x)=Hx,$$

$$k(x)=Kx.$$

9.2 把函数相等转化为齐次方程

条件

$$h(x)=k(x)$$

等价于

$$Hx=Kx.$$

在 $GF(2)$ 中，减法与加法相同，因此

$$(H-K)x=0$$

也可以写成

$$(H\oplus K)x=0.$$

这变成了一个 $32$ 元齐次线性方程组。

9.3 如何得到矩阵的秩

令 $e_j$ 表示只有第 $j$ 位为 $1$ 的单位向量。线性变换矩阵的第 $j$ 列就是

$$h(e_j)\oplus k(e_j).$$

对 $j=0,1,\ldots,31$ 依次计算这些列，再进行二进制高斯消元，得到

$$\operatorname{rank}(H-K)=30.$$

根据秩—零度定理，零空间维数为

$$32-30=2.$$

因此方程共有

$$2^2=4$$

个解。

四个实际解为：

0
994850162
2603816851
2692686561

将它们分别代入，都满足 $h(x)=k(x)$。

9.4 概率计算

全部 $32$ 位无符号整数共有

$$2^{32}$$

个，其中恰有 $4$ 个满足 $h(x)=k(x)$，所以精确概率为

$$\frac{4}{2^{32}} =\frac{1}{2^{30}} \approx9.313\times10^{-10}.$$

题目给出的选项为 $0$、$\frac1{17}$、$\frac13$、$1$。精确概率并不等于 $0$，但它与 $0$ 的距离最小，因此选择 A。

十、核心性质五：如何快速计算多次变换

设函数 $h$ 对应的线性变换矩阵为 $H$。连续执行两次 $h$ 得到

$$h(h(x))=H(Hx)=H^2x.$$

连续执行 $n$ 次得到

$$h^n(x)=H^nx.$$

如果直接循环执行 $n$ 次，关于 $n$ 的时间复杂度为

$$O(nP(w)),$$

其中 $P(w)$ 表示对 $w$ 位变换进行一次处理的成本。

可以对变换矩阵使用二进制快速幂：

result = 单位变换
base = H

while n > 0:
    如果 n 的最低位是 1：
        result = result 与 base 复合

    base = base 与 base 复合
    n = n / 2

每轮都把 $n$ 除以 $2$，循环轮数为

$$\Theta(\log n).$$

因此总时间为

$$O(P(w)\log n).$$

题目只比较关于 $n$ 的渐进次数，所以选择

$$O(\log n).$$

十一、六个小问逐问解析

第（1）问

判断：输入

2024 1 -1

时，程序不会输出任何数字。

结论：错误。

end 的类型是 unsigned，所以 -1 转换后为

$$2^{32}-1=4294967295.$$

函数 $h$ 是双射，因此方程

$$h(x)=2024$$

在全部 $32$ 位无符号整数中有唯一解。使用逆函数计算得到

$$x=861247625.$$

核验：

$$h(861247625)=2024.$$

并且

$$1\le861247625\le4294967295,$$

所以它位于枚举区间内。程序最终会输出

$$861247625\bmod13=4,$$

并输出命中数 $1$。

易错点：程序需要枚举约 $2^{32}$ 个数，实际运行非常慢。“短时间内看不到输出”不等于“数学上不会输出”。

第（2）问

判断：把循环变量 i 改为 unsigned int 后，程序可能无法结束。

结论：正确。

当

$$\text{end}=2^{32}-1$$

时，unsigned int i 到达最大值后执行 i++，会回绕到 $0$：

$$(2^{32}-1)+1\equiv0\pmod{2^{32}}.$$

因为所有 $32$ 位无符号整数都不大于 end，循环条件始终成立，程序无法正常退出。

易错点：不要把无符号溢出理解成得到 $2^{32}$；这个值超出 $32$ 位范围，实际结果会按模 $2^{32}$ 回到 $0$。

第（3）问

判断：对所有合法输入，输出的 count 不可能超过 $1$。

结论：正确。

关键证据是 $h$ 的三步异或移位均可逆，因此 $h$ 是双射。对于固定 target，全集中只有一个原像。任意枚举区间最多包含这个原像一次，所以

$$\text{count}\in\{0,1\}.$$

易错点：不能只凭样例或少量枚举猜测“一般不会重复”，必须用可逆性证明不会重复。

第（4）问

问题：均匀随机选择一个 unsigned x，$h(x)=k(x)$ 的概率最接近哪个选项？

选项：

• A：$0$
• B：$\frac1{17}$
• C：$\frac13$
• D：$1$

结论：A。

$h$ 与 $k$ 都是 $GF(2)$ 上的线性变换。方程

$$h(x)=k(x)$$

对应矩阵秩为 $30$ 的齐次线性方程组，所以解空间维数为 $2$，共有 $4$ 个解。精确概率为

$$\frac4{2^{32}}=2^{-30}.$$

该概率约为 $9.313\times10^{-10}$，最接近 $0$。

易错点：答案 A 表示“给定选项中最接近 $0$”，并不表示精确概率等于 $0$。

第（5）问

问题：计算 $h^n(x)$ 时，关于 $n$ 的最小渐进次数是哪一项？

选项：

• A：$O(1)$
• B：$O(\log n)$
• C：$O(\log^2 n)$
• D：$O(n)$

结论：B。

把 $h$ 看成固定线性变换 $H$，连续执行 $n$ 次就是计算

$$H^nx.$$

使用变换快速幂，每轮将指数减半，需要 $\Theta(\log n)$ 轮，因此总时间可表示为

$$O(P(w)\log n).$$

只看关于 $n$ 的次数，就是 $O(\log n)$。

易错点：$O(\log n)$ 是关于迭代次数 $n$ 的结论；每次矩阵或线性变换合成本身仍有与字长 $w$ 有关的成本。

第（6）问

问题：输入

100 1 4294967295

时，第一个输出的数是哪一个？

选项：

• A：$3$
• B：$5$
• C：$7$
• D：$11$

结论：D。

程序寻找满足

$$h(x)=100$$

的整数。由于 $h$ 是双射，解唯一。逆转三次异或移位可得

$$x=1711328604.$$

核验：

$$h(1711328604)=100.$$

程序输出的是 $x$ 除以 $13$ 的余数：

$$1711328604\bmod13=11.$$

所以选择 D。

易错点：程序输出的不是原像 $1711328604$，也不是函数值 $100$，而是原像对 $13$ 取模后的结果。

十二、辅助验证代码

下面的代码可以直接验证可逆性、第（1）问和第（6）问的数值结论。

#include <bits/stdc++.h>
using namespace std;

uint32_t h(uint32_t x) {
    x ^= x << 2;
    x ^= x >> 7;
    x ^= x << 1;
    return x;
}

uint32_t undoLeft(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x << shift;
    }
    return x;
}

uint32_t undoRight(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x >> shift;
    }
    return x;
}

uint32_t inverseH(uint32_t y) {
    y = undoLeft(y, 1);
    y = undoRight(y, 7);
    y = undoLeft(y, 2);
    return y;
}

int main() {
    uint32_t x1 = inverseH(2024);
    cout << x1 << " " << h(x1) << " " << x1 % 13 << '\n';

    uint32_t x2 = inverseH(100);
    cout << x2 << " " << h(x2) << " " << x2 % 13 << '\n';

    return 0;
}

输出为：

861247625 2024 4
1711328604 100 11

下面的代码用二进制高斯消元计算 $h(x)=k(x)$ 的方程秩。

#include <bits/stdc++.h>
using namespace std;

uint32_t h(uint32_t x) {
    x ^= x << 2;
    x ^= x >> 7;
    x ^= x << 1;
    return x;
}

uint32_t k(uint32_t x) {
    return (x >> 3) ^ (x >> 1) ^ x
           ^ (x << 4) ^ (x << 2);
}

int main() {
    uint32_t basis[32] = {};
    int rank = 0;

    // 第 j 列是 h(e_j) ^ k(e_j)
    for (int j = 0; j < 32; j++) {
        uint32_t v = h(uint32_t(1) << j)
                   ^ k(uint32_t(1) << j);

        for (int bit = 31; bit >= 0; bit--) {
            if (((v >> bit) & 1U) == 0) {
                continue;
            }

            if (basis[bit] != 0) {
                v ^= basis[bit];
            } else {
                basis[bit] = v;
                rank++;
                break;
            }
        }
    }

    cout << rank << '\n';              // 30
    cout << (32 - rank) << '\n';       // 零空间维数 2
    cout << (1U << (32 - rank)) << '\n'; // 解的个数 4
    return 0;
}

十三、复杂度与程序改进

13.1 原程序复杂度

设枚举区间长度为

$$L=\text{end}-\text{start}+1.$$

函数 $h$ 只执行固定次数的位运算，每次调用为 $O(1)$，所以原程序的时间复杂度为

$$O(L).$$

程序只使用常数个变量，空间复杂度为

$$O(1).$$

当区间覆盖整个 $32$ 位无符号整数范围时，$L$ 接近 $2^{32}$，直接枚举的实际运行时间很长。

13.2 利用可逆性改进查找

既然 $h$ 是双射，可以直接计算

$$x=h^{-1}(\text{target}).$$

然后判断

$$\text{start}\le x\le\text{end}.$$

如果成立，输出 $x\bmod13$ 和 $1$；否则输出 $0$。固定为 $32$ 位时，逆变换只需要常数次位运算，因此时间复杂度可降为

$$O(1).$$

改进后的程序如下：

#include <bits/stdc++.h>
using namespace std;

uint32_t undoLeft(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x << shift;
    }
    return x;
}

uint32_t undoRight(uint32_t y, int s) {
    uint32_t x = y;
    for (int shift = s; shift < 32; shift <<= 1) {
        x ^= x >> shift;
    }
    return x;
}

uint32_t inverseH(uint32_t y) {
    y = undoLeft(y, 1);
    y = undoRight(y, 7);
    y = undoLeft(y, 2);
    return y;
}

int main() {
    uint32_t target, start, end;
    cin >> target >> start >> end;

    uint32_t x = inverseH(target);

    if (start <= end && start <= x && x <= end) {
        cout << x % 13 << '\n';
        cout << 1 << '\n';
    } else {
        cout << '\n';
        cout << 0 << '\n';
    }

    return 0;
}

十四、最终答案

小问	答案	核心依据
第（1）问	错误	-1 转为 UINT_MAX，$2024$ 的唯一原像位于区间内
第（2）问	正确	$32$ 位循环变量在 UINT_MAX+1 后回绕为 $0$
第（3）问	正确	$h$ 是双射，固定目标值最多有一个原像
第（4）问	A	精确概率为 $2^{-30}$，最接近 $0$
第（5）问	B	对线性变换使用快速幂，需要 $O(\log n)$ 轮
第（6）问	D	$h^{-1}(100)=1711328604$，且 $1711328604\bmod13=11$

最终答案为：

错误，正确，正确，A，B，D