This is a discussion on Question about Two's Complement within the Tech Board forums, part of the Community Boards category; I am having a little trouble understand two's complement. I kind of get the general idea. What I don't get ...

1. ## Question about Two's Complement

I am having a little trouble understand two's complement. I kind of get the general idea. What I don't get is why an overflow occurs here? 1100 1000 which is 100+100 does in fact equal 200.... Can someone please explain this to me?

Thanks.... (The problem below was copied from my notes from class)

0110 0100 = +100
+ 0110 0100 = +(+100)
-------------------
1100 1000 = -56

WRONG! Carry into MSB is 1 and carry out of MSB is 0. Overflow condition occurs!

2. Also,
Why does: (- 40 * 144) mod 71 =62???!

When I calculate it, I get -9 for the answer.

3. Originally Posted by matthayzon89
WRONG! Carry into MSB is 1 and carry out of MSB is 0. Overflow condition occurs!
To understand that explanation you look into the overflow flag.

This flag is set whenever the most significant digit is changed. In the 8bit unsigned mathematical operation you perfomed, adding 01100100 to itself will set the overflow flag because the result is 11001000.

Now, with the overflow flag set, you know that the sign didn't change. Meaning, you must interpret 11001000 as a positive number, because the numbers being added had their most significant digit as 0 and were thus positive (the overflow flag is never set when you add or subtract positive and negative numbers. Only when both are either positive or negative).

Originally Posted by matthayzon89
Why does: (- 40 * 144) mod 71 =62
It's probably the result of one of the methods applied to the mod operation when there are negative operands involved. See here.

4. Originally Posted by matthayzon89
Also,
Why does: (- 40 * 144) mod 71 =62???!

When I calculate it, I get -9 for the answer.
It's just the way the C language chose to implement it.

From Modulo operation - Wikipedia, the free encyclopedia

When either a or n are negative, this naive definition breaks down and many programming languages differ in how these values are defined.

...This means there are two possible choices for the remainder, one negative and the other positive, and there are also two possible choices for the quotient. Usually, in number theory, the positive remainder is always chosen, but programming languages choose depending on the language and the signs of a and n.

5. I figured it out, its actually far more simple than what I thought....

-40 * 144 mod 71 =
[-40 mod 71] * [144 mod 71] mod 71= 31 * 2 mod 71= 62 mod 71 = 62

NOW, to the next problem...
Can someone help me understand how this works....
-55 mod 7= 1 ?!?!?! what the hell

6. Originally Posted by matthayzon89
Can someone help me understand how this works....
-55 mod 7 = 1 ?!?!?!
Well, -55 is indeed congruent to 1 (modulo 7). Consider: 8 is congruent to 1 (modulo 7). If you subtract 1 from 8, you get 7, which is perfectly divisible by 7. Likewise, if you subtract 1 from -55, you get -56, which is perfectly divisible by 7. That said, since you are probably really testing for a remainder operation here, don't be surprised if the results are different, as was pointed out to you earlier in this thread.

7. The way mod works in practice is the same whether the numerator is positive or negative.
It's the intermediate division that's confusing because it rounds towards zero when division is done in isolation, yet appears to round towards left within the mod operation.

Finding how many times the denominator divides:
-55 / 7 = -8 (rounding in the left direction on the number line)
Finding remainder:
-55 - (7 * -8) = 1