Flip and add 1: Two’s Complement and why
In computer language and logic, one of the most basic concepts is the representation of information through binary language of zeroes and ones. Everything can be interpreted in a different binary combination — be it characters, data, numbers.
Because the only participants in the binary language are 0’s, 1’s and amount of bits to represent each piece of information, there are a certain limitations or adjustments to be made in order to properly store all the correct information in memory without misinterpretation or loss of data.
In binary, which is a base-2 numeral system, every digit is referred to as a bit because of its straightforward implementation in computer language. Any number can be represented by a sequence of bits, which in turn can be represented by any mechanism or language or system capable of being in two mututally exclusive states — on and off, yes and no, black and white, dash and dot, 1 and 0…
In order to count in binary, the overflow when reaching 1 produces a flip of that number from one to zero, and an increment towards the left of that overflowing 1.
Check out the following counter that shows how to count in binary from numbers zero through thrity-one in a graphic way:
From Wikipedia, the free encyclopedia Click on a date/time to view the file as it appeared at that time. Date/Time…
Therefore taking into consideration the basic building of decimal numbers in binary, a representation of decimal numbers 0 through 7 in binary would look like this:
Where the blue numbers are bits that correspond to either 1, 2, 4, or 8 (from right to left). The starting point is 0000 and to convert from decimal to binary, we just have to set (switch from 0 to 1) the right bits that add up to the decimal value being converted.
Here are a few representations of the previous explanations:
8 4 2 1
0 0 0 0 = 0
8 4 2 1
0 0 1 1 = 0 + 0 + 2 + 1 = 3
8 4 2 1
0 1 1 1 = 0 + 4 + 2 + 1 = 7
For negative numbers, the first bit (most left handside bit) of every binary representation is flipped(turned to 1). For example, 1 decimal is 0001 in binary, so -1 decimal would be 1001 in binary.
This looks simple and easy to understand but unfortunately it creates a very big no-no which is the creation of a zero (0) and a minus zero (-0) as two different numbers, which will eventually make arithmetics explode — a.k.a: give wrong results.
Let’s make a simple addition in this way (even though we already know the answer will be wrong):
Decimal 5 equals 0101 binary so, following this theory, -5 would equal 1101.
Following binary addition rules:
If we add 0101 and 1101 we get: 0010 which equals to 2 and quite clearly, the wrong answer to this operation.
One way to try and avoid this problem is using the One’s Complement operation: Flipping all the bits in a binary sequence (turning 1’s to 0’s and 0s to 1s). So, for example if we take decimal 4, it’s binary value would be 0100 and -4 would be 1011. The addition of these two binaries is 1111. Applying the flip logic of the One’s Complement, 1111 is the opposite of 0000, which is decimal 0, so 1111 would be -0 — again resulting in a zero and minus zero which we want to avoid.
… and add 1!
There is a way to ignore the two zeroes and avoid confusion regarding the representations of zero and minus zero — Two’s Complement.
It works very similar to the One’s Complement by flipping bits, but it adds 0001 to the binary representation of the negative number after flipping the values. This shifts the range to get rid of the double value of zero.
In Two’s Complement, the carries in the left handside are ignored and “thrown away”.
For example for decimal 3, which in binary is 0011. If we flip the values to get the negative value, the binary representation would be 1100. Like we saw before, if we add these, the result would be 1111 resulting in the negative zero. If we add 0001 to the flipped value, the result is 1101.
And if we add 0011(3) + 1101(-3) the result is … 0000 ! Ta-da!
We avoided the double zero’s and could efficiently represent and store negative values in binary through the Two’s Complement operation.
In the following table we can see the binary representation of decimals -8 to 7:
We can see that all the negative values begin with 1, all the positive begin with 0. This first value is known in the One’s and Two’s notations as the Most Significan Bit, or MSB for short. The MSB corresponds to the sign bit of a signed binary number. In One’s and Two’s complement notation, 1 signifies a negative number and 0 signifies a positive number.
It is also noted that the double zero disappeared, This makes it so that the negative numbers’ absolute values are always 1 more than their positive equivalents. This explains what is mentioned in the image, and why in C, integers range from the INT_MIN -2,147,483,648 to INT_MAX 2,147,483,647, or in case of the example above, from -8 to 7 instead of -8 to 8.
— — — — —
Being able to correctly transform everything to computer language is essential and a huge must, especially when intepreting data and inputing this data for the computer to comprehend and use. Even though most processes can be automated and we don’t necessarily have to know how to intepret and convert it all, a proper understanding of some of these processes is crucial and important to further expand the thinking abbilities of us as computer userts.
A correct and generic representation of the information is crucial, and this post tried to explain a tiny fraction of this almost infinite world — hope you enjoed it !