Java Language Primitive Data Types 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
| 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 |
| 0 | 1 | Yes | (x1 + x2) mod 2n-1 = x1 + x2 - 2n-1 |
| 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 |
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) |
