binary numbers: 2's complement

Laserbeak43 · Post by **Laserbeak43** » Fri Dec 07, 2007 11:25 pm

Hi again

been stumped for at least a few days with this introductory 2's complement section of Programming the 6502 by Rodnay Zaks. it's a great book, i just seem bo be having a problem figuring out how certain things work i guess. like most of the whole 2's complement thing makes sense to me, until i start trying to work it out

Code: Select all

;signed numbers:

10111111
11000001
------------
10000000 

;but the real answer is

10000001

;cause in 2's complement, you ad 1 to it to get the result?

is this correct?? and if it is correct, has an overflow or an underflow occured? i'm not even sure that i can tell when one of these take place cause i've read about it being different than unsinged binary, though i'm not sure why it is.

thefox · Post by **thefox** » Fri Dec 07, 2007 11:50 pm

Correct answer is not 10000001... it is 10000000 like you calculated. The first number is -65, second one is -63, and -65 + (-63) = -128

jargon · Post by **jargon** » Fri Dec 07, 2007 11:50 pm

Laserbeak wrote:

Code: Select all

;signed numbers:

10111111
11000001
------------
10000000

;but the real answer is

10000001

;cause in 2's complement, you ad 1 to it to get the result?

Code: Select all


signed dec to signed char conversion:
f(x){
  return
    (sgn(x)==-1)
  ?
    (
      (abs(x)<=128)
    ?
      (
        (
          abs(x)^(0x7f)
        )
      +1)
    :
      0
    )
  :
    (x&0x7f);
}

i indented for easier reading (hopefully)
sorry for confusing you earlier, Laserbeak.

you can directly add two positive or a negative and postive signed char in unsigned binary, but not when both are negative.

disclaimer: there are overflow differences.

now for the sum:

the original method i told you:
bin 10111111 = unsigned dec 191 = signed dec -64
bin 11000001 = unsigned dec 193 = signed dec -62

unsigned bin 110000000 (OVERFLOW) = unsigned 384

the method you possibly used:
((10111111 and 01111111)-1) xor 0x7f = bin 00111110
((11000001 and 01111111)-1) xor 0x7f = bin 01000000
00111110 + 01000000 = bin 0111110
((0111110+1) xor 0xff)=(01111111 xor 0xff) = bin 1000000 = signed dec -128

this is correct

i hope this helps from our earlier convo, by the way sleep well Laserbeak.

jargon · Post by **jargon** » Sat Dec 08, 2007 12:39 am

(new post to reduce individual post size stress on MySql database)

method to convert signed char to signed dec:

Code: Select all

f(x)={
  return ((x&0x80)?-1:1)*(x^((x&0x80)?0x7f:0));
 // the following is incorrect to append: +((x&0x80)>>7)
}

remember:

Code: Select all

& is bitwise and
^ is bitwise xor
* is multiplication
foo?truthcase:falsecase is a boolean switch
>> is shift right
+ is addition
0xfoo is hexidecimal
// is a comment
<= is a less than or equal to inequality test that returns in most cases 1 for truth, 0 for false depending on the programming language

remember basica, gwbasic, and quick basic use -1 for true and 0 for false.

all systems test any value other than zero as true.

i feel the comment in my method to convert signed char to signed dec code explains your confusion, Laserbeak.

the only reason negative goes -1 to -128 while positive goes 1 to 127 is that zero is "00000000"

zero is "00000000"
positive uses "00000001" thru "01111111" as 1 thru 127
negative uses "10000000" thru "11111111" as -128 thru -1

jargon · Post by **jargon** » Sat Dec 08, 2007 2:12 am

simpler signed char to dec conversion.

Code: Select all

f(x){
return (x&0x80)?-((x&0x80)-(x&0x7f)):x;
}

blargg · Post by **blargg** » Sat Dec 08, 2007 5:16 am

First off, the simplest way to think of two's complement is that the highest bit simply has the negative place value it normally has. For an 8-bit value, that means the high bit has the place value -128 instead of the usual +128. And of course you don't have to do anything special when adding or subtracting two's complement values, since that's one of the main points of the representation, that it doesn't require different circuitry for add/subtract.

To "extract" a signed value, just flip the top bit then subtract its usual place value. So for an 8-bit value, XOR with 128 then subtract 128. This makes sense in light of the above. If the high bit was clear, after the flip it will be set, then the subtract will clear it again. If the high bit was set, then flipping it will clear it and subtracting 128 will yield the correct -128 place value.

Laserbeak43 · Post by **Laserbeak43** » Sat Dec 08, 2007 7:57 am

thefox:
Really? i did it right? damn, maybe this book is going so deep it's actually teaching, then confusing me. hmm wierd.

jargon:
Hehe, you sure know how to make extravagant explainations

yeah, i think i was starting to get some things in your examples but some stuff is still a blurr. mainly cause i haven't used the abs() and sgn() functions before i guess. i'll have to look those up sometime(this will be a good excuse to do so ) thanks.

Blargg:
you said:

For an 8-bit value, that means the high bit has the place value -128 instead of the usual +128.

i was under the impression that the highest 8-bit posative value in signed binary was 127. am i wrong?
all in all that does look like a nice and simple, easy trick.

i'm gonna finish working out the practice problems and post them. maybe someone will be kind enough to check them for me?

Disch · Post by **Disch** » Sat Dec 08, 2007 9:14 am

Laserbeak43 wrote: i was under the impression that the highest 8-bit posative value in signed binary was 127. am i wrong?

You're right. But Blargg was illustrating the following:

Code: Select all

given %10010010

unsigned:

   bit
76543210
--------
10010010
|  |  |
|  |  2
|  |
|  16
|
128

therefore:  2+16+128 = 146
--------------------
signed:

10010010
|  |  |
|  |  2
|  |
|  16
|
-128

therefore:  2+16-128 = -110

so $92 (%10010010) is
146 unsigned
or
-110 signed

Laserbeak43 · Post by **Laserbeak43** » Sat Dec 08, 2007 10:17 am

wow, good explanation! but that's just nuts. i guess it makes sense to the rest of the world though.
thanks guys, i'll give this thread a few looks till i understand.

Disch · Post by **Disch** » Sat Dec 08, 2007 11:18 am

it actually makes perfect sense.

Normally unsigned numbers would wrap 255 -> 0 (that is, you'd count 253, 254, 255, then you'd be back at 0 again)

2's compliment signed numbers wrap similarly: 127 -> -128... that is, it counts like:

125, 126, 127, -128, -127, -126, -125 .. etc

This works logically because when you clip to 8 bits, adding 255 is the same as subtracting 1. Example:

$63 - $01 = $62
$63 + $FF = $62 (really $162, but after clipping to 8 bits you're left with $62 because the $100 is lost)

2's compliment matches this logic *perfectly*. Because $FF is both 255 (unsigned), and -1 (signed).

Laserbeak43 · Post by **Laserbeak43** » Sat Dec 08, 2007 1:39 pm

so it's just pretty much different representation of the same absolute value of bits?

ok it's getting clearer

loopy · Post by **loopy** » Sat Dec 08, 2007 2:58 pm

Laserbeak43 · Post by **Laserbeak43** » Sat Dec 08, 2007 3:05 pm

Loopy:
Cool thanks

Here's another question though. this particular problem looks very confusing.

Code: Select all

;Negative-Negative Addition

11111110   (-2)
11111010   (-4)
------------------
11111010   (-6) with a disregarded carry

wtf??? the binary representation of -6 is the same as -4. what's that about????

loopy · Post by **loopy** » Sat Dec 08, 2007 3:14 pm

Laserbeak43 · Post by **Laserbeak43** » Sat Dec 08, 2007 4:16 pm

loopy wrote:-4 is 11111100, not 11111010.
Code: Select all
  11111110 (-2)
+ 11111100 (-4)
--------------
  11111010 (-6)

yes and i should've known that. but i was just so caught up in the fact that it looked like a typo that i didn't even bother to investigate it. binary is far from second nature to me, unfortunately. thanks.