You are given two arrays (with length 4) of Boolean values which correspond to a 4-bit unsigned integer. For each element at index \(n\), this corresponds to a bit in the \(2^{3-n}\) place. i.e. an input of [true, true, false, false] corresponds to the binary number \(1100_2\).

Write a function which performs addition on these two inputs and returns an array of Booleans corresponding to the binary representation of this result. For example: given inputs [false, true, false, true] (\(0101_2\), or \(5\)) and [false, false, false, true] (\(0001_{2}\), or \(1\)), the return value should be [false, true, true, false] (\(0110_2\), or \(6\)).

You must not utilise arithmetic operators (+, -, *, /)1, bitwise operators (<<, >>, &, |, ~), or the XOR operator (^). You may use Boolean logical operators (&&, ||, !) are allowed.

Your function must consider the potential for a carry bit. Given addition of two 4-bit inputs, a 5-bit output (or overflow) is possible. How this is handled is your choice, but the carry bit must be acknowledged in some way. Some options may include:

  1. Variable length return: Returning 4 bits or 5 bits depending on if there is a carry

  2. Fixed-length of 5 return: Always return 5 bits, and just set it true or false depending on the carry value

  3. Fixed-length of 4 return: Always return 4 bits, but wrap it in a tuple or object which contains both the sum and the carry

Any of these approaches are fine. The larger point is, don't discard the carry bit.

  1. You can, however, use + (or ++) and - (or --) to increment or decrement the index used to iterate over the Boolean arrays.↩

Solution

The operator restriction is in place because the challenge is intended to guide you toward recreating a full adder using Boolean algebra.

The first step is to recount how a half adder operates. We'll simplify things to just 1 bit for now. Let's write down the possible combinations:

  • \(0 + 0 = 00\).
  • \(0 + 1 = 01\)
  • \(1 + 0 = 01\)
  • \(1 + 1 = 10_2\)

We find that when we add \(1 + 1\), we get \(10_2\) (aka \(2\) in decimal). The addition resulted in a carry into the \(2^1\) place. Let's format this as a table:

\(A\) \(B\) \(2^1\) place \(2^0\) place
\(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(0\) \(1\)
\(1\) \(0\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\)

This is looking an awful lot like a truth table, isn't it? We can see here how the \(2^1\) place is simply the result of an AND \(\land\), and the \(2^0\) place is the result of an XOR \(\oplus\).

\(A\) \(B\) \(A \land B\) \(A \oplus B\)
\(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(0\) \(1\)
\(1\) \(0\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\)

However - this challenge restricts the usage of the XOR operation (which is written as ^ in most languages). In case you're unfamiliar with how XOR works, let's isolate that column to find out;

\(A\) \(B\) \(A \oplus B\)
\(0\) \(0\) \(0\)
\(0\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(1\) \(1\) \(0\)

The result of \(A \oplus B\) is \(1\), only if \(A\) and \(B\) are different. The mathematical way to notate this would be \((A \land \neg B) \lor (\neg A \land B)\). Alternatively, you could also use the != operator giving the expression A != B, which will also only return true when A and B differ. For the sake of keeping true to the mathematics, I'll using the former notation.

A full adder is achieved by chaining two half adders together. A complete addition, therefore, is simply a chain of full adders. This also means a full adder must account for an input carry signal. The solution I settled on in C# looks something like this:

bool[] A = [true, false, false, false];
bool[] B = [true, false, false, false];
Add(A, B).Dump();

bool AND(bool a, bool b) => a && b;
bool OR(bool a, bool b) => a || b;
bool NOT(bool a) => !a;
bool XOR(bool a, bool b) => OR(AND(a, NOT(b)), AND(NOT(a), b));

(bool Sum, bool Carry) HalfAdder(bool a, bool b) => (XOR(a, b), AND(a, b));
(bool Sum, bool Carry) FullAdder(bool a, bool b, bool carry)
{
    var first = HalfAdder(a, b);
    var second = HalfAdder(first.Sum, carry);
    return (second.Sum, OR(first.Carry, second.Carry));
}

bool[] Add(bool[] a, bool[] b)
{
    bool carry = false;
    var result = new bool[4];
    
    for (int i = 3; i >= 0; i--)
    {
        var add = FullAdder(a[i], b[i], carry);
        result[i] = add.Sum;
        carry = add.Carry;
    }

    if (carry)
    {
        result = [carry, ..result];
    }

    return result;
}