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

Question

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

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位类型具有2 ⁸ = 256个可能的值.在低级别,这些只是位,而无符号和无符号是我们如何解释这些位的问题.当解释为无符号整数时,它们的范围为0到255.当解释为带符号的二进制补码整数时,它们的范围为-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:两个值都在有符号的负范围内

在这种情况下,如果解释为signed,则两个值都在-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)但它的工作方式相同.事实上,它适用于每个大小的整数,并且在每种编程语言中,只要:

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

2. 加法包含溢出(而不是引发错误或提升为更大的数字类型或未定义).

您也可以反过来:如果您只有一个无符号整数类型,并且您想要进行二进制补码签名比较,请将已签名最小值(无符号解释)添加到每个数字.

因为该技术只是两个无条件的加法运算,所以即使不经过编译器或VM专门处理,它也非常有效.