如何用最简单粗暴的方法理解 unsigned 神力

· · 科技·工程

没判 |t_1|=|t_2| 的我，在离开“世界”之前在干什么呢？

继续集训。

同机房的一位厉害同学在调试 CSP-S 2025 T4 的 O(n^3) 代码（他赛时没过最后一题）。

他抱怨道：“怎么 T 了两个点啊？”

我过去一看，DP，看不懂。但是我注意到他的代码中有很多的 %mod。于是我不知怎的联想到了这篇文章，遂向他建议道：“你把 long long 换成 unsigned long long 试试？”

随后他做了。A 了。

“啊？？？？？”

两个小时后，我发觉我希望理解为什么 unsigned 类型具有如此的神力。随后我想到一个东西，汇编。

首先我不知道怎么写汇编。但是，我们可以近似认为，汇编代码中每一个指令的时间复杂度都是接近 O(1) 的。

我们不难编出如下的简单测试代码：

#include<random>
using namespace std;
const int N=2e7+10,mod=998244353;
random_device rd;
mt19937 mt(rd());
using ull=unsigned long long;
ull a[N],ret;
void proc(){
    for(int i=0;i<N;i++)a[i]=mt();
    ret=1;
    for(int i=0;i<N;i++)ret=ret*a[i]%mod;
}

将该代码写入 Compiler Explorer 的代码编辑器中，指定编译器为 GCC 9.3，使用编译参数 -std=c++14 -O2 后，可以得到一串汇编代码。

简单起见，我们忽略相同代码，仅在这里展示有显著不同的代码。此处展示的代码基本上是上面的代码块中倒数第二行的实际内容。（下面的代码语言使用 Web Assembly，因为 asm 和 assembly 都没法启用代码高亮）

.L33:
        mov     QWORD PTR mt[rip+4992], r9
        mov     edx, 1
        movabs  r8, -8525806094425994177
.L18:
        mov     rdi, QWORD PTR [rcx]
        add     rcx, 8
        imul    rdi, rdx
        mov     rax, rdi
        mul     r8
        shr     rdx, 29
        imul    rdx, rdx, 998244353
        sub     rdi, rdx
        mov     rdx, rdi
        cmp     rsi, rcx
        jne     .L18
        mov     QWORD PTR ret[rip], rdi
        ret

而将上面的代码中的 unsigned 删掉之后，变成了这样：

.L33:
        mov     QWORD PTR mt[rip+4992], r9
        mov     edx, 1
        movabs  r8, 155014655926305585
.L18:
        mov     rdi, QWORD PTR [rcx]
        add     rcx, 8
        imul    rdi, rdx
        mov     rax, rdi
        imul    r8
        mov     rax, rdi
        sar     rax, 63
        sar     rdx, 23
        sub     rdx, rax
        imul    rdx, rdx, 998244353
        sub     rdi, rdx
        mov     rdx, rdi
        cmp     rsi, rcx
        jne     .L18
        mov     QWORD PTR ret[rip], rdi
        ret

我们首先观察一下上面的代码。发现两个代码都有一个奇怪的常数，上面的是 -8525806094425994177，下面的是 155014655926305585。一个常数？很奇怪。不过不要急，我们从 P6276 那里偷一个 Barrett 模乘的模板过来：

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

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};

我们发现这个常数的作用和上面代码里面的 m 很像。由此，我们发现编译器自动对模数固定的取模使用了 Barrett 模乘进行优化。实际上，即使不指定 -O2 参数，编译器仍然会进行 Barrett 模乘优化。

现在，我们直接将上面的两个汇编代码块丢进 Diffing Tool 里面进行比较，发现无符号整数和有符号整数的取模部分在汇编意义上真正不同的代码很短：

        mul     r8
        shr     rdx, 29
        imul    r8
        mov     rax, rdi
        sar     rax, 63
        sar     rdx, 23
        sub     rdx, rax

在这里，mul 与 imul 分别为汇编乘法运算的无符号和有符号版本，shr 与 sar 分别为向右位移的无符号和有符号版本。查阅资料后可以发现，sar 在右移时会保留符号位不变，而 shr 不会。这就导致 sar 可能在右移过程中设置一些本来为 0 的位置为 1。

但无论如何，在这一段代码上，无符号只用两行，有符号用五行，无符号的开销低于有符号的一半！

由此，我们以最简单粗暴的方法领略了 unsigned 神力。