Common representation of negative integers.
In modern computers, almost all numeric values are processed and represented internally in some base-2 form. Starting with that, a reasonable next question might be: “How are negative values represented?” There’s more than one way to do that—“Positional notation: Non-integral values” mentioned that the float and double types use a sign bit—but for integers, two’s complement is used far more often by CPUs (including the JVM) and compilers (including javac) than any other.
In two’s complement, the representation of the negative value of an integer n is found by flipping all of the bits in n, and adding 1. In other words, the value of the following boolean expression is (with one exception) true:
-n == ~n + 1
For a concrete example, let’s look at 42, which we can write in Java as the base-2 literal 0b00101010. If we flip all the bits, we get 0b11010101. If we add 1 to that value, we end up with 0b11010110, which must be (according to the above) the two’s-complement representation of -42.
Another way of describing two’s complement is that it treats the left-most bit as the negative of its unsigned value. To illustrate, remember that a byte has 8 bits, and let’s revisit positional notation for base-2, but with a change in the sign of the left-most column. Again, let’s use 42:
| -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
That is, 42 = 32 + 8 + 2.
Note that the value of left-most column is -128, not 128.
Now, flip the bits in the above:
| -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Next, add 1, carrying as necessary:
| -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
We now have -128 + 64 + 16 + 4 + 2, which adds up to -42.
This approach works equally well (with the exception mentioned above, and explained below) for taking the negative of a value that’s already negative. For a simple example of this, start with -1, which we can express (in the case of a byte) as the Java literal 0b11111111 (-128 + 64 + 32 + 16 + 8 + 4 + 2 + 1). Flip the bits, and we have 0b00000000. Add 1, and we have 0b00000001, which is (of course) 1, or -(-1).
Another advantage of this representation is that the basic arithmetic operations work the same for positive and negative values: little (if any) adjustment is needed in the underlying CPU instructions, even if we switch between signed and unsigned types.
This representation works for wider integer types, as well: In a type composed of $N$ bits, the leftmost bit represents $-(2^{N - 1})$, while all the other bits count as normal. Consider the short (16-bit signed) value expressible as 0b00000101_01010101:
Now, flip the bits to get 0b11111010_10101010:
Finally, add 1, and we get -1365.
(Note that just as we can use underscores as digit separators in Java literals expressed in base-10, we can do the same with binary, octal, and hexadecimal literals.)
With the 8 bits of a Java byte, we can count from 0 (0b00000000) to 127 (0b01111111) in the usual fashion; if we add 1 more, we get 0b10000000, or -128. Continuing to add 1 repeatedly, we get the values from 0b10000001, or -127, up to 0b11111111, or -1. Add 1 more to that, and throw away the overflow bit (produced when our addition carries over to a 9th bit, which doesn’t fit into an 8-bit byte), and we’re back to 0b00000000, or 0.
One interesting implication of all of the above is that a two’s-complement representation always allows for a negative value that is 1 larger in absolute value than the largest positive value. For example, the values allowed by the byte type range from -128 to 127; for the short type, the range is -32,768 to 32,767; and so on. Because of this, something curious happens when we compute (for example) the negative of a byte that has the value -128. As we saw above, byte only allows a maximum value of 127, so where does that leave -(-128)?
Let’s try it in JShell:
byte b = -128;
b *= -1;
In the second line, the value of b is multiplied by -1, and the result is assigned back to b. But what was the value assigned? If you didn’t notice the value displayed after the assignment, simply type b on a new line and then [Enter].
Note that we could written the first line above as
byte b = Byte.MIN_VALUE;
Let’s try it with the int type: Using JShell, write the following, to see what happens when we multiply Integer.MIN_VALUE by -1:
-Integer.MIN_VALUE
Do you notice anything strange? It sure looks like the result of negating the Integer.MIN_VALUE is the same value!
Let’s check our suspicion about this, by evaluating this expression:
-Integer.MIN_VALUE == Integer.MIN_VALUE
Of course, we expect an expression like -0 == 0 to evaluate to true, but for a non-zero value to be equal to its negation can be a bit puzzling.
All finite numeric representation schemes have weaknesses. This simple JShell experiment demonstrates one such weakness in two’s complement: The result of negating the minimum value in the representable range is the same minimum value.