### 2019-04-14

**Adding numbers using Boolean operations in JavaScript**

* javascript, microprocessors*

* javascript, microprocessors*

*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.

AND & XOR

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

Adding one bit numbers

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.

Half-adder

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.

- "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.

Result of 11 + 01 => 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.