3
\$\begingroup\$

(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).

this 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.

\$\endgroup\$
12
  • 1
    \$\begingroup\$ you don't define \$s_n\$, so it's hard to answer 1. \$\endgroup\$ Dec 10, 2023 at 19:46
  • \$\begingroup\$ Sorry, about that. I am using what I thought was the conventional notation that \$s\$ is a bit vector representing \$s_n...s_0\$. Hopefully that clears it up? @MarcusMüller \$\endgroup\$
    – EE18
    Dec 10, 2023 at 20:01
  • 1
    \$\begingroup\$ What does the "↓" mean? \$\endgroup\$ Dec 10, 2023 at 20:52
  • \$\begingroup\$ Deleted and replaced with 0s. That was because the original context was multiplication. Thank you for pointing that out and sorry for the error @SpehroPefhany \$\endgroup\$
    – EE18
    Dec 10, 2023 at 22:52
  • \$\begingroup\$ @EE18 Name each full-adder as \$\small\small\sum_i\$ with inputs \$a_i\$, \$b_i\$, and \$ci_i\$ and outputs \$s_i\$ and \$co_i\$, for \$0 \le i\le n-1\$, then observe \$v=co_{n-2} \oplus co_{n-1}\$. If \$v=0\$ then you can discard \$co_{n-1}\$ and take \$s_{n-1}\dots s_0\$ (and sign extend it, if desired.) If \$v=1\$ then you must take \$co_{n-1}\$ as an extended bit and widening the result before sign extension would be valid. Here then, only \$n\$ \$\small\small\sum\$ are needed. Without the XOR you need \$n+1\$ \$\small\small\sum\$. \$\endgroup\$ Dec 11, 2023 at 0:26

2 Answers 2

1
\$\begingroup\$

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)

\$\endgroup\$
7
  • \$\begingroup\$ "If I interpret your nomenclature correctly, the n+1'th bit of the result equals the carry from the nth adder, yes." I guess this is what I'm asking about. I think doing this in case (1) works but per my linked question, doing this in case (2) does not work (hence we need to sign-extend and then compute)? \$\endgroup\$
    – EE18
    Dec 10, 2023 at 20:19
  • \$\begingroup\$ You don't need to sign extend and then add, just add and use the carry as before. \$\endgroup\$ Dec 10, 2023 at 20:25
  • \$\begingroup\$ Perhaps I am misunderstanding then. In the linked question there is explicitly shown an example where sign extension is necessary right? \$\endgroup\$
    – EE18
    Dec 10, 2023 at 20:36
  • \$\begingroup\$ The linked question is related to multiplication. Can you provide an example where you are simply adding two n-bit numbers and it does not work? \$\endgroup\$ Dec 10, 2023 at 20:42
  • \$\begingroup\$ Done :) Please let me know if the edit helps clarify my issue \$\endgroup\$
    – EE18
    Dec 10, 2023 at 20:47
0
\$\begingroup\$

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.

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here


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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.