user
Task

"*Simulate*" a four-bit adder.

This design can be realized using four 1-bit full adders.
Each of these 1-bit full adders can be built with two half adders and an   *or*   gate. ;

Finally a half adder can be made using an   *xor*   gate and an   *and*   gate.

The   *xor*   gate can be made using two   *not*s,   two   *and*s   and one   *or*.

**Not**,   **or**   and   **and**,   the only allowed "gates" for the task, can be "imitated" by using the bitwise operators of your language.

If there is not a *bit type* in your language, to be sure that the   *not*   does not "invert" all the other bits of the basic type   (e.g. a byte)   we are not interested in,   you can use an extra   *nand*   (*and*   then   *not*)   with the constant   **1**   on one input.

Instead of optimizing and reducing the number of gates used for the final 4-bit adder,   build it in the most straightforward way,   *connecting* the other "constructive blocks",   in turn made of "simpler" and "smaller" ones.

Schematics of the "constructive blocks"

| (Xor gate with ANDs, ORs and NOTs) | (A half adder) | (A full adder) | (A 4-bit adder) |
| --- | --- | --- | --- |
|  |  |  |  |

Solutions should try to be as descriptive as possible, making it as easy as possible to identify "connections" between higher-order "blocks".

It is not mandatory to replicate the syntax of higher-order blocks in the atomic "gate" blocks, i.e. basic "gate" operations can be performed as usual bitwise operations, or they can be "wrapped" in a *block* in order to expose the same syntax of higher-order blocks, at implementers' choice.

To test the implementation, show the sum of two four-bit numbers (in binary).
assistant
(formerly Perl 6)

```
sub xor ($a, $b) { (($a and not $b) or (not $a and $b)) ?? 1 !! 0 }

sub half-adder ($a, $b) {
    return xor($a, $b), ($a and $b);
}

sub full-adder ($a, $b, $c0) {
    my ($ha0_s, $ha0_c) = half-adder($c0, $a);
    my ($ha1_s, $ha1_c) = half-adder($ha0_s, $b);
    return $ha1_s, ($ha0_c or $ha1_c);
}

sub four-bit-adder ($a0, $a1, $a2, $a3, $b0, $b1, $b2, $b3) {
    my ($fa0_s, $fa0_c) = full-adder($a0, $b0, 0);
    my ($fa1_s, $fa1_c) = full-adder($a1, $b1, $fa0_c);
    my ($fa2_s, $fa2_c) = full-adder($a2, $b2, $fa1_c);
    my ($fa3_s, $fa3_c) = full-adder($a3, $b3, $fa2_c);

    return $fa0_s, $fa1_s, $fa2_s, $fa3_s, $fa3_c;
}

{
    use Test;

    is four-bit-adder(1, 0, 0, 0, 1, 0, 0, 0), (0, 1, 0, 0, 0), '1 + 1 == 2';
    is four-bit-adder(1, 0, 1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0), '5 + 5 == 10';
    is four-bit-adder(1, 0, 0, 1, 1, 1, 1, 0)[4], 1, '7 + 9 == overflow';
}

```

Output:

```
ok 1 - 1 + 1 == 2
ok 2 - 5 + 5 == 10
ok 3 - 7 + 9 == overflow
```