Java Language Negative value representation


Example

Java and most other languages store negative integral numbers in a representation called 2's complement notation.

For a unique binary representation of a data type using n bits, values are encoded like this:

The least significant n-1 bits store a positive integral number x in integral representation. Most significant value stores a bit vith value s. The value repesented by those bits is

x - s * 2n-1

i.e. if the most significant bit is 1, then a value that is just by 1 larger than the number you could represent with the other bits (2n-2 + 2n-3 + ... + 21 + 20 = 2n-1 - 1) is subtracted allowing a unique binary representation for each value from - 2n-1 (s = 1; x = 0) to 2n-1 - 1 (s = 0; x = 2n-1 - 1).

This also has the nice side effect, that you can add the binary representations as if they were positive binary numbers:

v1 = x1 - s1 * 2n-1
v2 = x2 - s2 * 2n-1
s1s2x1 + x2 overflowaddition result
00Nox1 + x2 = v1 + v2
00Yestoo large to be represented with data type (overflow)
01No
x1 + x2 - 2n-1 = x1 + x2 - s2 * 2n-1
= v1 + v2
01Yes
(x1 + x2) mod 2n-1 = x1 + x2 - 2n-1
= v1 + v2
10*see above (swap summands)
11Notoo small to be represented with data type (x1 + x2 - 2n < -2n-1 ; underflow)
11Yes
(x1 + x2) mod 2n-1 - 2n-1 = (x1 + x2 - 2n-1) - 2n-1
= (x1 - s1 * 2n-1) + (x2 - s2 * 2n-1)
= v1 + v2

Note that this fact makes finding binary representation of the additive inverse (i.e. the negative value) easy:

Observe that adding the bitwise complement to the number results in all bits being 1. Now add 1 to make value overflow and you get the neutral element 0 (all bits 0).

So the negative value of a number i can be calculated using (ignoring possible promotion to int here)

(~i) + 1

Example: taking the negative value of 0 (byte):

The result of negating 0, is 11111111. Adding 1 gives a value of 100000000 (9 bits). Because a byte can only store 8 bits, the leftmost value is truncated, and the result is 00000000

OriginalProcessResult
0 (00000000)Negate-0 (11111111)
11111111Add 1 to binary100000000
100000000Truncate to 8 bits00000000 (-0 equals 0)