"No exceptional circumstances whatsoever, whether a state of war or a threat of war, internal political instability, or any other public emergency, may be invoked as a justification of torture." -- U.N. Convention Against Torture
In order to fully comprehend the importance of Twos Complement for computer science, one must first have a basic understanding of binary numbers. Binary numbers are important in computers because everything in your computer is ultimately stored in a digital format using binary.
Understanding binary is not a difficult task, as long as one first understands the basics behind any numbering system. Every system of numbering since the ancient times has used a numeric base as its foundation. This base, called a radix, is the fundamental point of origin for using the number system. Most everyone today uses the modern base ten number system(which has 10 as its radix). Numbers are then assigned a value based on the digits present. For instance, consider the decimal(base 10) number 34. This is redundantly represented as
3 x 10^1 + 4 x 10^0 = 34(10)
NOTE:Radices are often written as a subscript to denote in which base the number is.
NOTE:In this article, radices are denoted in parenthesis.
This concept also applies to other radices than our modern base-10 system; it applies to any number system. Since binary is the term for the number system with radix two, we could represent any number in binary with the aforementioned concept. However, it is important to remember that the number of digits a numbers system has is equal to its radix. For example, the common base ten number system has ten digits, 0,1,2,3,4,5,6,7,8 and 9. For binary, there are only two digits present: 0 and 1. With that in mind, we will change the value 34(10) into binary. Recall that 34 can be represented as
3 x 10^1 + 4 x 10^0 = 34(10)
This means that we will need to put the value 34 in terms of 2s:
1 x 2^5 + 0 x 2^4 + 0 x 2^3 + 0 x 2^2 + 1 x 2^1 + 0 x 2^0
Thus, 34(10) = 100010(2). Keep in mind that the actual value of the number is preserved and it is only the way we represent the number that changes.
Computers and Binary
At this point, the reader may be wondering why we chose to put such emphasis on radix two numbers. After all, we could theoretically choose any positive integer to be our radix and still represent numbers. The reason we are focused on binary is because it is in binary that a computer works. Almost every piece of data can ultimately be traced down to a series of 1s and 0s. Of course, to show how various types of data are represented in binary is beyond the scope of this paper, but there is one type of data in which we will delve further into the underlying principles to better understand how it is used in modern computing. This data type is the integer. Fundamentally, integers are stored in computers in a byte, that is, eight binary digits. Recall from the previous section that the binary representation of 34(10) was 100010(2). A computer could store this value as 00100010. Note that this is the same value, merely with the leading zeros showing to denote that the computer analyzes all 8 bits(a binary digit) as a whole. With all eight of these bits being used, this means that the computer could represent any integer from 0(00000000) to 255(11111111). However, this leads to an inherent lack of negative numbers. Thus, there are several methods which have been developed in order to represent these negative numbers using a byte.
Signed Magnitude(also known as Sign and Magnitude) is a way of representing negative numbers in binary based on the way we express negative natural numbers. The philosophy behind Signed Magnitude is that by using one of the bits(the one that represents 2^7 in almost all cases) to designate the sign of the number, while the other 7 represent the magnitude of the number.
Ones Complement is a method of representing negative numbers that uses the bitwise NOT operator. It operates on the idea that by flipping all the bits of a positive integer, a negative integer can be achieved with the opposite bits(as far away as possible from the original). This creates a symmetrical list of values that can represent numbers from -127 to +127.
Twos Complement is a method of representing negative numbers that is based off ones complement, but with the main advantage of not having to deal with a positive and negative zero. This allows for a greater range as well, with the range being from -128 to 127.
Negabinary, although not a commonly seen method in computing, is a method that uses mathematics to define a number system that uses a radix of -2 to represent negative numbers. This means that each bit then inherits the following values:
This leads for the maximum negative value to be -128+-32+-8+-2 = -170 and the maximum positive number to be 64+16+4+1 = 85. This asymmetrical balance can be shifted towards the positive end with the use of a bias.
The storage of a Signed Magnitude value is based on the leading bit, which is the sign bit. If this bit is set, it denotes that the value is negative. If this bit is reset, it denotes that the value is positive. In addition to the leading bit, the other seven bits are used to store the magnitude of the value. These seven bits have the same value as an unsigned byte with a leading zero.
To negate a signed magnitude, the sign bit merely needs to be switched.
The addition of two Signed Magnitude numbers is highly dependent on the sign bits of both operands. The first method of determining how to add the two numbers is to perform an exclusive or on the sign bits. If this returns a zero both signs are the same, and so the normal addition for unsigned bytes can be performed on the seven magnitude bits(a half-adder using an AND and XOR gate), then the sign bit of either operand can be set to the sign bit of the result. This finalizes the result. However, if the initial XOR check returns a zero, the two magnitudes must be compared to see which operand has a larger magnitude. Both operands are passed into an argument specific adder in which the first operand, which has the larger magnitude, is added with the byte that has the other magnitude, and the sign bit from the first operand is used in the result.
The major disadvantage behind the signed magnitude representation of negative numbers is that performing addition or subtraction on the number requires several conditional jumps, resulting in rather long code for performing almost any basic operation on the number. Of course, on the positive size, converting to a signed magnitude from an unsigned byte is a breeze; it simply entails setting the sign bit to the desired sign. Another small con of using the signed magnitude representation of a negative byte is that it results in two values for zero, which slightly reduces the range which the byte can cover(both 00000000 and 10000000 are +0 and -0, respectively). This can be viewed as an advantage, depending on context. For example, limits can approach +0 and -0 with a need for distinction between the two.
storage of a Ones Complement number is a bit odd, because although one may still determine the sign of the value from the sign bit as with signed magnitudes, the magnitude of a negative number is actually the unsigned value of the seven bits subtracted from 127. However, the magnitude of a positive number stays as it is in a signed magnitude. This guarantees a symmetrical table of values in which positive and negative zero occupy the extremes.
To negate a ones complement byte, one may simply use the bitwise NOT on the byte, which will effectively represent the positive values with a zero in the sign bit and the magnitude in the other seven bits and the negative values with a one in the sign bit and the magnitude subtracted from 127 in the other seven bits.
Addition of a ones complement is much simpler than that of a signed magnitude because rather than being dependent on the signs of the operands, it is an unconditional operation. The addition of two ones complement numbers can be achieved by passing them through a normal half-adder and then adding the carry flag to them.
The major disadvantage that a ones complement value holds over a signed magnitude is that it does not require any conditional jumps in the addition algorithm. This effectively reduces the time of the addition, as well as frees memory used by the extra code. It also makes any debugging necessary much easier for the programmer. It still has the minor disadvantage of having a positive and negative zero, which reduces the range of the byte.
The storage of a Twos Complement value is almost the exact same as a ones complement value, except for the fact that the negative numbers magnitude is the unsigned magnitude subtracted from 128. This shifts the range from the -127 to 127 of the other aforementioned representations to -128 to 127 by eliminating the negative zero value. Thus, the table of values for twos complement is asymmetrical, centering around 127 and -128, with 0 and -1 at the extremes.
To negate a twos complement value, simply bitwise NOT the value and increment it. Another method developed for negating a twos complement value is to find the right-most(least value) one in the byte and then flip all the bits to the left of that one. If there is not a right-most one, nothing happens to the value because it is zero, which is neither positive nor negative(mathematically speaking). However, almost all computers use the former algorithm, as it only involves two instructions, as opposed to a loop of shifts that the latter might involve, or the dynamic creation of a bitmask.
Addition of a twos complement number is even simpler than that of a ones complement number because by shifting the range down one, it effectively eliminates the need to add the carry flag returned from the half-adder to the value at the end. Therefore, by using one simple half-adder, every value can be added. This also has the added bonus of working simultaneously with unsigned bytes.
Twos complement has many advantages working for it. Negation is a two-instruction operation, the range is fully optimized, and addition can be used with a simple half-adder. Also, due to the nature of twos complement, when two numbers are added, regardless of whether they are unsigned or twos complements, the same result will be returned. This allows for support of negative numbers with literally no extra hardware involved, which has allowed for painless support of negative numbers to be a reality. For these reasons, it is the most commonly found representation of a negative number.
The storage of a negabinary number follows the exact same storage as a normal unsigned binary number, except that the radix under which it is stored is -2. This allows a range from -170 to 85, which can be shifted towards the positive side with a bias, or a constant that is added and subtracted as needed to shift the range of the value.
Negating a negabinary number is a tricky operation, especially without a bias where there may not be a value that exists in the range of the negabinary number that is the negative counterpart of the original value(i.e. When using an original value of -130). However, a general algorithm can be developed by checking each bit. If the bit is reset, add a 0 to a bitmask and if it is set add a 10 to the bitmask. Then xor the bitmask with the original number. The negated value should be returned.
Addition of negabinary numbers can occur with a half-adder, but this half adder is slightly tweaked in that it takes the carry and subtracts it from the next digit(if the digit is zero and the carry is one, the resulting digit would be zero). See figures on the last page of this document for the diagram of this circuit.
Negabinary excels at representing numbers such that every bit of the number is thoroughly used for a value(in that no bit is taken specifically for a sign bit) and in that respect, it is an interesting method of negative numbers in computing. However, do to the unusual nature of its format, it is not the most compatible with modern hardware, and a negation would subsequently require a loop through each of the operands bits to create a bitmask. It is unable to be added with unsigned bytes as with twos complement, and the rand is so asymmetrical that overflow errors could drastically change the value intended. Even through this list of disadvantages, due to its obscure nature, it is an interesting system to attempt to develop, and it just might have the potential to increase efficiency in computing if used with specialized hardware designed to “think” in negative radicies.
NOTE:Negabinary is also a great way to obscure any specific values you want to keep hidden from any potential reverse engineers....
The following are ASCII art diagrams of a normal half-adder and a half-adder designed for adding negabinary numbers. Notice that the only difference is the addition of the NOT gate on the carry before it is ANDed(instead of ORed) with the result of the computation. They are all in code boxes because that offers monospaced font ^_^
This is a bit level operation that occurs on all 8 bits individually.
After some review, the advantages and disadvantages of each of these systems is apparent. The Signed Magnitude representation of negative numbers is the easiest to negate: with only one flip of a bit, the value of the number can be negated successfully. However, it a very expensive operation to mathematically manipulate these values. Alternatively, the Ones Complement approach offers symmetric values with O(n) negation and a simple addition algorithm, providing a good tradeoff between negation and addition/subtraction. Twos complement has the same order of run time for negation and addition/subtraction as Ones complement, but has the distinct advantage of being able to handle signed and unsigned values in its addition algorithm. Negabinary, while unique in its lack of a sign bit, offers the same order as ones complement and twos complement in addition run time and an expensive negation algorithm.
I also feel the need to encourage you to play around with Negabinary, as I developed all the algorithms for it from scratch. Perhaps there is a way to negate them that is more efficient than my algorithm, who knows....
Cast your vote on this article 10 - Highest, 1 - Lowest
Comments: Published: 3 comments.
HackThisSite is is the collective work of the HackThisSite staff, licensed under a CC BY-NC license.
We ask that you inform us upon sharing or distributing.