# Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image below).I mean C1 comes from the frist block and I dont provide it. And this mean I can only choose the first bit of C0. So it does not add 3 integers, right?

2)Is it possible to get the sum of k n-bit integers with full adder circuit?

• Just use $W+X+Y+Z=((W+X)+Y)+Z$ to compute the sum? – kennytm May 14 '16 at 14:20

It seems you have almost invented the carry-save adder.

You can use independent full adders for several layer, each time reducing 3 wires of equal weight to 1 wire of that weight and 1 for the next higher weight. Of course if there are 6 wires of the same weight, you can reduce them to 2 of the same weight and 2 of the next higher weight, and so on.

But the result of doing a bunch of that is not the sum, but two partial sums, one coming from all the S outputs of the last layer and one coming from all the C outputs. They still have to be added normally. You can use a ripple-carry adder or something faster/bigger there like a Kogge-Stone adder (which you'd only need once, compared to n-1 times if you just added up everything the obvious way).

1) That is correct. Even if you could mux the carry bits to be set to the bits of a third input, your adder would produce incorrect results. The carry is necessary to compute the addition of the two inputs, A and B. Try doing addition the elementary school way and ignore the numbers you carry over (or even better, set the carried over numbers to a third operand's digits). It wouldn't make sense.

2) Of course. This is also mentioned by @kennytm

The simplest way is to replicate and cascade the adder you have shown in your question such that the sum of one adder is one input operand of the next. The other operand is the next n-bit input.

To add k n-bit numbers, you would require k-1 two (n-bit) input adders. The input of the mth adder would be the sum from the m-1th adder and the m+1th number, for all m except m=1.

To add three n bit numbers, there is a simple method.

Take n one-bit full adders. Each full adder takes one bit of each of the three numbers as input, and generates a sum and a carry.

You create one n+1 number by shifting all the carrys one position to the left and filling with a zero, and one n+1 number by taking all the sums and adding a zero bit. Now you just have two n+1 bit adders to add.

Full-adder 0: x0, y0, z0 -> s0, c0

Full-adder 1: x1, y1, z1 -> s1, c1

Full-adder n-1: x(n-1), y(n-1), z(n-1) -> s(n-1), c(n-1)

Now add (0, s(n-1), s(n-2), ..., s2, s1, s0) and (c(n-1), c(n-2), ..., c1, c0, 0).

You use the same principle to add k numbers quickly: For every 3 n-bit numbers, you use a line of full adders to create two n+1 bit numbers. For example, given k = 10 numbers, you use three lines of full numbers to reduce this to 7 numbers (by turning three times 3 numbers into three times 2 numbers), then reduce 7 to 5, 5 to 4, 4 to 3, and 3 to 2. And then comes your n-bit adder.

The same principle can be used at a massive scale to build a 64 x 64 bit multiplier: You multiply a 64 bit number by 1 bit using 64 AND gates. Now you have 64 64-bit numbers to add. A massive number of full adders converts 21 sums of 3 numbers into 42 numbers and so on.