Negative value representation

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

s1 | s2 | x1 + x2 overflow | addition result | —— | —— | — | — | 0 | 0 | No | x1 + x2 = v1 + v2 | 0 | 0 | Yes | too large to be represented with data type (overflow) | 0 | 1 | No | x1 + x2 - 2n-1 = x1 + x2 - s2 * 2n-1 = v1 + v2 | 0 | 1 | Yes | (x1 + x2) mod 2n-1 = x1 + x2 - 2n-1 = v1 + v2 | 1 | 0 | * | see above (swap summands) | 1 | 1 | No | too small to be represented with data type (x1 + x2 - 2n < -2n-1 ; underflow) | 1 | 1 | Yes | (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

Original | Process | Result | —— | —— | —— | 0 (00000000) | Negate | -0 (11111111) 11111111 | Add 1 to binary | 100000000 100000000 | Truncate to 8 bits | 00000000 (-0 equals 0)