language-agnostic - 添加 MIN_VALUE 如何将整数比较为无符号？

Question

在 Java 中 int 类型是有符号的，但它有 a method比较两个整数，就好像它们是无符号的一样:

public static int compareUnsigned(int x, int y) {
    return compare(x + MIN_VALUE, y + MIN_VALUE);
}

它添加 Integer.MIN_VALUE到每个参数，然后调用正常的有符号比较方法，即:

public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

如何添加 MIN_VALUE对每个参数神奇地使比较无符号？

Answer 1

这种技术适用于任何大小的整数，但我将使用一个 8 位字节大小的整数来解释，因为这些数字更小且更易于使用。

8 位类型有 28 = 256 个可能的值。在低级别，这些只是位，有符号与无符号是我们如何解释这些位的问题。当解释为无符号整数时，它们的范围为 0 到 255。当解释为有符号整数时 two's complement整数，它们的范围是 -128 到 +127。

类型的数轴如下所示:



请注意，从 0 到 127 的正数可以用有符号和无符号类型表示，并且它们由完全相同的位模式(00000000 到 01111111)表示。

在无符号解释中代表从 128 到 255 的大正数的位模式被重用于有符号解释中的数字 -128 到 -1。就好像有人拿了无符号数行，砍掉了范围的上半部分，然后把它粘在了行的下端。

现在，让我们看看当我们比较一对整数时会发生什么。

情况 1:两个值都在有符号的正范围内

两个值都在 0 到 127 的范围内，无论这些位被解释为有符号还是无符号，它们都具有相同的数值。

我们无条件地将 MIN_VALUE 添加到每个值。我们的有符号字节类型的 MIN_VALUE 是 -128，因此添加意味着我们实际上减去了 128。

一个例子:我们的比较函数，使用有符号类型，给定 x = 20 和 y = 60。加上 MIN_VALUE，我们得到 x' = 20 − 128 = −108 和 y' = 60 − 128 = −68:



将 MIN_VALUE 添加到正值将始终将其映射到负值。在范围的最末端，0 将变为 -128，而 127 将变为 -1。该操作不会改变x和y相对于彼此的顺序，因此x'和y'之间的任何比较的结果都将与我们没有添加MIN_VALUE一样，这是正确的。

情况 2:两个值都在有符号负数范围内

在这种情况下，如果解释为有符号，两个值都在 -128 到 -1 的范围内。如果解释为无符号，它们的范围是 128 到 255(大于 256)。

当我们无条件地将 MIN_VALUE 添加到我们的每个有符号负值时，它 总是 导致溢出和环绕，以带符号的正值。从数字上讲，这种环绕与加 256 相同。如果我们给定 x = −35 和 y = −80 进行比较，我们得到 x' = −35 − 128 + 256 = 93 和 y' = −80 − 128 + 256 = 48:



我们也可以用 -35 和 -80 的无符号解释来形象化，它们是 221 和 176。当减去 128 时，我们得到 x' 和 y' 完全相同的结果。二进制补码的优点之一是，无论您将数据视为有符号还是无符号，加法和减法都会产生相同的结果，因此 CPU 可以使用相同的电路。

与情况 1 一样，该操作不会更改两个数字之间的任何比较结果。我们的 x 大于 y(负值较小)，并且 x' 也大于 y'。因此，这些输入之间的比较将是正确的。

情况 3:一个值在有符号的正数范围内，另一个是负数

这是一个有趣的案例。请注意，当我们添加 MIN_VALUE 时，它总是会更改数字的符号。正值映射到负值，负值映射到正值。

让我们比较 x = -35 和 y = 60。由于我们希望将它们作为无符号进行比较，因此我们确实希望将 x 解释为 -35 + 256 = 221。因此，x 需要被解释为大于 y，即使我们的签名数据类型通常不会这样做。

因为数字具有相反的符号，改变符号的 MIN_VALUE 操作将颠倒数轴上数字的顺序。 x' = −35 − 128 + 256 = 93 , y' = 60 − 128 = −68 .所以我们得到 x' 大于 y'，这是我们想要的:



概括

由于我们已经处理了正负的所有组合，我们知道该技术适用于所有可能的值。

在 32 位整数的情况下，范围更大(有符号范围是 -2,147,483,648 (MIN_VALUE) 到 +2,147,483,647，无符号范围是 0 到 4,294,967,295)但它的工作原理是一样的。事实上，它适用于各种大小的整数，并且适用于每种编程语言，前提是:

有符号整数使用二进制补码表示(这几乎是通用的)。

加法环绕溢出(而不是引发错误或提升为更大的数字类型或未定义)。

你也可以做相反的事情:如果你只有一个无符号整数类型，并且你想要做一个二进制补码有符号比较，将有符号最小值添加(无符号解释)到每个数字。

由于该技术只是两个无条件加法运算，因此即使没有经过编译器或 VM 的特殊处理，它也非常有效。