逻辑右移：不同语言与架构对边界条件的处理

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3k 阅读时长 ≈ 4 分钟

讨论一个问题：一个 32 位的整数，如果逻辑右移 32 位，结果如何？

先说结论：对于 C++ 是未定义行为，不同架构有不同处理，某些处理从数学角度看可能有问题；对于 CUDA (PTX) 和 Python，行为定义得更好，这个 case 下结果为 0.

逻辑右移：数学视角 vs 硬件视角

大胆揣测一下，提到“移位”，大部分计算机专业学生的第一反应都是硬件视角，即二进制表示层面，将各 bit 逐个向左或向右移动一个整数 n 位。 这就涉及到 n 的合法范围问题。

注意，这涉及两个层面的考量，其一是编程语言层面，其二是处理器硬件架构层面，需要区分的地方将特别注明。 另外，主要讨论无符号整数的逻辑右移，也就不涉及有符号数的补 0 还是补 1 问题，也不考虑舍入问题了。

硬件视角

在 32 位语境下，寄存器位宽最大 32 位，一条 32 位整数的右移指令，原则上只应允许 \(n\in[31]\)，即 1~31 的整数。 当然，这很容易扩展到 \(n=0\) 的情况——右移 0 位，相当于什么都不做，也就是一个 nop. 对于 \(n>32\) 的场景，以及 \(n<0\) 的场景，似乎也很好处理，只要禁止这些取值——具体怎么禁止，后文讨论。 事实上，如果定义 n 是一个无符号数，可以直接绕过 \(n<0\) 的场景。 现实中，架构层面上，常见的架构应该都是视其为无符号数。

那么 \(n=32\) 怎么办呢？ 一种直觉的处理是，视为 \(n>32\) 的同类——移动 32 或更多位，意味着原始值的任一 bit 都不在输出中，那么 32 和 33 甚至 100 也没什么区别。 尤其是考虑到 31 是一个 5 位无符号数，而从 32 开始就是 6 位及以上的无符号数了（后文将展示为什么位宽有影响）。

数学视角

数学上，一个 N-bit 无符号数 \(x<2^N\) 逻辑右移 \(n\ge 0\) 位，等价于计算 \[\left\lfloor \frac{x}{2^n} \right\rfloor.\]

从这个角度看，最合理的做法，首先是将 \(n\) 定义为无符号数，毕竟不应该“右移”之后结果反而变大了——那是左移该做的事。

其次，就是对于 \(n\ge N\)，最合理的做法是直接返回 0 ——这和上面的数学定义是一致的。 因此，完全可以将 \(n>N\) 直接看作 \(n=N\)，因为效果是相同的。

因此从数学视角，对于 32 位无符号整数，应该将 \(n=32\) 定义为合理场景，并返回 0（所有 bit 都移出寄存器了）。对于 \(n>32\)，直接当成 32 处理即可。

定义和实现

怎么定义和实现逻辑右移，尤其是 \(n=32\) 这个边界条件？对于正常范围的定义和实现都很明确了，问题其实是讨论“怎么禁止”前述的不合法情况。

在编程语言层面，如果编译期（或汇编期）发现 n 是一个不合法取值，可以告警或直接报错。 如果 n 是一个运行时变量，那么编程语言可以做两个选择：

  1. 不管了，直接当成未定义行为——很直接，但很不负责任，没错，我们 C++ 就是这么厉害的语言:-)
  2. 对 n 做 clamp（好像没有共识的翻译，或许可以叫“压缩”，但也不应该叫“截断”，毕竟截断应该是一个二进制层面的操作），即小于最小值的视为最小值，大于最大值的视为最大值；CUDA (PTX) 是这样做的，而且它将 n 定义为无符号数，所以不存在 \(n<0\) 的 case，而 \(n>32\) 将被 clamp 到 32.

C++:

lhs >> rhs

If the value of rhs is negative or is not less than the number of bits in lhs, the behavior is undefined.

PTX:

shr.type d, a, b;

Shift a right by the amount specified by unsigned 32-bit value in b.

硬件层面，能想到的处理是 mask 或 clamp. x86 继承了古老的遗产，选择的方案是最简单的 mask，唯一合理的 mask 是 \(2^5-1\)=0x1f. 首先，这确实解决了 \(n<0\) 的 case，因为 32 位整数用这个 mask 视角看其实是无符号数。 其次，这导致 x86 上 \(n=32\) 只能和 \(n>32\) 归为一类，x86 为这种 case 选择的处理是“无事发生”——相当于 nop. 从结果上看，\(n=0\) 和 \(n>31\) 都是 nop，这还真是最硬件的视角。 NVIDIA GPU 和 Armv7 的处理更现代一点，选择了 clamp，首先视为无符号数，然后 \(n>32\) 将被 clamp 到 32.

到这里，其实可以看出，硬件指令集和编程语言之间有着紧密的联系，C/C++ 和 x86 作为古老组，倾向于“未定义”和 mask 这种简单做法，或许也受制于当时的条件。 而更现代的指令集和语言则倾向于通过 clamp 扩展到 \(n\in\{0\}\cup[32]\) 的支持，并做了明确定义。

x86:

SHR r/m32, CL

SHR r/m32, imm8

The count operand can be an immediate value or the CL register. The count is masked to 5 bits (or 6 bits with a 64-bit operand). The count range is limited to 0 to 31 (or 63 with a 64-bit operand).

NVIDIA GPU:

同上文的 PTX 定义.

Armv7:

LSR{S}{cond} Rd, Rm, Rs

LSR{S}{cond} Rd, Rm, #sh

Rs is a register holding a shift value to apply to the value in Rm. Only the least significant byte is used.

sh is a constant shift. The range of values permitted is 1-32.

虽然 Armv7 Rs 只说了用最低的 byte（类似 x86 CL 寄存器），没说到底是 mask 还是 clamp，但从和立即数保持一致考虑，以及实验验证，判断应该是 clamp 到 1-32 区间。 实验中也发现，虽然定义没说右移 0 位的情况，但立即数取 0 可以通过汇编，不论是立即数还是寄存器，右移 0 位结果是无事发生，相当于 nop.

而对于 Python 3 这种解释器/虚拟机语言，直接按照数学定义即可。

Python:

A right shift by n bits is defined as floor division by pow(2,n).

评价

综合上面的讨论，可以看出现代指令集和语言的处理基本都是将无符号数 n 通过 clamp 限定在 \(n\in\{0\}\cup[32]\) 区间，从而符合逻辑右移的数学定义。 但 C/C++ 和 x86 则是未定义 \(n\ge 32\) 的情况，导致边界条件上和数学定义不一致。

具体实现中，对于 C++，如果编译器发现 \(n\ge 32\)，会编译器告警，在 GCC 上，如果开启 -O3 优化，结果会被编译器优化为 0，也算是符合数学定义。 但运行时遇到 \(n\ge 32\) 以及不开启编译器优化时，则依赖于目标架构的逻辑右移实现。 在 Armv7 这类架构上，应该返回 0，和数学定义一致。 而对于 x86 架构，这种情况则会当作无事发生，与数学定义不符。

这种不一致，在特定算法中可能导致意料之外的麻烦，比如“除数为常数的无符号整数除法”。如果有空，且听下回分解。