Results 1 to 12 of 12

Thread: (-n == ~n + 1)?????

  1. #1

    Thread Starter
    Dazed Member
    Join Date
    Oct 1999
    Location
    Ridgefield Park, NJ
    Posts
    3,418

    (-n == ~n + 1)?????

    I figured out how to take a negative number in binary and convert it to it's absoulte value with (-n == ~n + 1).

    -256 = 1100000000
    255 = 0011111111 + 1 = 256

    or

    -16 = 1111110000
    15 = 0000001111 + 1 = 16

    ok..... now then. If i want to find a postive numbers negative
    counterpart how would i go about doing this? Would this be correct? (n == -n >> 1) This seems to work on random numbers. For instance: 256 = 1000000
    -256 = 1100000
    but not on every number. How would i go about doing this?

    Thanks guys!!

  2. #2
    Frenzied Member
    Join Date
    Mar 2000
    Posts
    1,089
    the way this works is that -1 in binary is 11111111.

    and for any binary number x x + ~x = 11111111.

    because for any bit in x, the corresponding bit in ~ is the opposite, so if the x bit is 1 the ~ bit is 0 and vice versa. so both bits add up to 1.


    and hence we get the identity


    x + ~x = -1

    so x + ~x + 1 = 0

    -x = ~x + 1


    so for any integer x : -x = ~x + 1

    it doesn't matter if x is +ve or -ve the same formula applies.
    If it wasn't for this sentence I wouldn't have a signature at all.

  3. #3
    Frenzied Member
    Join Date
    Jul 1999
    Location
    Huntingdon Valley, PA 19006
    Posts
    1,151

    Forget memory.

    I will not try to describe what appears in the memory of an Intel Chip. It is strange, especially Single & Double variables.

    Most computers use complements for negative numbers, rather than signed magnitude. To understand binary complement notation, it is best to think of fixed length binary numbers. I will use 12-bit numbers.

    001 ----->> 0000 0000 0001
    -001 ---->> 1111 1111 1111

    255 ---->> 0000 1111 1111
    -255 --->> 1111 0000 0001

    256 ---->> 0001 0000 0000
    -256 --->> 1111 0000 0000

    097 ---->> 0000 0110 0001
    -097 --->> 1111 1001 1111

    If high order bit is one, the number is negative. Oddly enough, the high order bit is not really analogous to the sign. It actually has a negative weight.

    In the above, the high order bit acts like -2048, while the other bits act as 1024, 512, 256, 128, et cetera.

    The algorithm for changing a positive to a negative number or vice versa is as follows.
    • Change one bits to zero bits and vice versa.
    • Add one, carrying as required.
    • If the carry into the highest order bit is not the same as the carry out, you have overflow.
    The most negative number is the following.

    1000 0000 0000

    If you complement it, you get 0111 1111 111 before adding one. When you add one, you get 1000 0000 0000, which is not positive, indicating overflow and an erroneous result. Note that you got carry into the highest order bit, but not carry out.

    The carry in-out rule is applied to all add/subtract operations.

    When adding, there is no special logic relating to the sign. Just add the two numbers. If there is no overflow, the high order bit tells you whether the result is positive or negative.

    To subtract. complement the number you are subtracting and add.
    Live long & prosper.

    The Dinosaur from prehistoric era prior to computers.

    Eschew obfuscation!
    If a billion people believe a foolish idea, it is still a foolish idea!
    VB.net 2010 Express
    64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.

  4. #4

    Thread Starter
    Dazed Member
    Join Date
    Oct 1999
    Location
    Ridgefield Park, NJ
    Posts
    3,418
    "the way this works is that -1 in binary is 11111111. "

    Wouldnt 11111111 in Binary be 255? not -1. What i dont understand is if the highest order byte determines wether the number is a negative or a postive and 11111111 = 255 why isnt this negative? It higest order byte is 1 right?

    To convert negitive to postive.

    (-n == ~n + 1)

    -156 = 1101100100
    155 = 0010011011 + 1 = 156

    "it doesn't matter if x is +ve or -ve the same formula applies."

    I dont think the same formula would apply.
    To reverse( to convert the positive back to negative wouldnt we take 156 minus 1 and reverse the bits? (n - 1 == ~n)

    156 - 1 = 155
    155 = 0010011011
    - 156 = 1101100100 = - 156

  5. #5

  6. #6
    Frenzied Member
    Join Date
    Jul 1999
    Location
    Huntingdon Valley, PA 19006
    Posts
    1,151

    Some ground rules are required.

    It gets very confusing if you do not specify some basic rules about variable size and what the notation is. It is also easier to read binary if you use spaces to create groups of 4 bits.

    8-bit bytes are usually defined as unsigned integers, in which case the following is valid.
    • 0000 0000 is zero, the smallest possible value.
    • 1111 1111 is 255, the largest possible value.
    • There are no negative values possible.
    If you define 8-bit bytes as signed integers using complement binary, the following are valid.
    • 0000 0000 is zero, the smallest non-negative value.
    • 0111 1111 is 127, the largest possible positive value.
    • 1111 1111 is minus one.
    • 1000 0000 is minus 128, the algebraically smallest value.
    For both of the above, the high order bit has a weight of 128. For unsigned binary it is a positive weight. For signed complement binary it is a negative weight.

    I did not analyze your algorithm carefully, but it seems to be correct.

    However, when doing binary arithmetic, you should stick with binary operations. You are describing an algorithm which requires converting binary to decimal and vice versa. The conversion is tuffer than the binary operations.

    Read my previous post to this thread. It is valid. Converting positive to negative uses the same algorithm as converting negative to positive.
    Change one bits to zero bits & vice versa. Then do an unsigned addition of 1 to the bit reversed value.
    Live long & prosper.

    The Dinosaur from prehistoric era prior to computers.

    Eschew obfuscation!
    If a billion people believe a foolish idea, it is still a foolish idea!
    VB.net 2010 Express
    64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.

  7. #7
    Frenzied Member HarryW's Avatar
    Join Date
    Jan 2000
    Location
    Heiho no michi
    Posts
    1,827
    There is one's complement and there's two's complement. What you're talking about here is two's complement. If I remember right, in one's complement 1111 1111 is a duplicate value for 0 and you can only represent -127 to 127 in 8 bits, rather than the -128 to 127 you can represent in two's complement.

    Dilenger, the two conversion algorithms are functionally identical. Negating the value and adding one is the same as subtracting one and then negating. You can do either, but usually you add one after the negation, or at least that's what I've always seen.
    Harry.

    "From one thing, know ten thousand things."

  8. #8

    Thread Starter
    Dazed Member
    Join Date
    Oct 1999
    Location
    Ridgefield Park, NJ
    Posts
    3,418
    "8-bit bytes are usually defined as unsigned integers, in which case the following is valid."

    1111 1111 is 255, the largest possible value.


    "If you define 8-bit bytes as signed integers using complement binary, the following are valid."

    1111 1111 is minus one.


    Im a little confused........
    I dont see how -1 is represented as 1111 1111 in binary. I punched 255 into ever conversion calculator i have and 255 comes out to 1111 1111. -1 comes out to 11 1111 1111

    Also i dont see how the same formula would apply.

    (-n == ~n + 1)

    -163 = 11 0101 1101
    00 1010 0010 = 162
    162 + 1 = 163
    ok
    but to apply the same formula, it doesnt seem to work.

    (n == ~n +1)
    163 = 1010 0011
    0101 1100 = 92
    92 + 1 = 93

    to me it only makes sense to work backwards to reverse.
    ((n-1) ~n == (-n))

    163 - 1 = 162
    162 = 00 1010 0010
    -163 = 11 0101 1101

    another example:

    neg to pos (-n == ~n +1)
    -484 = 10 0001 1100
    01 1110 0011 = 483
    483 + 1 = 484
    ok

    pos to neg ((n-1) ~n == (-n))
    484 - 1 = 483
    483 = 01 1110 0011
    -484 = 10 0001 1100


    Well anyway thanks for your guys help. I know this is a boring subject so i will leave this for another time.
    Thanks again.

  9. #9
    Frenzied Member
    Join Date
    Jul 1999
    Location
    Huntingdon Valley, PA 19006
    Posts
    1,151

    Watch closely.

    Dilenger4: If you were not intelligent, you probably would not be posting at VB forum, but are you really paying attention?

    Do not try to apply the results from your calculator without thinking about what is going on. You are ignoring word length, the length of the registers involved in binary operations. According to your last post, you got the following results from your calculator.

    255 is 1111 1111
    -1 is 11 1111 1111

    The above suggests to me that your calculator provides 10-bit integers and perhaps leaves off leading zero bits. A calculator which provides 16-bit binary integers would give you the following results.

    1023 is 11 1111 1111 (which is the above 10-bit value for minus one)
    -1 is 1111 1111 1111 1111

    Word length affects the results you get. In you previous post, you provided the following.

    -163 --->> 11 0101 1101, correct for 10-bit arithmetic.
    163 ---->> 1010 0011, correct for 8-bit arithmetic, not quite correct for 10-bit.

    163 ---->> 00 1010 0011 is correct value for 10-bit arithmetic.
    reverse is 11 0101 1100
    +1 is -->> 11 0101 1101, which is -163 (same as above).

    Note that to apply the algorithm I previously posted, you need not know the decimal equivalents of the binary values. You merely reverse the bits and add one. It works for negating both positive and negative values.

    This algorithm is used by the arithmetic units of many binary systems. Subtraction is usually implemented by negating and adding. Negation is also used in the division process of many arithmetic units.
    Live long & prosper.

    The Dinosaur from prehistoric era prior to computers.

    Eschew obfuscation!
    If a billion people believe a foolish idea, it is still a foolish idea!
    VB.net 2010 Express
    64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.

  10. #10

    Thread Starter
    Dazed Member
    Join Date
    Oct 1999
    Location
    Ridgefield Park, NJ
    Posts
    3,418
    Why thank you. I think

    I see what you mean now.

    neg to pos (-n == ~n +1)

    -484 = 10 0001 1100
    01 1110 0011 = 483
    483 + 1 = 484

    pos to neg (n == ~n +1)
    484 = 01 1110 0100
    10 0001 1011 = - 485 + 1 = 484

    same formula applies.....

    i still think ((n-1) ~n == (-n)) would work though.

    pos to neg ((n-1) ~n == (-n))
    484 - 1 = 483
    483 = 01 1110 0011
    -484 = 10 0001 1100

    Thanks......

  11. #11
    Frenzied Member HarryW's Avatar
    Join Date
    Jan 2000
    Location
    Heiho no michi
    Posts
    1,827
    Well yes it would work, because they are the same. Negating then adding is the same as subtracting then negating.

    123-1 = 122
    negated is -122

    123 negated is -123
    -123+1 = -122

    Just the same.
    Harry.

    "From one thing, know ten thousand things."

  12. #12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width