Why prefer two's complement over sign-and-magnitude for signed numbers?
Solution 1
It's done so that addition doesn't need to have any special logic for dealing with negative numbers. Check out the article on Wikipedia.
Say you have two numbers, 2 and -1. In your "intuitive" way of representing numbers, they would be 0010
and 1001
, respectively (I'm sticking to 4 bits for size). In the two's complement way, they are 0010
and 1111
. Now, let's say I want to add them.
Two's complement addition is very simple. You add numbers normally and any carry bit at the end is discarded. So they're added as follows:
0010
+ 1111
=10001
= 0001 (discard the carry)
0001
is 1, which is the expected result of "2+(-1)".
But in your "intuitive" method, adding is more complicated:
0010
+ 1001
= 1011
Which is -3, right? Simple addition doesn't work in this case. You need to note that one of the numbers is negative and use a different algorithm if that's the case.
For this "intuitive" storage method, subtraction is a different operation than addition, requiring additional checks on the numbers before they can be added. Since you want the most basic operations (addition, subtraction, etc) to be as fast as possible, you need to store numbers in a way that lets you use the simplest algorithms possible.
Additionally, in the "intuitive" storage method, there are two zeroes:
0000 "zero"
1000 "negative zero"
Which are intuitively the same number but have two different values when stored. Every application will need to take extra steps to make sure that non-zero values are also not negative zero.
There's another bonus with storing ints this way, and that's when you need to extend the width of the register the value is being stored in. With two's complement, storing a 4-bit number in an 8-bit register is a matter of repeating its most significant bit:
0001 (one, in four bits)
00000001 (one, in eight bits)
1110 (negative two, in four bits)
11111110 (negative two, in eight bits)
It's just a matter of looking at the sign bit of the smaller word and repeating it until it pads the width of the bigger word.
With your method you would need to clear the existing bit, which is an extra operation in addition to padding:
0001 (one, in four bits)
00000001 (one, in eight bits)
1010 (negative two, in four bits)
10000010 (negative two, in eight bits)
You still need to set those extra 4 bits in both cases, but in the "intuitive" case you need to clear the 5th bit as well. It's one tiny extra step in one of the most fundamental and common operations present in every application.
Solution 2
Wikipedia says it all:
The two's-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract. This property makes the system both simpler to implement and capable of easily handling higher precision arithmetic. Also, zero has only a single representation, obviating the subtleties associated with negative zero, which exists in ones'-complement systems.
In other words, adding is the same, wether or not the number is negative.
Solution 3
Even though this question is old , let me put in my 2 cents.
Before I explain this ,lets get back to basics. 2' complement is 1's complement + 1 . Now what is 1's complement and what is its significance in addition.
Sum of any n-bit number and its 1's complement gives you the highest possible number that can be represented by those n-bits. Example:
0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
1111 (the highest number that we can represent by 4 bits)
Now what will happen if we try to add 1 more to the result. It will results in an overflow.
The result will be 1 0000
which is 0 ( as we are working with 4 bit numbers , (the 1 on left is an overflow )
So ,
Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)
Someone then decided to call 1's complement + 1 as 2'complement. So the above statement becomes: Any n'bit number + its 2's complement = 0 which means 2's complement of a number = - (of that number)
All this yields one more question , why can we use only the (n-1) of the n bits to represent positive number and why does the left most nth bit represent sign (0 on the leftmost bit means +ve number , and 1 means -ve number ) . eg why do we use only the first 31 bits of an int in java to represent positive number if the 32nd bit is 1 , its a -ve number.
1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________
1 0000 (result is zero , with the carry 1 overflowing)
Thus the system of (n + 2'complement of n) = 0 , still works. The only ambiguity here is 2's complement of 12 is 0100 which ambiguously also represents +8 , other than representing -12 in 2s complement system.
This problem will be solved if positive numbers always have a 0 in their left most bit. In that case their 2's complement will always have a 1 in their left most bit , and we wont have the ambiguity of the same set of bits representing a 2's complement number as well as a +ve number.
Solution 4
Two's complement allows addition and subtraction to be done in the normal way (like you wound for unsigned numbers). It also prevents -0 (a separate way to represent 0 that would not be equal to 0 with the normal bit-by-bit method of comparing numbers).
Solution 5
Two's complement allows negative and positive numbers to be added together without any special logic.
If you tried to add 1 and -1 using your method
10000001 (-1)
+00000001 (1)
you get
10000010 (-2)
Instead, by using two's complement, we can add
11111111 (-1)
+00000001 (1)
you get
00000000 (0)
The same is true for subtraction.
Also, if you try to subtract 4 from 6 (two positive numbers) you can 2's complement 4 and add the two together 6 + (-4) = 6 - 4 = 2
This means that subtraction and addition of both positive and negative numbers can all be done by the same circuit in the cpu.
Related videos on Youtube
Ray
Technical Business Analyst / Senior Developer working for in Fund Management in the City of London. Currently working on enterprise datawarehouse hub, vendor feed integration, client reporting solutions. A large chunk of which is Salesforce and the Force.com platform. Pretty broad enthusiast for all sorts. Project experience across C#, ASP.Net, LINQ, SQL, C++, Java, Python, Ruby on Rails, PHP, ColdFusion. Spare time Assembler tinkerer.
Updated on January 01, 2022Comments
-
Ray over 2 years
I'm just curious if there's a reason why in order to represent -1 in binary, two's complement is used: flipping the bits and adding 1?
-1 is represented by 11111111 (two's complement) rather than (to me more intuitive) 10000001 which is binary 1 with first bit as negative flag.
Disclaimer: I don't rely on binary arithmetic for my job!
-
Adisak over 14 yearsFWIW, your "intuitive" method of using a sign-bit is ocassionally used -- for example, most computers use a sign-bit when representing floating point numbers.
-
Cole Tobin about 11 years@Adisak It's called signed magnitude
-
Adisak about 11 yearsI've always associated sign-and-magnitude representation with integers since Floating Point numbers contain three components: a sign, an exponent, and a mantissa (often with an implicit '1'). But I guess it's easy enough to treat the exponent and mantissa as magnitude as long as one realizes they are not strictly linear.
-
GDP2 over 6 yearsHere's an article discussing how floating-point numbers are stored in binary, for those who are curious about @Adisak's remarks.
-
allenlinli about 5 yearsJust saw a nice video explaining this youtube.com/watch?v=dHB7jFjESLY
-
-
Lazer about 14 yearsI agree. 2's complement works. But how did we arrive at it in the first place? If suppose I need to arrive at this notation, what would the thought process be. I think arriving at 2's complement has to be more than just luck, isn't it?
-
Lazer about 14 yearsAlso, why is there no 2's complement counterpart for floats?
-
Harshal Gajjar over 9 yearsCan anyone tell me how does computer know that it's 2s complement and not any other poisitive binary number?
-
Ankit over 9 years@HarshalGajjar to computer it does not matter whether it is 2 complement or not. For it, it is just a binary number and it simply perform the operation. However the 2's complement come into picture while saving the data in binary. So if you have a negative number, it is automatically represented in 2s compliment and stored, and positive number is saved as it is. Please correct me if I am wrong.
-
Ankit over 9 years@Lazer check this article to know
how we arrived at 2s compliment the first place.
cs.cornell.edu/~tomf/notes/cps104/twoscomp.html -
phuclv almost 9 yearsNot that only non-widening multiplication is the same. But as most high level languages don't support widening multiplication without explicit cast, the result will be the same in those languages.
-
phuclv almost 9 yearsnon-widening multiplication is also the same and you don't need separate circuitry for that
-
hagrawal almost 9 years+1'ed. It was information, however in the end it I am not sure why you wanted have the approach of most significant bit to represent whether it is a positive or negative number. It has many issue like 0 will have 2 representations - 0000(+) and 1000(-) .. Also addition and subtraction cannot be done using same algorithm. When you say an normal 0100 then it is +8 and when you say two's complement 0100 then it is -12 ..
-
hagrawal almost 9 yearsThanks for an informative post .. Is my understanding correct - When I say normal 0100 then it is +8 and when I say two's complement 0100 then it is -12 ?? In Java, negative numbers are stored as 2's complement ??
-
Welbog almost 9 years@hagrawal, no. 0100 is +4. The bits are -8, 4, 2 and 1, so 0100 is 0*-8 + 1*4 + 0*2 + 0*1 = 4. This is true in two's complement or "normal".
-
hagrawal almost 9 yearsSorry, I goofed up .. 2's complement of 0100(4) will be 1100. Now 1100 is 12 if I say normally. So, when I say normal 1100 then it is 12, but when I say 2's complement 1100 then it is -4? Also, in Java when 1100 (lets assume 4 bits for now) is stored then how it is determined if it is +12 or -4 ??
-
Welbog almost 9 yearsJava only has signed integer types as far as I'm aware, so it always treats it in its two's complement interpretation. In other languages, how the value is treated depends on how the code treats it. There's nothing to tell you that a block of memory is a signed or unsigned integer or a double or a string or something else. The raw data is whatever type you choose to interpret it as.
-
user4581301 over 8 yearsThat code blob needs an edit so readers don't have to keep scrolling back and forth. Better, that massive comment at the top should become plain old text and let the renderer take care of the formatting. You should also add a caveat to the bit near the end where you discuss the sizes and formatting because the sizes are not fixed.
-
mw215 over 8 years@hagrawal The system establishes how to interpret a sequence of bytes through types. Below you can find a more elaborate version of this comment.
-
Welbog over 8 years+1. One thing you might consider doing, @mw215, is making this question/answer pair a Community Wiki entry on its own, because it's useful for people who might be interested in raw byte interpretation outside of the context of two's complement math.
-
Suraj Jain over 7 years@Welbog how can
1111
be negative one . It does not when i try to convert it into decimal. I am so confused? -
Suraj Jain over 7 years@Welbog If i take most significant bit as the identifier whether this number is positive or negative . Then
1111
MSB is1
so number is negative then how does the remaining part tells that it is-1
. I mean it does not add up to1
so that the result becomes-1
.MSB telling that the number is negative. What Really Happens? -
Welbog over 7 years@Suraj, I suggest looking at the Wikipedia article on two's complement for the full answer: en.wikipedia.org/wiki/Two%27s_complement. The short answer is the MSB
1
indicates-8
, and the remaining three1
s indicate4
,2
, and1
, respectively, so-8+4+2+1 = -1
. -
Suraj Jain over 7 years@Welbog I Just want to know is 2's complement always follow , i mean if i have
int x = -4
, and i then doprintf("%d" , x)
how does it get interpreted ? Also what is the difference betweenunsigned int
andsigned int
and%d
and%u
... this has been bugging me for a long time now .Thanks. -
Suraj Jain over 7 yearsI Just want to know is 2's complement always follow , i mean if i have
int x = -4
, and i then doprintf("%d" , x)
how does it get interpreted ? Also what is the difference betweenunsigned int
andsigned int
and%d
and%u
... this has been bugging me for a long time now .Thanks. -
Suraj Jain over 7 yearsPlease Format Your Answer In Paragraph and mark code as code , it would be more readable and you will get upvote.
-
Suraj Jain over 7 yearsSir , if i write char a = 12 ; and unsigned char b = 12 , is the underlying bit patter same , what really happens ?
-
supercat over 7 years@SurajJain: Is that better?
-
Suraj Jain over 7 yearsYeah , better than what it earlier was , i want to ask you one thing what is the difference between signed char a = 1 and unsigned char a = 1 , how are they represented in memory.
-
supercat over 7 years@SurajJain: On two's-complement systems where "char" is smaller than "int" [i.e. the vast majority of systems], the signed and unsigned char types will behave identically except that signed types will be sign-extended when read and unsigned types won't. On such a system, storing the value 194 or -62 into a signed char will write the same bit pattern as storing 194 or -62 into an unsigned char (i.e. 11000010). Reading that bit pattern from a signed char will yield -62, and reading it from an unsigned char will yield 194.
-
Suraj Jain over 7 yearssign-extended means ?
-
supercat over 7 years@SurajJain: Copying the value of the top bit of a shorter type to all of the upper bits of a longer type. So a system with 16-bit "int", reading the signed char value 11000010 would yield the int value 1111111111000010.
-
Welbog over 7 years@Suraj, Two's complement only applies to signed integers. Unsigned integers don't need to represent negative numbers, and two's complement is a way of representing negative numbers.
%d
forces it to print as a signed integer, and%u
forced it to print as an unsigned integer. -
Suraj Jain over 7 years@Welbog If i write char x = -1 and unsigned char x = -1 , what would be the underlying representation ?
-
Suraj Jain over 7 yearsJust want to know is 2's complement always follow , i mean if i have int x = -4 , and i then do printf("%d" , x) how does it get interpreted ? Also what is the difference between unsigned int and signed int and %d and %u ... this has been bugging me for a long time now .Thanks
-
Suraj Jain over 7 yearsIf i write
signed int a = -1
, then-1
in 2's complement form is11111111 11111111 11111111 11111111
and then when i use%d
to interpret it it prints-1
and%u
, it prints4294967295
and when i writesigned int a = 2
, it prints2
when i use%d
and also when i use%u
. If 2 would be in two's complement it would be11111111 11111111 11111111 11111101
, and then it would be a very diffrenet answer , what i really want to ask is when does 2's complement happen is it depend on-
sign or it happens for every integer if type is signed int which must not be the case here. -
Suraj Jain over 7 yearsAlso when i write
unsigned int a = -1
, then-1
in 2's complement form is11111111 11111111 11111111 11111111
and then when i use%d
to interpret it it prints-1
and%u
, it prints4294967295
.So if a number is negative it is alwasys stored as 2's complement no matter the type unsigned or signed , is that right ... this question has been bugging me for a while , i would have asked a new question on stackoverflow , but my experience tells me it is not very friendly to beginner , so i am afraid to write a new question. -
supercat over 7 years@SurajJain: If the situation described, the
printf
will output -4. Sane implementations on commonplace hardware will treat signed values fromINT_MIN
to -1 as equivalent to unsigned values fromINT_MAX+1u
toUINT_MAX
, but the Standard would allow a compiler to do anything it likes if%u
or%x
is used on a value of typeint
or "%i` or%d
is used on a value of typeunsigned
. -
supercat over 7 years@LưuVĩnhPhúc: Widening multiplication will usually be the same, but results for signed and unsigned multiply are only guaranteed to be the same if the result would fit in the range of a signed int. Some compilers like gcc, given something like
unsigned mul(unsigned short x, unsigned short y) { return x*y; }
[16-bit short; 32-bit int] will occasionally generate code that will malfunction if the product is larger than 2147483647. -
Suraj Jain over 7 yearsIf i write
signed int a = -1
, then ` -1` in 2's complement form is11111111 11111111 11111111 11111111
and then when i use%d
to interpret it it prints -1 and %u , it prints4294967295
and when i writesigned int a = 2
, it prints 2 when i use%d
and also when i use%u
. If2
would be in two's complement it would be11111111 11111111 11111111 11111101
, and then it would be a very diffr answer , what i really want to ask is when does 2's complement happen is it depend on - sign or it happens for every integer if type issigned int
which must not be the case here. -
supercat over 7 years@SurajJain: Two's-complement is relevant for values less than zero or beyond the positive range of an integer's type. Non-negative values which are within the range of a signed integer type will simply behave as numbers.
-
Suraj Jain over 7 yearshow does computer knows when to do 2's bit complement and when to not , i have many doubts , if you would be able to clear it , it would be of great help.
-
mw215 over 7 years@Suraj Jain When using
int
types, thesigned
modifier is default. This means thatint
andsigned int
are exactly the same type. Thus the two definitionsint i = -4;
andsigned int i = -4;
have the same meaning. -
mw215 over 7 years@Suraj Jain The system establishes how to interpret a sequence of bytes through types. Types define: how many bytes have to be considered and how those bytes have to be interpreted. An
int
is 4 bytes in 2's complement and anunsigned int
is 4 bytes in plain binary notation (check the actual type size on your system using thesizeof
operator). -
mw215 over 7 years@Suraj Jain So, for instance, after
int x = -4;
you would have the following adjacent 4 bytes somewhere in RAM:11111111 11111111 11111111 11111100
; while afterunsigned int x = 4;
the 4 adjacent bytes in RAM would be00000000 00000000 00000000 00000100
. -
mw215 over 7 years@Suraj Jain As for
printf
formatting, you can use both%d
and%u
with either anint
or anunsigned int
. In fact, if you use%d
"Theint
argument is converted to signed decimal in the style [−]dddd" and an analogous conversion takes place using%u
.d
andu
are called "conversion specifiers" in the C Standard. -
Welbog over 7 years@Suraj, I think you have some incorrect assumptions about two's complement and signed and unsigned numbers. In memory, there is no difference between a signed and unsigned number. The
signed char x = -1
andunsigned char y = -1
have the same representation in memory. The same ones and zeroes in the same order. The only difference between the two is how they're interpreted. When stored in an unsigned variable, they're interpreted as unsigned. When stored in signed variables, they're signed. When printed as signed, they're signed, etc. The same is true forun/signed char z = 2
. -
Welbog over 7 years@Suraj, you should always ask new questions as questions. This site is helpful to new users if their questions are clear. New users often have a hard time forming their thoughts into a clear question, but get the hang of it when looking at other questions. If you want to ask your question as a question and link it here, I will do my best to answer it.
-
Suraj Jain over 7 years
-
Talespin_Kit over 7 yearsNothing changes when writes or reads. Only applicable when addition or subtraction.
-
Rob over 7 yearsactually, if you have a decimal point and are explicit about what all bits are: "0..0000.1111..1" means that all left-most unstated bits are 0, and all right-most unstated bits are 1, and therefore the "..1" means that a carry is triggered. Therefore it's (mechanically) "0.0001.0000..0". It means that "1..1111.1111..1" is equal to zero! This also means that to negate an integer, you really do just flip its bits. But it now applies to representable fractions.
-
0xB00B over 2 yearsBut with two's complement (assuming 4bit ints), 7+1 = -8, Isn't that counterintuitive ?
-
Welbog over 2 years@Tanishq-Banyal: yes, but it's a small price to pay on the edge case to enable a much easier time, computationally, for the average case.
-
Geremia almost 2 yearsYes, having a negative zero is a waste.