PDA

View Full Version : Two's Compliment




MorphingDragon
Oct 8, 2009, 04:44 AM
Can someone explain to me what this is and how its used and how it might be useful? The programming book only touched on it and the books at school are useless. :confused:



robbieduncan
Oct 8, 2009, 05:45 AM
It's used to represent negative numbers.

cqexbesd
Oct 8, 2009, 06:36 AM
Can someone explain to me what this is and how its used and how it might be useful? The programming book only touched on it and the books at school are useless. :confused:

If you are at school you must have heard of Wikipedia...I thought it was all students used these days ;-)

http://en.wikipedia.org/wiki/Twos_complement

When it comes to being useful...it's used all the time in computing to make arithmetic work easily with integers, regardless of their sign (i.e. positive and negative numbers). If you want to understand it try doing arithmetic with binary numbers using a different representation scheme and you will soon be convinced that 2s-complement is a good idea.

That said, unless you are programming at a fairly low level (that is with little abstraction between you and the hardware) you are unlikely to have to deal with it directly very often. That doesn't mean you shouldn't understand how a computer actually works mind you - if you do then it allows you to become a better programmer, even if programming at a level of higher abstraction, for many reasons including working out what happened when it all goes wrong :-)

HTH,

Andrew

Flynnstone
Oct 8, 2009, 08:25 AM
That said, unless you are programming at a fairly low level (that is with little abstraction between you and the hardware) you are unlikely to have to deal with it directly very often.
Andrew

If you program in "C" or "C++" or many other languages, you deal with it very often.

"int" as in : int Ctr;
is 2's complement.

unsigned int Ctr;
is not 2's complement.

electroshock
Oct 8, 2009, 08:37 AM
If you program in "C" or "C++" or many other languages, you deal with it very often.

"int" as in : int Ctr;
is 2's complement.

I'm sure cqexbesd meant in the sense of directly twiddling the bits and doing an addition.

whooleytoo
Oct 8, 2009, 11:04 AM
I'm sure cqexbesd meant in the sense of directly twiddling the bits and doing an addition.

Quite possibly, though it is very important for starter programmers to learn the difference between signed and unsigned data types, and their respective ranges; even if they don't understand all the other ins-and-outs of twos complement.

notjustjay
Oct 8, 2009, 12:41 PM
I'm simplifying things here, but basically when it comes down to the bits and bytes, a CPU is only really able to do two things: add two bits, and compare two bits.

Everything else that CPU's do is broken down into steps that ultimately turn into adds and compares. By this time you're not looking at a CPU anymore, you're zoomed in really deeply and looking at individual logic gates, made up of little transistors.

So how do we do something as simple as add two numbers when all the CPU can do is recognize bits, 1's and 0's, on and off? It's almost common knowledge now that the answer is to use binary, so we add 12 + 7 by turning it into binary 1100 + 0111, which results in binary 10011 which is 19.

So how do we subtract?

Here's an example in decimal that I stole from Wikipedia. What's 873 - 218?

You can do something called the "9's complement" of 218 by taking each digit and subtracting it from 9, so you get 781. The 10's complement is the 9's complement plus 1.

So, add 873 + 781 + 1. You get 1655. Drop out the last digit and you get 655 which is the answer to 873 - 218. Congratulations, you just solved a subtraction problem by actually doing an addition problem!

http://en.wikipedia.org/wiki/Method_of_complements

(In binary, it's even easier to understand because instead of some nebulous "subtract the digit from 9" -- where did I get that from? -- you just flip the bits. If it was a 1, it's now a 0. If it was a 0, it's a 1. A simple inverter gate in logic-speak.)

The Wiki article explains better, but this is also a great way to represent negative numbers (not otherwise possible in binary). So negative numbers are represented internally in binary in 2's complement format. That's why in a language like C you need to specify whether you're working with signed or unsigned integers.

autorelease
Oct 8, 2009, 03:50 PM
In two's complement representation, you negate a number by flipping its bits and adding 1.

So, in C for example, (-x) is the same as (~x) + 1.

So "negating x" is the same as "taking the two's complement of x."

The bit-flipping operation (the "bitwise NOT" operation, ~ in C) is called the ones complement. Thus, the two's complement of a number is its ones complement plus 1.

gnasher729
Oct 8, 2009, 05:46 PM
Can someone explain to me what this is and how its used and how it might be useful? The programming book only touched on it and the books at school are useless. :confused:

Compliment = Saying something nice about someone.
Complement = Adding to something to make it complete.

1. You use binary digits to represent unsigned integer numbers. The least valued bit has a value of 1 (or 0), the second bit has a value of 2 (or 0), next bit has a value of 4, then 8, 16, 32, 64 etc. With 32 binary digits you can represent every unsigned integer number from 0 to 2^32 - 1 (two to the power of 32, minus 1).

2. To represent signed numbers as well, one bit is used to represent the sign of the number. For example, a 32 bit signed integer would use one bit as the sign bit, and the other 31 bits for the value. A positive number, like +5, is stored as sign bit = 0, and the remaining 31 bits contain the unsigned number 5. A negative number, like -5, is stored as sign bit = 1, and then there are different methods to decide what you would store in the other 31 bits.

3. A simple method is "signed magnitude" representation. In signed magnitude representation, the signed number -5 is stored as sign bit = 1, value bits = same as the unsigned number 5. Something similar is usually used for floating-point numbers. Signed-magnitude has the disadvantage that the two simplest operations, adding and subtracting, are quite complicated. You can see this by writing the bits for +5 and -5, and checking what happens to these bits if you add +1: Both numbers change in completely different ways.

4. Another method is called "one's complement" representation. To store the number -5, the sign bit is set to 1, the other bits are stored as the number 5, but with all bits reversed ("complemented"), so instead of 5 = 0000....0101, you store 1111....1010. This method has been used in some computers, like the Control Data supercomputers in the 1970's. Haven't seen it for a while.

5. A third, and the most common method, is called "two's complement". The simplest way to explain it is this: A positive number from 0 to 2^31 - 1 is stored in 32 bits exactly the same as if it was an unsigned number. A negative number x from -2^31 to -1 is stored exactly the same as the unsigned number 2^32 + x would be stored.

The biggest advantage of two's complement is that addition and subtraction of signed numbers can be performed using exactly the same hardware that is used for unsigned numbers. It's not just saving by using the same hardware, it is also the simplest possible hardware for these operations, and they are the most time critical operations in the processor of all. More complicated add/subtract would mean that your processor clock speed would go down.

MorphingDragon
Oct 10, 2009, 12:23 AM
Compliment = Saying something nice about someone.
Complement = Adding to something to make it complete.

1. You use binary digits to represent unsigned integer numbers. The least valued bit has a value of 1 (or 0), the second bit has a value of 2 (or 0), next bit has a value of 4, then 8, 16, 32, 64 etc. With 32 binary digits you can represent every unsigned integer number from 0 to 2^32 - 1 (two to the power of 32, minus 1).

2. To represent signed numbers as well, one bit is used to represent the sign of the number. For example, a 32 bit signed integer would use one bit as the sign bit, and the other 31 bits for the value. A positive number, like +5, is stored as sign bit = 0, and the remaining 31 bits contain the unsigned number 5. A negative number, like -5, is stored as sign bit = 1, and then there are different methods to decide what you would store in the other 31 bits.

3. A simple method is "signed magnitude" representation. In signed magnitude representation, the signed number -5 is stored as sign bit = 1, value bits = same as the unsigned number 5. Something similar is usually used for floating-point numbers. Signed-magnitude has the disadvantage that the two simplest operations, adding and subtracting, are quite complicated. You can see this by writing the bits for +5 and -5, and checking what happens to these bits if you add +1: Both numbers change in completely different ways.

4. Another method is called "one's complement" representation. To store the number -5, the sign bit is set to 1, the other bits are stored as the number 5, but with all bits reversed ("complemented"), so instead of 5 = 0000....0101, you store 1111....1010. This method has been used in some computers, like the Control Data supercomputers in the 1970's. Haven't seen it for a while.

5. A third, and the most common method, is called "two's complement". The simplest way to explain it is this: A positive number from 0 to 2^31 - 1 is stored in 32 bits exactly the same as if it was an unsigned number. A negative number x from -2^31 to -1 is stored exactly the same as the unsigned number 2^32 + x would be stored.

The biggest advantage of two's complement is that addition and subtraction of signed numbers can be performed using exactly the same hardware that is used for unsigned numbers. It's not just saving by using the same hardware, it is also the simplest possible hardware for these operations, and they are the most time critical operations in the processor of all. More complicated add/subtract would mean that your processor clock speed would go down.

Nu Uhh, I could be complimenting the computer in two different ways. XD...
I know, I get told off by my computing teacher.

http://www.witchyswikkedgraphix.com/categories/Thank%20You/thanks%20(50).gif

chown33
Oct 10, 2009, 06:06 PM
Compliment = Saying something nice about someone.
Complement = Adding to something to make it complete.


My favorite two's compliment: "Nice pair of bits you've got there."

Note: never say this to an inverter. A compliment is always inverted and taken as an insult.