几乎总是无符号（2022）

# 几乎总是无符号 来源：https://graphitemaster.github.io/aau/ 作者：Dale Weiler - Twitter (https://twitter.com/actualGraphite) - GitHub (https://github.com/graphitemaster) 最后更新：2022年1月1日，星期六 对带符号整数算术的需求往往被误置，因为大多数整数在程序中从不表示负值。数组的索引和循环的迭代次数也反映了这一概念。我们应当更倾向于使用无符号整数而非有符号整数，然而多数代码却错误地几乎独占性地选择有符号整数。本文的动机主要适用于 C 和 C++，但也会提供其他语言（如 Go、Rust 和 Odin (https://odin-lang.org/)）的例子，试图说明这一概念适用于所有语言，无论它们的选择如何（例如，C 和 C++ 将有符号整数溢出设为未定义行为），而是算术本身固有的特性。 ## 反对无符号的论点{#the-arguments-against-unsigned} 有很多反对使用无符号整数的论点。让我解释为什么我认为它们大多不正确。 ### 安全性论点{#the-safety-argument} 反对使用无符号整数最常见的论点是它更容易出错，因为表达式下溢比溢出更容易发生。这种建议非常普遍，以至于官方的 Google C++ 风格指南 (https://google.github.io/styleguide/cppguide.html#Integer_Types) 直接不鼓励使用无符号类型。我们将在接下来的论点中看到这些安全问题来自何处，以及如何通过比处处使用有符号更容易理解的简单惯用法来轻松避免它们。我们还会看到这些论点在大多数情况下是不正确的，因为它们鼓励继续编写和使用不安全的代码。 ### 反向循环论点{#the-loop-in-reverse-argument} 当 for 循环的计数器需要反向计数，并且循环体需要在计数器也为零时执行时，大多数程序员会发现很难使用无符号类型，因为 `i >= 0` 总是计算为 `true`。于是人们倾向于将无符号值强制转换为有符号值，例如： ```c for (int64_t i = int64_t(size) - 1; i >= 0; i--) { // ... } ``` 当然这是危险的，因为它是一个窄化转换，并且强制转换会屏蔽一个合法的警告。在 C 和 C++ 中，当给定特定的大值时，它会引发未定义行为，并且极有可能被利用。大多数应用程序会在输入 `>= 0x7ffffffffffffffff` 时崩溃。典型的论点是这样的值是“病理性的”。这个论点不仅不正确，而且更加危险，我们稍后会看到。这种危险是始终使用有符号整数算术的支持论点之一。然而这个论点是不正确的，因为 `int64_t` 永远不会允许值 `>= 0x7ffffffffffffffff`。它只是回避了问题，即上述限制以上的特定有问题的数值范围不再被允许。如果你需要那么大的值，并且听从了谷歌的明智建议始终使用有符号并拥有那个大值，那么你将面临一个严重得多的问题，因为你无条件地触发了有符号溢出。对于像 C 和 C++ 这样的语言，这会引发未定义行为。而对于像 Go 和 Odin 这样的语言，它们会进行回绕，并且由于回绕行为，循环中的数值范围会出错。 这里的正确方法是：无符号下溢在 C 和 C++ 中是良好定义的，我们应该教授回绕算术的行为，因为它通常很有用，同时它也使反向迭代变得像正向迭代一样简单。 ```c for (size_t i = size - 1; i < size; i--) { // ... } ``` 这里的方法是从 `size - 1` 开始，每次迭代向下计数。当计数器达到零时，递减导致计数器下溢并回绕到无符号类型的最大值。这个值远大于 `size`，因此条件 `i < size` 计算为假，循环停止。像 Rust 这样的语言选择即使在 Debug 构建中也让无符号下溢成为陷阱表示，但诸如 `Range` 这样的特性可以让你安全地实现相同的在回绕时的高效行为，且语法更简洁。 ```rust for i in (0..size).rev() { // ... } ``` 使用这种方法，不需要强制转换，不会引入静默的错误，并且“病理性”输入也能正常工作。事实上，这种形式允许从 `[0, 0xffffffffffffffff]` 的每一个可能值，覆盖了整个范围。需要注意的是，如果 `size == 0`，这些循环仍然有效，因为 `0 - 1` 产生无符号类型的最大可能值，该值大于 `size`（仍然是 `0`），因此循环永远不会进入。 ### 两个数的差可能为负{#the-difference-of-two-numbers-can-become-negative} 当你想计算两个数之间的差（或增量）时，通常想要表示为： ```c delta = x - y; ``` 尽管大多数时候不需要符号，所以你往往写成和看到： ```c delta = abs(x - y); ``` 反对无符号的论点是这里很危险，因为如果 `y > x`，就会发生下溢。这个论点的问题是它不成立，因为无论 `x` 和 `y` 是有符号还是无符号，代码本身都是不正确的。存在一些 `x` 和 `y` 的值会导致有符号整数下溢。因此和之前一样，在 C 和 C++ 这样的语言中，你无条件地触发了未定义行为，因为有符号整数下溢是未定义的。事实证明，即使是在支持回绕行为的语言中，计算差值的差值对于有符号整数来说也很困难，例如 `INT_MAX - INT_MIN` 仍然会不正确。目前还没有简单的方法来安全地做到这一点；这是我所知道的最佳技术。 ```c if ((y > 0 && x < INT_MIN + y) || (y < 0 && x > INT_MAX + y)) { // 错误 } else { delta = abs(x - y); } ``` 然而对于无符号整数，更容易写成： ```c delta = max(x, y) - min(x, y); ``` 这将始终安全地给出绝对差值。这可能是个人偏好，但我觉得这也更容易阅读。名称 `delta` 不再必要，因为表达式本身就是自文档化的。 ### 用有符号算术计算索引更安全{#computing-indices-with-signed-arithmetic-is-safer} 上述论点的一个扩展是，如果你有一个更复杂的表达式来计算索引，用有符号来表达更安全。我认为这个论点主要源于对下溢和上溢的不正确直觉，但它却以更糟糕的方式表现在有符号上。让我们以最简单的“稍微复杂一些”的索引计算表达式为例：区间的中点。 ```c int mid = (low + high) / 2; ``` > 我选择这是一个真实世界、非刻意的例子。你可以在二分搜索、归并排序以及几乎任何其他分治算法中找到它。 这是大多数人会写的方式。low 和 high 的平均值，向最近的整数截断。当 `low` 和 `high` 的和超过 `2^31 - 1` 时，和会溢出为负值，并且除以 2 后仍然为负。使用更大的有符号整数类型也不能解决这个问题，因为和很容易超过 `2^63 - 1`。和前一个例子一样，这段代码并不理想。事实上，在任何语言中，如果没有库函数的帮助，安全地计算两个变量的中点几乎是不可能的，因为无论是回绕还是其他方式，都存在特定的输入会导致失败。对有符号的一个常见解决方法是重写为这个惯用法，但它在 `high = INT_MAX` 和 `low = INT_MIN` 时仍然会失败。 ```c int mid = low + (high - low) / 2; ``` 坚持使用无符号整数，你可能会认为可以用你最初想要的那种明显的方式写，因为下溢是良好定义的，但我们会看到这也有问题。 ```c size_t mid = (low + high) / 2; ``` 这实际上不适用于例如 `low = 0x80000000` 和 `high = 0x80000002`，这会导致下溢并产生 `2`，除以 `2` 得到 `1`，而正确的值实际上是 `0x80000001`。无符号在这里的好处是，当这些值用作数组索引时，有符号行为几乎肯定会产生无效索引，导致内存不安全问题。而无符号方式永远不会那样，它会保持有界，即使它产生的索引实际上是错误的。这是一个不那么严重的逻辑错误，但根据上下文仍然可以被恶意利用。无论有无符号，正确的安全方法是将所有内容转换为无符号，并使用掩码加法来处理回绕。 ```c T midpoint(T x, T y) { // U 是类型 T 的无符号版本，如果 T 已经无符号则与 T 相同 // digits 是类型 T 中的数字位数（不包括符号位）。 // C++ 中的 std::numeric_limits::digits 对此很有帮助。 U shift = digits - 1; U difference = (U)x - (U)y; U sign = y < x; U half = (difference / 2) + (sign << shift) + (sign & difference); T mid = (T)(x + half); return mid; } ``` > C++ 实际上有 `std::midpoint`，它正是做这件事的。 ### 无符号乘法可能溢出{#unsigned-multiplication-can-overflow} 当乘以无符号变量时，担心这样的表达式容易溢出并产生远小于正确值的值。这是一个非常常见的抱怨，特别是对于内存安全，因为无符号乘法最常在分配数组时出现。在 C 中，人们倾向于写： ```c malloc(sizeof(Object) * n) ``` 如果这样的表达式发生溢出，那么 `malloc` 将分配并返回一个指针，指向的内存实际上不足以容纳所有 `n` 个 `Object`。再次强调，有符号在这里也救不了我们，实际上它会通过过度分配大约 4 GiB 的内存来静默地避免内存安全问题（如果你使用 `int`，因为负值强制转换为 `size_t` 会变得那么大）。随机资源耗尽也不是一个更好的情况。有几种更好的写法。第一个明显的是使用 `calloc`。但这有清零的成本，并且在需要 `realloc` 时没有帮助。像 C++ 和 Go 这样的语言注意到了这个问题，并以更清晰的方式解决，消除了危险乘法的需要。 - C++ ```cpp std::vector<Object> vec(n); ``` - Go ```go make([]Object, n); ``` 但那些并不普遍适用。检查 `x * y` 是否会溢出其实非常容易，你应该学会这个极其简单和明显的测试。 ```c if (x > (T)-1 / y) { // 错误 } ``` > 这里的 `(T)-1` 是你的无符号类型，将 `-1` 强制转换只是给出了最大值，即每一位都置位。你也可以使用 `~((T)0)`、`UINT{8,16,32,64}?_MAX` 或 C++ 中的 `numeric_limits::max()`，有很多方法计算这个值。 ### 哨兵值{#sentinel-values} 有符号整数的一个极其常见的用途是使用负数范围来编码错误代码或某种哨兵值 (https://en.wikipedia.org/wiki/Sentinel_value)。这是一种糟糕的编程实践，实际上是一种类别错误。在处理现有或基于此设计的遗留代码时，它几乎无法避免，但这并不是有符号整数继续这种实践的强有力论据。你也可以用无符号来拥有哨兵值，尽管你不应该这样做。我们不应鼓励这种做法，并将其作为支持有符号的论据。 ```c int result = connect(); if (result >= 0) // ... ``` > 这是早期 C 的典型做法。 有几种更好更安全的方法来表达，例如： - 使用输出参数返回结果。虽然看起来不太整洁。 ```c if (uint result; connect(&result)) { // ... } ``` - 返回元组或对。看起来稍微好一些。 ```c tuple<bool, uint> result = connect(); if (get<0>(result)) { // ... } ``` - 我们可以使用选项类型。这在 Rust 中很常见。 ```rust // connect 返回 Option match connect() { Some(u32) => // ... None => // 错误 } ``` - 然而，如果数值范围一开始就定义明确，只需定义整个域，并避免用全范围整数来表示所有可能值的一个子集。 ```cpp enum class ConnectionStatus : unsigned { Connected, NoRouteToHost, Disconnected, TimedOut, }; ConnectionStatus status = connect(); if (status == ConnectionStatus::Connected) { // ... } ``` - 一些语言如 Odin 和 Go 支持多重返回，惯用方式如下： ```go status, err := connect() if err != nil { // ... } ``` 这些都是更优越的方法，消除了将有符号整数负数部分编码错误状态的需要，并且几乎在任何语言中都可以表示。 ### 它是默认值{#its-the-default} 这是一个薄弱的论点，但至少是唯一一个难以反驳的。C 和 C++ 默认将 `int` 设为有符号，这是一个历史遗留选择，并在许多源自 C 的语言中持续存在。现在普遍认为 C 中的许多默认值是不好的，也许我们也应该考虑这一点？ ## 如果定义有符号为回绕会怎样？{#what-if-signed-was-defined-to-wrap} 一些语言如 Go 和 Odin (https://odin-lang.org/) 声称避免了这些问题，因为有符号整数算术被定义为在下溢和溢出时回绕。那里的安全性论点也是不正确的。在前面所有的例子中，如果有符号整数回绕，它们几乎总是产生负值，这要么引入静默的逻辑错误，要么更糟，当用作数组索引时导致内存安全问题。 > 唯一能安全地以这种方式使用有符号整数的方法是进行所有数组访问的边界检查，这会有显著且不可忽视的运行时成本。边界检查如果不自动化也很容易出错，因为很容易忘记检查，并且在代码重构时往往不维护。 不幸的是，对于基于 LLVM 的语言，无论你多么努力地挥手并希望有符号回绕被定义，都不会起作用，因此关于安全性的这种说法在事实上是不正确的。以下是一个不完全列表，列出了 LLVM 中有符号整数算术的所有未定义行为，适用于所有使用 LLVM 的语言： - `x / 0` - `INT_MIN / -1` - `INT_MAX % -1` - `INT_MAX - INT_MIN` > 这些在 Go、Rust 和 Odin 等语言中肯定会产生无效结果。 ## 那么陷阱机制呢？{#what-about-trapping} 一些语言如 Rust 采取了不同的方法，在 Debug 构建中任何整数下溢或溢出都会导致陷阱表示，程序会 panic。C 和 C++ 也有清理工具来帮助检测这些问题，并且由于 C 和 C++ 将无符号下溢定义为回绕，实际上使用有符号整数更好，因为这是唯一能获得整数陷阱行为的方式，因为对无符号使用陷阱机制会触发依赖该行为的有效代码的陷阱表示。陷阱机制实际上相当不足，因为它们只能在运行时成功执行路径并带有正确的产生陷阱的输入时触发。即使进行详尽的单元测试，在任何非平凡的程序中也不可能预期这种覆盖。这个想法在许多上下文中也是不兼容的，例如 libra...（原文似乎未完成，但保留原样）