Sign Bit, One's Complement, Two's Complement#
1: Why do we have sign bit, one's complement, and two's complement?#
In order to simplify numerical calculations in computers, we use two's complement.
The specific implementation will be discussed later, but first let's take a look at what sign bit, one's complement, and two's complement are.
2: Sign bit, one's complement, and two's complement for positive numbers#
Most online sources introduce sign bit, one's complement, and two's complement separately. However, I (the author) feel that this method is not convenient for understanding. So, I will use positive and negative numbers instead.
Let's represent numbers using 8 bits, as there are too many zeros if we use int, which is not convenient to read.
Positive numbers are simply the conversion of decimal numbers to binary.
The sign bit, one's complement, and two's complement for positive numbers are the same.
[+1] = [00000001] (sign bit) = [00000001] (one's complement) = [00000001] (two's complement)
3: Sign bit, one's complement, and two's complement for negative numbers#
Sign bit: The highest bit is 1, indicating that the number is negative.
One's complement: The sign bit remains the same, and the other bits are inverted.
Two's complement: One's complement + 1.
[-1] = [10000001] (sign bit) = [11111110] (one's complement) = [11111111] (two's complement)
4: The significance of sign bit, one's complement, and two's complement#
They all exist to make calculations in computers simpler and improve performance.
Knowledge: 1 - 1 = 1 + (-1), so machines only need addition.
If we only use sign bit for calculations, humans can easily calculate the values because they can distinguish the sign bit.
However, it is difficult for computers to recognize the sign bit. Is there a way to make calculations simpler for computers? That's where one's complement comes in.
Let's take a look at the calculation with one's complement.
1 - 1 = 1 + (-1)
= [0000 0001] (original) + [1000 0001] (original)
= [0000 0001] (one's complement) + [1111 1110] (one's complement)
= [1111 1111] (one's complement)
= [1000 0000] (original)
= -0
One's complement already simplifies calculations for computers. But why do we still have two's complement?
Because in one's complement, the encoding of 0 can be [1111 1111] (one's complement) = [-0] and [0000 0000] (one's complement) = [+0].
Positive and negative 0 have no meaning, so two's complement is used to solve the problem of 0 having two encodings.
(Actually, in one's complement, it is not directly apparent which number it represents, so understanding is required. Two's complement is even more difficult to understand as it involves adding 1 to one's complement. I also tried to express it in a simpler way, and if you have any questions, please write them in the comments.)
In two's complement, it is defined that the encoding of 0 is [0000 0000] (two's complement) = [+0].
Here, let's not think about the binary representation of decimal numbers, but imagine them as "encodings".
First, with 8 bits of binary, there are only so many encodings from 0000 0000 to 1111 1111 (starting from 0000 0000 and adding 1).
Then, for positive numbers, the sign bit, one's complement, and two's complement are all the same. So let's remove 0000 0000 to 0111 1111.
What remains is 1000 0000 to 1111 1111, which are negative numbers (because the sign bit is 1).
Adding 1 to these encodings is as follows:
1000 0000
1000 0001
1000 0010
....
1111 1101
1111 1110
1111 1111
First, if these encodings are in the original form, the corresponding decimal numbers are:
-0
-1
-2
....
-125
-126
-127
Since one's complement makes calculations easier for computers, these encodings are the one's complement and the corresponding decimal numbers are:
-127
-126
-125
...
-2
-1
-0
But there is -0. How do we solve this -0? By subtracting 1 from each number, there will be no -0 anymore, and it becomes:
-128
-127
-126
...
-3
-2
-1
This perfectly solves the encoding problem of -0 and adds an additional -128. This is why the range of int in Java is $-2^{31}$ to $2^{31}-1$.
Now let's discuss how to transform one's complement into these numbers. The one's complement of -1 is 1111 1110, and now the encoding of -1 becomes 1111 1111 (this is the two's complement of -1).
In conclusion, two's complement = one's complement + 1.
That's how two's complement is derived. Using two's complement allows computers to perform calculations faster (one's complement can also be used, but there is still the problem of -0, so two's complement is used).