How many bits are needed to "fully capture" the addition of two binary integers?

Question

(This is all related to my trying to understand my question here.)

Let's consider the addition of two n-bit integers, \$x = x_{n-1}...x_0\$ and \$y\$. Let their sum be \$s\$.

---

For the addition of unsigned integers...

If I want to add two n-bit numbers, is it correct to say that I simply need to take the carry out \$c_{n}\$ and set \$s_n\$ as such, \$c_{n} = s_n\$?

---

For the addition of signed integers using 2's complement (does this matter?) representation...

If I want to add two n-bit numbers, is it correct to say that I have to sign-extend each of \$x,y\$ to n+1 bits and use an extra full-adder so that \$s_n\$ can be computed directly?

In particular, I am interested in knowing if I must include an extra full adder here. Or is there is something clever I could do to avoid this, while still capturing the sum of any two n-bit numbers.

---

Edit: In response to a query below, here is an example which shows that with signed numbers we must sign-extend and cannot simply just "use the carry out bit" from the last adder as we can with the unsigned case (see the accepted answer to my linked question):

The issue is that without sign extension, the "extra bit" that one might suggest keeping can be wrong. In the below, the extra 0 bit is wrong (if we were to keep it).

                     101011
                   + 000000
                   -------
                    0101011

One might ask why can't we just delete the extra bit if it might be wrong: after all, in the above we would get the correct 101011 output under this strategy. But of course that won't work in general (we know this on the general grounds that we need an n+1 bits to account for the addition of two n-bit numbers) and also by explicit example:

                     101011
                   + 100000
                   -------
                    1001011

Here ignoring the carry out of the final stage gives us the wrong answer again, 001011. Thus neither keeping nor excluding the final bit gives us the right answer in general, only sign extension will.

Edit2: Per a very helpful comment from @periblepsis, I think the "keep the carry out bit" method described above can be rescued at the cost of an extra couple gates (which of course hurts the benefit of not using an extra full adder in this method).

As per the schematics above it appears that we can basically keep the carry out bit if there is overflow or, if there is not, then we can sign extend from the final sum bit.

Answer 1

If I interpret your nomenclature correctly, the n+1'th bit of the result equals the carry from the nth adder, yes.

2's complement signed numbers are added with the exact same hardware as unsigned numbers of the same width. The difference is in the interpretation.

For example, if you have two 7 bit numbers 2's complement -1 and add to an 8-bit result:

7F + 7F = FE (which is -2 base 10 in 8 bit 2's complement)

That's the same as if you added unsigned 127 base 10 to 127 base 10 to get 254 base 10 (FE in hex)

Answer 2

For the addition of unsigned integers...

If I want to add two n-bit numbers, is it correct to say that I simply need to take the carry out \$c_n\$ and set \$s_n\$ as such, \$c_n = s_n\$?

Yes.

---

For the addition of signed integers using 2's complement (does this matter?) representation...

Yes, it does matter. If you use another representation then two's complement of a signed integer, you cannot use the same adder for unsigned and signed integers.

The reasoning is left as an exercise to the reader, or a new question because it is another issue.

---

For the addition of signed integers using 2's complement [...] representation...

If I want to add two n-bit numbers, is it correct to say that I have to sign-extend each of \$x,y\$ to n+1 bits [...]?

Yes, directly or indirectly. The sum needs n+1 bits in any case.

[...] and use an extra full-adder so that \$s_n\$ can be computed directly?

In particular, I am interested in knowing if I must include an extra full adder here. Or is there is something clever I could do to avoid this, while still capturing the sum of any two n-bit numbers.

No, your don't necessarily need a full adder. As your question's 2nd edit shows, you can minimize the logic.

---

I let Logisim build your alternatives with only NANDs of 2 inputs, which can be seen as the most basic building blocks. The layout was automatic, too. ;-)

Alternative 1 (XOR and MUX)

This is the XOR, built from 5 NANDs, 2 of which can be replaced by NOTs.

This is the MUX, built from 4 NANDs, 1 of which can be replaced by a NOT.

The total is 9 NANDs, three of which can be replaced by NOTs.

Alternative 2 (Full Adder)

This the full adder, built from 23 NANDs, 12 of which can be replaced by NOTs.

Circuit built from truth table

At last I let Logisim build this circuit with its integrated optimizing circuit analyzer as the combination of XOR and MUX. It is built from 8 NANDs, 3 of which can be replaced by NOTs.

---

Your conclusion is correct, a XOR and a MUX seems to be less logic than a full adder.

What enables the massive optimization? The inputs of the alternatives are different!

However, you will not build such a logic from discrete logic blocks. In the real world you will use:

• A ready-made multi-bit adder, which its designers optimized already.
• A programmable logic device (CPLD or FPGA) with the logic's description in an abstract hardware description language. The synthesizer software will optimize the logic. BTW, the internal building blocks can often be seen as LUT, quite similar to a small ROM.
• A processor, which uses optimized logic for its additions.

As a foot note and final line, the optimization part of this question is mostly academic. But we all love this stuff, don't we?