Thread: Two's complement

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    244

    Two's complement

    Sorry, I didn't want to start a new thread as this is not DIRECTLY tied to C programming..

    I need to understand one’s and two's Complement System Arithmetic.

    Here is an example problem:

    ______________________________________________
    Step1: Represent -3 and +5 as 4-bit numbers

    So, -3 = 1100 and +5 = 0101

    Step2: Add +5 to -3

    1100 = -3
    + 0101 = +(+5)
    -------------------
    0001
    + 1
    -------------------
    0010 = +2


    Carry into MSB is 1 and carry out of MSB is 1. No overflow.

    __________________________________________________

    The only thing I don't understand is how they got "Carry into MSB is 1 and carry out of MSB is 1"

    I think I understand overflow but I am not sure. The way I see it, one way of detecting overflow is if you add two positive numbers and end up with a negative result or you are suppose to end up with a negative result and you end up with a positive result that that is considered overflow. Is that correct?

    Thank you in advance for the help.

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    Carry into MSB is 1 and carry out of MSB is 1
    MSB = Most significant bit.
    In this case adding bit 2^2 (3rd from the right) results in (1+1 = 0 carry 1), and adding the MSB (2^3) results in (1+0 + [carry 1] = 0 carry 1).

    The way I see it, one way of detecting overflow is if you add two positive numbers and end up with a negative result or you are suppose to end up with a negative result and you end up with a positive result that that is considered overflow. Is that correct?
    Yes. However not all numbers are two's complement (read: unsigned integer) so more technically an overflow is when the result of an operation is too big to fit in whatever the answer is supposed to go into.
    That is, some bits have to be dropped (the most significant ones) in order to keep the answer to, say, 8 bits.
    Consider this post signed

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    244
    Thanks for the reply bernt. I now understand overflow a lot better, however, I am still completely lost when it comes to carry in/out of MSB:/

  4. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    244
    can anyone give me some more pointers? I really am lost when it comes to carry/ overflow:/

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Your math is wrong. -3 is 1101 (because 3 is 0011, invert to 1100, add 1: 1101).
    Add 1101 and 0101:

    1101
    0101
    ---------
    1 0010

    The carry bit is the bit next to the MSB. In this case, it's 1 (the one to the far left).
    This is the carry out.

    What they actually mean by carry in/out to the MSB I don't know.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Carry in/out (or carry input and output) refers to how the carry flag is being used by an instruction. A carry input means the instruction will use the the carry flag. A carry output means the instruction will change the carry flag (whether or not the change actually occurs).

    EDIT:

    I feel I should emphasize that the above is indeed only for the carry flag (CF). Not for the carry bit. Do not confuse both. The CF is set according to the value of the carry bit, naturally. But some instructions may change the carry bit without that meaning they are carry out instructions. In this group are all instructions where the CF is classified as undefined.

    Also, because the carry flag can be used as a borrow flag, one can be pedantic and insist carry out/in instructions do not apply to instructions that use CF as a borrow flag. In this case the terminology should be borrow in/out. Personally I don't think one can be pedantic enough in assembly. So these distinctions make all sense to me. But they can also be useful if one thinks for instance that some processors do make the distinction very clear. See, Carry flag vs. Borrow flag header in http://en.wikipedia.org/wiki/Carry_flag (the last paragraph in that header also lists the unfortunate exceptions and who should be more careful with their terminology)
    Last edited by Mario F.; 08-29-2010 at 08:57 AM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #7
    Registered User
    Join Date
    Feb 2010
    Posts
    244
    Quote Originally Posted by Elysia View Post
    Your math is wrong.
    My math is NOT wrong. This is actually suppose to be 1's complement. My post's got moved to this thread by a moderator.

    thanks for the responses

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Ah. I see.
    It's wrong for two complement, but for one complement I don't know.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. integer to two's complement
    By -EquinoX- in forum C++ Programming
    Replies: 8
    Last Post: 11-30-2009, 11:39 AM
  2. two's complement
    By alyeska in forum C++ Programming
    Replies: 4
    Last Post: 10-21-2007, 09:55 PM
  3. sscanf and 32 bit two's complement
    By The Urchin in forum C++ Programming
    Replies: 4
    Last Post: 10-15-2006, 02:17 AM
  4. two's complement question
    By NetWeirdo in forum C Programming
    Replies: 1
    Last Post: 12-10-2005, 02:36 PM
  5. Two's Complement
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 02-26-2002, 05:52 AM