April 14, 2019

*Photo by **Crissy Jarvis** on **Unsplash*

You know how to add numbers progmatically, right? `1 + 1`

will basically give you 2.

Numbers are added in binary form down in machine level.

But how do numbers get added underneath the hood?

I will show how to add “positive” integers (no floating) using boolean operations.

I will assume the knowledge of binary numbers and Boolean operations.

And you can follow along on CodeSandbox.

Below is the truth table of all possible XOR & AND operations I will refer back to.

When you add two one-bit numbers, you get either 0 or 1 for the sum and 0 or 1 for the carry.

Did you notice that, `carry`

output looks the same as output of AND truth table, and sum equal to that of XOR?

The operation can be represented using logical XOR & AND gates as shown here.

A circuit formed that way is called half-adder.

Armed with the knowledge and we can now implement the addition using XOR & AND.

const xor = (a, b) => Boolean(a) !== Boolean(b); | |

const and = (a, b) => Boolean(a) && Boolean(b); | |

const toBit = predicate => (a, b) => (predicate(a, b) ? 1 : 0); | |

const xorBit = toBit(xor); | |

const andBit = toBit(and); | |

const halfAdder = (a, b) => ({ c: andBit(a, b), s: xorBit(a, b) }); |

`xor`

returns true (or 1) when both input are different.`and`

was used using built-in JavaScript`&&`

operator.`xorBit`

&`andBit`

return 1 or 0 depending on whether result is true or false.- Think of
`andBit`

as an AND gate and`xorBit`

as XOR gate in the Half-adder figure above.

- Think of
- “s” refers to “sum”, while “c” means “carry”.

When we run the half adder on combination of one bit addition, the result looks like below.

function addOneBit(v1, v2) { | |

return halfAdder(v1, v2); | |

} | |

[[0, 0], [0, 1], [1, 0], [1, 1]].map(v => | |

console.log(`addOneBit(${v[0]}, ${v[1]})`, addOneBit(v[0], v[1])) | |

); | |

// result | |

// addOneBit(0, 0) { c: 0, s: 0 } | |

// addOneBit(0, 1) { c: 0, s: 1 } | |

// addOneBit(1, 0) { c: 0, s: 1 } | |

// addOneBit(1, 1) { c: 1, s: 0 } |

OK, that wasn’t interesting enough as we can’t do anything by adding just one bit.

Let’s spice it up by adding two bits.

We got the carry from the half-adder but to calculate the next bit we need to pass the carry to the next adder.

But the problem is that, half-adder accepts only two inputs and doesn’t accept a carry.

We can solve the problem by combining two half-adders, making it a full-adder.

Logic looks like following.

- You calculate the first (least significant) bit using the half-adder and feed the carry from it to the full adder.
- The full adder will calculate the 2nd bit and then sum again in the half adder with the carry as the input
- Lastly, output carry of the full adder is the OR of carries from two-half adders in the full-adder.

Simply put, you perform two operations. One for the current bit, and another with the carry.

Let’s take a look at an example of adding 11 and 01 to get 100.

*I apologize for the 💩 illustration 😅.**And thank you **@MarkN_LP** for **catching the error**.*

The diagram shows the result of first carry being fed into the 2nd half-adder, which is used to calculate sum.

Let’s implement the full-adder & add two bit numbers.

const or = (a, b) => Boolean(a) || Boolean(b); | |

const orBit = toBit(or); | |

const fullAdder = (a, b, c = 0) => { | |

const first = halfAdder(a, b); | |

const second = halfAdder(first.s, c); | |

return { c: orBit(first.c, second.c), s: second.s }; | |

}; | |

function addTwoBits(a1, a2) { | |

// Note that we start with the index `1` here | |

// because we need to start from the right-most (least significant) bit. | |

// e.g.) given a1 = "01", we start from "1", not "0". | |

const { c: c0, s: b0 } = halfAdder(+a1[1], +a2[1]); | |

const { c: c1, s: b1 } = fullAdder(+a1[0], +a2[0], c0); | |

return { c1, b1, b0 }; | |

} | |

[ | |

["00", "10"], ["01", "00"], ["10", "00"], | |

["10", "01"], ["10", "10"], ["11", "00"], | |

["11", "01"], ["11", "10"], ["11", "11"] | |

].map(v => log(`addTwoBits(${v[0]}, ${v[1]})`, addTwoBits(v[0], v[1]))); | |

// result | |

// addTwoBits(00, 10) { c1: 0, b1: 1, b0: 0 } | |

// addTwoBits(01, 00) { c1: 0, b1: 0, b0: 1 } | |

// addTwoBits(10, 00) { c1: 0, b1: 1, b0: 0 } | |

// addTwoBits(10, 01) { c1: 0, b1: 1, b0: 1 } | |

// addTwoBits(10, 10) { c1: 1, b1: 0, b0: 0 } | |

// addTwoBits(11, 00) { c1: 0, b1: 1, b0: 1 } | |

// addTwoBits(11, 01) { c1: 1, b1: 0, b0: 0 } | |

// addTwoBits(11, 10) { c1: 1, b1: 0, b0: 1 } | |

// addTwoBits(11, 11) { c1: 1, b1: 1, b0: 0 } |

Full-adder is implemented in line#4~8 using newly created `orBit`

method to calculate the carry.

It uses two half-adders and uses the carry from the “first” operation in the second half-adder.

And the carry is the result of two carries in the two half-adders as shown in the diagram.

`11 + 01`

correctly returns `{ c1: 1, b1: 0, b0: 0 }`

.

Still useless right? Let’s add more bits.

When you add one bit, you need just a half-adder. For two bits, 1 half-adder & 1 full-adder.

For 3 bits, you would need 1 half-adder & 2 full-adders.

So for N-bit addition, you need 1 half-adder & N-1 full-adders.

I could’ve shown 3-bit operation but decided to share a method that works on any N-bits instead (unlike how microprocessors are physically constrained).

function addBits(v1, v2) { | |

const toNumberArray = str => str.split("").map(_ => +_); | |

const [a1, a2] = [toNumberArray(v1), toNumberArray(v2)]; | |

// Add bits from right (least significant bit) | |

// to left (most significant bit) | |

const sum = a1.reduceRight((acc, a, i) => { | |

const b = a2[i]; | |

// c => carry, s => sum | |

let [c, s] = [0, 0]; | |

// Calculate the first bit | |

if (i === a1.length - 1) { | |

({ c, s } = halfAdder(a, b)); | |

} else { | |

// Calculate the rest of the bits using the carry | |

const carry = (acc[0] && acc[0].c) || 0; | |

({ c, s } = fullAdder(a, b, carry)); | |

} | |

return [{ c, s }, ...acc]; | |

}, []); | |

// Build readable text | |

return sum.reduce( | |

(acc, { s, c }, i) => `${acc}${(i === 0 && c === 1 && "1") || ""}${s}`, | |

"" | |

); | |

} |

*This code assumes that length of two digits have the same length.**I initially was going to change the length dynamically but it made the demo code too convoluted so left it out.*

Line #2 & #3 converts strings into array of numbers

and #7 uses reduceRight to start working on the least significant (right-most) bit.

On first iteration, we calculate the sum using half-adder on line #14, and then we use the full-adder for the rest.

Carry passed to the full-adder is retrieved from the first item in the array because we are prepending new digit (`[{c, s}, ...acc]`

) on each iteration.

Lastly, we are returning a text representation of the sum for demo purpose only.

*Sorry about abusing **&&** there 😜.I got excited after reading “*

Let’s check out the demo result.

const toDec = binaryText => parseInt(binaryText, 2); | |

[ | |

["0", "0"], ["0", "1"], ["1", "0"], ["1", "1"], | |

["00", "10"], ["01", "00"], ["10", "00"], ["10", "01"], | |

["10", "10"], ["11", "00"], ["11", "01"], | |

["11", "10"], ["11", "11"], ["101", "001"], | |

["1111", "0011"], ["011111", "111111"], | |

["11011", "00001"], ["11111111", "00000001"] | |

].map(([a, b]) => | |

log(`${a} + ${b} = ${addBits(a, b)} (${toDec(a)} + ${toDec(b)} = ${toDec(addBits(a, b))})`) | |

); | |

// Result | |

// 0 + 0 = 0 (0 + 0 = 0) | |

// 0 + 1 = 1 (0 + 1 = 1) | |

// 1 + 0 = 1 (1 + 0 = 1) | |

// 1 + 1 = 10 (1 + 1 = 2) | |

// 00 + 10 = 10 (0 + 2 = 2) | |

// 01 + 00 = 01 (1 + 0 = 1) | |

// 10 + 00 = 10 (2 + 0 = 2) | |

// 10 + 01 = 11 (2 + 1 = 3) | |

// 10 + 10 = 100 (2 + 2 = 4) | |

// 11 + 00 = 11 (3 + 0 = 3) | |

// 11 + 01 = 100 (3 + 1 = 4) | |

// 11 + 10 = 101 (3 + 2 = 5) | |

// 11 + 11 = 110 (3 + 3 = 6) | |

// 101 + 001 = 110 (5 + 1 = 6) | |

// 1111 + 0011 = 10010 (15 + 3 = 18) | |

// 011111 + 111111 = 1011110 (31 + 63 = 94) | |

// 11011 + 00001 = 11100 (27 + 1 = 28) | |

// 11111111 + 00000001 = 100000000 (255 + 1 = 256) |

Values within parenthesis shows operations in base 10.

We’ve looked at how positive numbers are added under the hood.

I am also just learning about this thus the explanation might lack much.

The source I am learning from is “The Manga Guide to Microprocessors“.

*I still haven’t finished the book but it has been delightful. *

If you want to dig deeper, check out following resources.

- The Manga Guide to Microprocessors – No Starch Press
- Adder Wikipedia article
- Diagram & Truth tables for
- Demo program is available on CodeSandbox
- Full-adder diagram on Google Slides.
- Half-adder on Wikipedia.