|
SoCoder -> Article Home -> Advanced Techniques |
|
|
|
|
Scherererer
|
Storing Signed IntegersAn Explanation of 2's Complement |
|
Storing Signed Integers: 2's Complement One of the early problems in computing technology was how to store signed (negative and positive) numbers versus unsigned (only positive) numbers. This article goes over how modern computers store signed variables bit for bit. note: this article will consider the word to be 4 bits for simplicity. Most modern computers use a 32 bit or 64 bit word architecture, however all examples will be with 4 bits, though the methods described can be easily applied to longer bit lengths. The Sign Bit MethodThe method that seems to most logical at first is by having a sign bit. This is very simple, it involves using the first bit to denote sign, and the remaining bits to denote value.For example: 1010 would break down to 1 = negative, 010 = 2 0111 would break down to 0 = positive, 111 = 7 The problem with the method is that there is a redundancy: you can have a positive and negative zero, i.e. 0000 and 1000 are positive and negative zero, respectively. In the 4-bit example, numbers can go from -7 to +7. Another issue that arises is when math is done on the computer. It is more difficult for the computer to do simple arithmetic, because it has to account for sign in an awkward manner; there is no general case for mathematical operations. The Solution: 2's ComplementLuckily, computer scientists have come up with a neat way of handling positive and negative numbers called 2's Complement. Here's what you do:given a positive number, it's 2's complement (negative form) is it's bits flipped plus 1. for example, the number 7 in 2's complement: 0111 7 in positive form 1000 bits are flipped 1001 add one. This can be used in the reverse as well, let's say we have -7, which we just found to be 1001: 1001 -7 0110 bits are flipped 0111 add one. as you can see, 2's complement can be flipped back and forth in the general case. Let's observe what's important about all of this: - There's only one zero (0000). - We've squeezed an extra negative number out (now runs from -8 to 7) - Math with 2's complement is easy! - We can still tell the sign by looking at the first bit! When a computer does addition with 2's complement, everything works properly. Unlike with a sign bit where the computer has to decide between addition and subtraction based on the sign and then work out the sign at the end, 2's complement takes care of everything without any work -- you only have to add no matter the sign! for example: add 4 (0100) and -5 (1011) 0100 +1011 ------ 1111 Look at that! we got -1! To verify, we'll do the 2's complement of the result to see what it is 1111 0000 0001 (now we know it in positive form it's 1) cool beans! This is the method that all modern computers use today for signed integers, and now that you know it, you can do all kinds of cool manipulations with ints  But also, this reveals something else cool: if you ever noticed that continuously incrementing an integer (signed integer) eventually results in a "negative" number being displayed, you're whitnessing what's called an overflow. Here's an example: add 7 and 1 0111 +0001 ------ 1000 oh no! we got -8? That doesn't make any sense! But here's what happened: the bits that were added carried over, and overflowed into the sign bit place, telling us that it was a negative number. However, in reality, we know that 7+1 is 8, and so it's important for us to know the limitations of our system architecture, just in case we're adding two really really big numbers together. Hope this was helpful! |
|
|
|
|
Comments |
|
| Wednesday, 06 January 2010, 23:32 | |
|
Sticky |
Well done, this actually explained the use of Twos-Complement. When I'd read about it earlier on Wiki or somewhere else it didn't explain it particularly well so I was just left thinking "Well, that's a stupid idea. I wonder why they did that." So, thanks
|
| Thursday, 07 January 2010, 05:10 | |
|
CodersRule |
Yeah, I vaguely understood it when I was learning Z80 Assembly. Now it makes sense   oh no! we got -8? That doesn't make any sense! But here's what happened: the bits that were added carried over, and overflowed into the sign bit place, telling us that it was a negative number. However, in reality, we know that 7+1 is 8, and so it's important for us to know the limitations of our system architecture, just in case we're adding two really really big numbers together.  But just remember, an unsigned long long can go up to 18446744073709551615
|
| Thursday, 07 January 2010, 07:14 | |
|
Sticky |
Or if you're into using an unsigned dqword, you can go up to 340282366920938463463374607431768211455
|
|
|
| |||
|
| ||||