Smallest positive number to trigger carry out

Question

I'm following a course on Computer Architecture and I have the following exercise:

What is the smallest positive decimal number that should be added to -20 so that a carry-out is triggered (in 2 complement's notation)?

I solved this exercise, but I'm not sure of my results. So I found this:

First convert -20 to 2 complements binary notation. This gives -20 = 11101100. Now add 000101000 to trigger a carry out. Which is equivalent to 20.

Would that be correct?

Answer 1

Yes! That is correct!

Adding -20 to 20 will give you 0 as a result with a carry-out 1. If you choose any positive number smaller than 20 it won't generate a carry-out and the result will be a negative number. If you choose any positive number larger than 20 it will generate a carry-out with a positive result. So 20 is the answer you are looking for.

If you really want to go into the binary detail, you can go step-by-step:

1. We are looking for a number that will be added to -20 and will generate a carry-out, let's represent it with x, y will be the result and c will be the carry-out.

      11101100
    + xxxxxxxx
      --------
     cyyyyyyyy

2. We are looking for c = 1 and we know that X is positive so its most significant bit is 0

      11101100
    + 0xxxxxxx
      --------
     1yyyyyyyy

3. Now we can clearly see that the only way that we can get a carry-out from bit 7 is by getting a carry-in from bit 6. So y[6] = 0.

      11101100
    + 0xxxxxxx
      --------
     10yyyyyyy

4. There are two ways we can generate a carry on bit 6. Either x[6] is one. Or there was a carry-in from bit 5. We want to minimize x, so we should choose x = 0 with a carry-in from bit 5.

      11101100
    + 00xxxxxx
      --------
     10yyyyyyy

5. The same applies to bit 5. We can choose between x[5] = 1 or a carry-in from bit 4. We should go for carry-in from bit 4, since we have to minimize x.

      11101100
    + 000xxxxx
      --------
     10yyyyyyy

6. Now we don't have any other option other than set x[4] = 1 because if x[4] = 0 there will be no carry being propagated to higher bits.

      11101100
    + 0001xxxx
      --------
     10yyyyyyy

7. And we are back on the same as 4. x[3] = 0 to minimize x.

      11101100
    + 00010xxx
      --------
     10yyyyyyy

8. Finally we got to the last 1 on the operand. It is our last chance to generate a carry. If we choose x = 0 there will be no carry out. Our only option is x = 1.

      11101100
    + 000101xx
      --------
     10yyyyyyy

9. Last two bits of x should be 0, because once again we are minimizing x.

      11101100
    + 00010100
      --------
     10yyyyyyy

10. And the result is... (with carry indicated)

      11111
      11101100
    + 00010100
      --------
     100000000

Ta-da!