如何添加MIN_VALUE将整数比较为无符号? [英] How does adding MIN_VALUE compare integers as unsigned?

问题描述

在Java中，int类型是带符号的，但是具有

In Java the int type is signed, but it has a method that compares two ints as if they were unsigned:

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

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

It adds Integer.MIN_VALUE to each argument, then calls the normal signed comparison method, which is:

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

如何在每个参数中添加MIN_VALUE神奇地使比较无符号?

How does adding MIN_VALUE to each argument magically make the comparison unsigned?

推荐答案

此技术适用于任何大小的整数，但我将使用8位字节大小的整数进行解释，因为数字更小且更容易理解与之共事.

This technique works for any size of integer, but I'll use an 8-bit byte-sized integer to explain, because the numbers are smaller and easier to work with.

8位类型具有2 ⁸ = 256个可能的值.在较低的级别上，这些只是位，有符号与无符号的关系取决于我们如何解释这些位.当解释为无符号整数时，它们的范围为0到255.当解释为有符号二的补数整数，范围为-128至+127.

An 8-bit type has 2⁸ = 256 possible values. At a low level these are just bits, and signed vs unsigned is a matter of how we interpret those bits. When interpreted as an unsigned integer, they have a range of 0 to 255. When interpreted as a signed two's complement integer, they have a range of −128 to +127.

类型的数字行看起来像这样:

The number line for the types looks like this:

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

Notice that the positive numbers from 0 to 127 can be represented by both signed and unsigned types, and they are represented by exactly the same bit patterns (00000000 to 01111111).

表示无符号解释中从128到255的较大正数的位模式将重新用于有符号解释中的-128至-1.好像有人拿了无符号数字行，将其切掉范围的上半部分，然后将其粘贴在该行的下端.

The bit patterns which represent the large positive numbers from 128 to 255 in the unsigned interpretation are reused for the numbers −128 to −1 in the signed interpretation. It is as if someone took the unsigned number line, chopped off the upper half of the range, and glued it on at the lower end of the line.

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

Now, let's look at what happens when we compare a pair of integers.

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

With both values in the range 0 to 127, they have the same numeric value whether the bits are interpreted as signed or unsigned.

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

We unconditionally add MIN_VALUE to each value. MIN_VALUE for our signed byte type is −128, so adding that means we are actually subtracting 128.

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

An example: our comparison function, using signed types, is given x = 20 and y = 60. Adding MIN_VALUE, we get x' = 20 − 128 = −108 and y' = 60 − 128 = −68:

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

Adding MIN_VALUE to a positive value will always map it to a negative value. At the extreme ends of the range, 0 would become −128, and 127 would become −1. The operation will not change the order of x and y relative to each other, so the result of any comparison between x' and y' will be the same as if we had not added MIN_VALUE, which is correct.

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

In this case, both values are in the range −128 to −1 if interpreted as signed. If interpreted as unsigned they are in the range 128 to 255 (which is 256 greater).

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

When we unconditionally add MIN_VALUE to each of our signed negative values, it always causes overflow and wrap-around, to signed positive values. Numerically, this wrap-around is the same as adding 256. If we are given x = −35 and y = −80 to compare, we get x' = −35 − 128 + 256 = 93 and y' = −80 − 128 + 256 = 48:

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

We can also visualize this with the unsigned interpretations of −35 and −80, which are 221 and 176. When subtracting 128, we get exactly the same results for x' and y'. One of the advantages of two's complement is that addition and subtraction give the same results regardless of whether you treat the data as signed or unsigned, so CPUs can use the same circuitry.

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

As in case 1, the operation does not change the results of any comparisons between the two numbers. Our x was greater than y (being of lesser negative magnitude), and x' is also greater than y'. So comparisons between these inputs will be correct.

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

This is the interesting case. Notice that when we add MIN_VALUE, it always changes a number's sign. Positive values are mapped to negative values and negative values are mapped to positive values.

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

Let's compare x = −35 and y = 60. Since we want these to be compared as unsigned, we really intend x to be interpreted as −35 + 256 = 221. So x needs to be interpreted as greater than y, even though our signed data type will not normally do this.

由于数字的符号相反，因此更改符号的MIN_VALUE操作将颠倒数字在数字行上的顺序. x' = −35 − 128 + 256 = 93 ，而 y' = 60 − 128 = −68 .因此我们得到 x'大于 y'，这就是我们想要的:

Because the numbers have opposite signs, the MIN_VALUE operation which changes the signs will reverse the numbers' order on the number line. x' = −35 − 128 + 256 = 93, and y' = 60 − 128 = −68. So we get x' is greater than y', which is what we wanted:

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

Since we've handled all combinations of positive and negative, we know the technique works for all possible values.

对于32位整数，范围更大(有符号范围为−2,147,483,648(MIN_VALUE)至+2,147,483,647，无符号范围为0至4,294,967,295)，但它的作用相同.实际上，只要满足以下条件，它就适用于每种整数大小以及每种编程语言:

In the case of 32-bit ints, the ranges are bigger (signed range is −2,147,483,648 (MIN_VALUE) to +2,147,483,647, and unsigned range is 0 to 4,294,967,295) but it works just the same. In fact it works for every size of integer, and in every programming language, provided that:

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

1. The signed integers use two's complement representation (which is nearly universal).

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

Addition wraps around on overflow (rather than raising an error or promoting to a bigger number type or being undefined).

您也可以执行相反的操作:如果您只有一个无符号整数类型，并且要进行二进制补码有符号比较，则将有符号最小值加(无符号解释)给每个数字.

You can also do the reverse: if you have only an unsigned integer type, and you want to do a two's complement signed comparison, add (the unsigned interpretation of) the signed minimum value to each number.

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

Because the technique is just two unconditional addition operations, it is extremely efficient even if not treated specially by a compiler or VM.

这篇关于如何添加MIN_VALUE将整数比较为无符号?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！