There are many cases where it is desired to add more than two numbers together. The straightforward way of adding together m numbers (all n bits wide) is to add the first two, then add that sum to the next, and so on. This requires a total of m − 1 additions, for a total gate delay of O(m lg n) (assuming lookahead carry adders). Instead, a tree of adders can be formed, taking only O(lg m · lg n) gate delays.

Using carry save addition, the delay can be reduced further still. The idea is to take 3 numbers that we want to add together, x + y + z, and convert it into 2 numbers c + s such that x + y + z = c + s, and do this in O(1) time. The reason why addition can not be performed in O(1) time is because the carry information must be propagated. In carry save addition, we refrain from directly passing on the carry information until the very last step. We will first illustrate the general concept with a base 10 example.

To add three numbers by hand, we typically align the three operands, and then proceed column by column in the same fashion that we perform addition with two numbers. The three digits in a row are added, and any overflow goes into the next column. Observe that when there is some non-zero carry, we are really adding four digits (the digits of x,y and z, plus the carry).

The carry save approach breaks this process down into two steps. The first is to compute the sum ignoring any carries:

Each si is equal to the sum of xi + yi + zi modulo 10. Now, separately, we can compute the carry on a column by column basis:

In this case, each ci is the sum of the bits from the previous column divided by 10 (ignoring any remainder). Another way to look at it is that any carry over from one column gets put into the next column. Now, we can add together c and s, and we’ll verify that it indeed is equal to x + y + z:

The carry save adder block is the same circuit as the full adder.

One CSA block is used for each bit. This circuit adds three n = 8 bit numbers together into two new numbers.

The important point is that c and s can be computed independently, and furthermore, each ci (and si) can be computed independently from all of the other c’s (and s’s). This achieves our original goal of converting three numbers that we wish to add into two numbers that add up to the same sum, and in O(1) time.

The same concept can be applied to binary numbers. As a quick example:

What does the circuit to compute s and c look like? It is actually identical to the full adder, but with some of the signals renamed. Figure 1 shows a full adder and a carry save adder. A carry save adder simply is a full adder with the cin input renamed to z, the z output (the original “answer” output) renamed to s, and the cout output renamed to c. Figure 2 shows how n carry save adders are arranged to add three n bit numbers x,y and z into two numbers c and s.

Note that the CSA block in bit position zero generates c1, not c0. Similar to the least significant column when adding numbers by hand (the “blank”), c0 is equal to zero. Note that all of the CSA blocks are independent, thus the entire circuit takes only O(1) time. To get the final sum, we still need a LCA, which will cost us O(lg n) delay. The asymptotic gate delay to add three n-bit numbers is thus the same as adding only two n-bit numbers.

So how long does it take us to add m different n-bit numbers together? The simple approach is just to repeat this trick approximately m times over. This is illustrated in Figure 3. There are m−2 CSA blocks (each block in the figure actually represents many one-bit CSA blocks in parallel) that we have to go through, and then the final LCA. Note that every time we pass through a CSA block, our number increases in size by one bit. Therefore, the numbers that go to the LCA will be at most n + m − 2 bits long. So the final LCA will have a gate delay of O(lg (n + m)). Therefore the total gate delay is O(m + lg (n + m)).