Adding Addition to JS
Tags: js binary post computer-architecture
Click here to see an interactive version of the 16-bit adder we develop below.
Today we’re going to be adding addition to JavaScript. Now I know what you’re thinking, I can just do this:
1+1
// 2Math in JS already works perfectly fine, but it’s hiding so many details from you! Underneath, deep within the circuitry of your computer, binary numbers are powering your machine. The truth is JavaScript numbers aren’t just decimal numbers, as it seems on the surface. It’s actually being represented as “64-bit floating point numbers” and you can read more about how they’re encoded here. So that’s great and all, but what does that actually mean? If I were to go into the hardware, how could that look like? Well today, we’re going to use JavaScript to describe how your hardware could theoretically manipulate 16-bit numbers, that means anything from 0 to about 65,356. That’s a far cry from 9007199254740991 which is the highest number JavaScript can represent safely. Still this is going to give you a great view as to how addition works and show you how far just a little bit of logic can go.
Our basic logic gates
Your device is made up of a series of different “gates”. These gates take 0s and 1s as inputs, binary numbers, which they manipulate. This is one of the lowest levels of abstraction you can get to without working with individual transistors. We will use the logic behind binary addition, which is addition involving binary numbers, to build a very simple adder that will take two 16-bit numbers and add them together. Let me be your guide you to a world where all that exists is 1s and 0s.
To begin, we need three gates: an Or, Xor and an And gate. These basic units work on simple principles. Theoretically, you can start building an entire computer from one gate (as they do in the Nand2Tetris course which I highly recommend) or use different gates as your starting point, but I’d like to start with these three that way we can really focus on the logic behind this addition.
An Or gate will return the highest of two values (either a 1 or a 0). The table below shows the different values it’ll return. The Or gate will return the “Out” value if you give it the A and B values as input. Representing the values of a gate in this way is known as a “truth table”.
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Or gate truth table
In an Xor gate (“exclusive” Or), it’ll pick the highest value given the two inputs (either 0 or 1), EXCEPT if it’s given two 1s in which case it’ll output a 0. This exception is what differentiates it from a regular Or gate, where the highest value is always chosen.
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Xor gate truth table
Next, here’s the truth table for an And gate.
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
And gate truth table
An And gate will give you the output of 1 only if both input values are 1, if not it’ll return 0.
As crazy as it seems, with just those three building blocks we can start adding numbers together!
To kick things off, let’s implement our lovely Xor gate with JavaScript. Remembering that our Xor gate will always return the highest value EXCEPT when 1 and 1 be are given as inputs. In that case the result is 0. We can build this gate using some if statements.
function xor(a, b){
if(a == 0 && b == 0){
return 0;
}
if(a == 0 && b == 1){
return 1;
}
if(a == 1 && b == 0){
return 1;
}
if(a == 1 && b == 1){
return 0;
}
}I’m sure you could simplify this gate further (and feel free to do so!), but I like this representation because it clearly shows what happens in each scenario.
After that, we can create our Or gate! This will always return the highest value.
function or(a, b){
if(a == 1 || b == 1){
return 1;
} else {
return 0;
}
}Next, we can create our And gate. As a quick reminder, this will return 1 only if both inputs are 1, in every other scenario it’ll return 0.
function and(a, b){
if(a == 1 && b == 1){
return 1;
} else {
return 0;
}
}With our three elementary gates complete we can now build a half-adder!
Half Adder
All the half-adder does is adds one bit to another bit. Before we begin, let’s do a quick overview of how binary addition works.
A decimal number, the type that you’re used to working with, can be split into different parts using a place value chart. We know that the number “111” can really be broken down into:
| Hundreds (10^2) | Tens (10^1) | Units(1^0) |
|---|---|---|
| 1 | 1 | 1 |
What that means is that 111 is really 100 + 10 + 1. Since decimal is based around the number 10, each part of its place value chart becomes 10 to the power of an exponent, starting with zero and going up by one each time.
Binary numbers work the same way! Except instead of each column being 10 to the exponent, it’s always 2 to the exponent. Here’s how we could represent the same value 111, in binary:
| Sixty-fours (2^6) | Thirty-twos (2^5) | Sixteens (2^4) | Eights (2^3) | Fours (2^2) | Twos (2^1) | Units (2^0) |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
What that means is that 111 in binary is really 1101111 or 64+32+8+4+2+1. As you can see, representing numbers in binary requires a bit more effort, but uses the same principles that you used to break down decimal numbers.
With that, we’re ready to move on to binary addition! Just like in regular addition, you need to carry numbers. Let’s see an example, what happens when we add 2 to 99 in decimal?
I represented the carried numbers as underlined. In this scenario, first we add 2 to 9 and carry the 1. Then we add 1 to 9 which results in additional 1 that needs to get carried. This results in our answer of 101.
To add 1 bit to another you use the same principles! 1 + 0 results in a sum of 1 and a carry of 0. 1 + 1 results in a sum of 0 and a carry of 1 (as the whole result is carried over, just like when you add 9 + 1, you get a 0 and a carry of 1!)
With that lesson over, we’re ready to build our half-adder, which again, adds 1 bit to another! Before we begin let’s think back to the gates we just built. How can we use them to get the results we see above? Our sum should only be a 1 if it’s inputs are a 0 and a 1 (in any order), and our carry should be 1 only if both inputs are 1. Wait a second, that perfectly matches with the truth tables of our Xor and And gates respectively! An Xor gate will return 1 only if it’s inputs are 0 and 1, which perfectly fits the expected result for the sum. Plus, since our And gate will return 1 only if both of its inputs are 1 then it can perfectly represent the carry!
Now we’re ready to write some code! Since JavaScript doesn’t allow you to return two values from one function, we’ll return an object with sum and carry values.
Here’s the code to represent our half-adder:
function halfadder(a, b){
var sum = xor(a,b)
var carry = and(a,b)
return {
sum: sum,
carry: carry
}
}Full Adder
You may be wondering why this component is called a “half-adder”, that’s because our “full-adder” comes next! A “full-adder” allows you to input 3 different bits, and is made up of two half-adders as well as an Or gate!
function fulladder(a,b, c){
var basicSumCarry = halfadder(a,b);
var sumAndLastCarry = halfadder(basicSumCarry.sum, c);
var carry = or(a=basicSumCarry.carry, sumAndLastCarry.carry);
return {
sum: sumAndLastCarry.sum,
carry: carry
}
}Let’s break this down. First, we add our first two bits. Then we take the sum of those first two bits and add it to the last bit. This is what allows us to add all the bits together.
var basicSumCarry = halfadder(a,b);
var sumAndLastCarry = halfadder(basicSumCarry.sum, c);What about our carries? We take care of that in the next line. We use the Or gate to mean that if either the first sum or the second sum has a carry then we should have a carry for this calculation.
var carry = or(a=basicSumCarry.carry, sumAndLastCarry.carry);You may be wondering, well aren’t we losing data if both sums have carries? Well the beauty of the full-adder is that no matter what we can’t have two carries. So we just want to make sure that if there is one we’re passing it on.
The return statement of the function matches the one from our half-adder so that means we’re done breaking it down!
The big difference to understand between a half-adder and a full-adder is that the half-adder could never represent something with a sum and a carry of 1. Without that, numbers greater than a bit would be impossible. By allowing this extra input field, we can keep the carry and keep passing it on, which you’ll see in our final component coming up which adds 16-bit numbers together!
We’ve finally come to the point where we can construct our 16-bit number adder! Here’s what it looks like:
function add16(a,b){
var out = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
var firstCalc = fulladder(a[15], b[15], 0);
out[15] = firstCalc.sum
var secondCalc = fulladder(a[14], b[14], firstCalc.carry);
out[14] = secondCalc.sum
var thirdCalc = fulladder(a[13], b[13], secondCalc.carry);
out[13] = thirdCalc.sum
var fourthCalc = fulladder(a[12], b[12], thirdCalc.carry);
out[12] = fourthCalc.sum
var fifthCalc = fulladder(a[11], b[11], fourthCalc.carry);
out[11] = fifthCalc.sum
var sixthCalc = fulladder(a[10], b[10], fifthCalc.carry);
out[10] = sixthCalc.sum
var seventhCalc = fulladder(a[9],b[9], sixthCalc.carry);
out[9] = seventhCalc.sum
var eighthCalc = fulladder(a[8], b[8], seventhCalc.carry);
out[8] = eighthCalc.sum
var ninthCalc = fulladder(a[7], b[7], eighthCalc.carry);
out[7] = ninthCalc.sum
var tenthCalc = fulladder(a[6], b[6], ninthCalc.carry);
out[6] = tenthCalc.sum
var eleventhCalc = fulladder(a[5], b[5], tenthCalc.carry);
out[5] = eleventhCalc.sum
var twelthCalc = fulladder(a[4], b[4], eleventhCalc.carry);
out[4] = eleventhCalc.sum
var thirteenthCalc = fulladder(a[3], b[3], twelthCalc.carry);
out[3] = thirteenthCalc.sum
var fourteenthCalc = fulladder(a[2], b[2], thirteenthCalc.carry);
out[2] = fourteenthCalc.sum
var fifteenthCalc = fulladder(a[1], b[1], fourteenthCalc.carry);
out[1] = fifteenthCalc.sum
// last carry ignored
var sixteenthCalc = fulladder(a[0], b[0], fifteenthCalc.carry);
out[0] = sixteenthCalc.sum
return out
}Like I explained at the start, the code isn’t as clean or even as efficient as it could be because I want to show you exactly what happens in each scenario. Our 16-bit adder uses a full-adder to input each bit, and then uses the last argument to input the carry. Since there’s no carry after the first bit calculation, the last argument given to the full-adder is 0. After that, all of them take the carry from the previous calculation. The final carry is ignored as it should always be 0, unless you are adding two numbers together that give a result that can’t be represented with 16-bits. In that scenario, the result would “overflow” and an incorrect result would be given. Nonetheless, our 16-bit adder works perfectly for adding 16-bit numbers.
If you want to pass in two binary numbers to the function, be sure to split them into arrays and then join the output. The follow snippet will add 10 and 5 together and print their sum:
var five = "0000000000000101".split("") // 0000000000000101 is 2^2 + 2^0 which equals 5
var ten = "0000000000001010".split("") // 0000000000001010 is 2^3 + 2^1 which equals 10
var sum = add16(five, ten).join("")
console.log(sum)With that, our work is complete! Congrats! You’ve added addition to JavaScript and now have a greater understanding of how binary numbers can represent that! If you’re interested in doing more research, feel free to look up the term “ripple-carry adder”. This is the type of adder we implemented today, but it isn’t the only option. It’s actually incredibly inefficent, but I’ll leave it up to you to learn more. Until next time!
P.S. Our 16-bit adder can add negative numbers too!
Okay so this is a bit more complicated than the rest so that’s why I’ve separated it. Our 16-bit adder can, in fact, add negative numbers too, but only if we can accept the fact that we’re going to be able to represent less positive numbers then before.
If we use the leftmost bit to check whether something is positive or negative then we can add negative numbers using something known as “two’s complement”. With this system the highest positive number we can represent is 32,767 with 16-bits. By reserving this bit to represent the sign we’ve made these numbers “signed integers”. Before they were “unsigned integers” as they did not have a bit to represent the sign, meaning they were always positive.
Let’s accept the following premise, if the first bit is a 0 then it’s positive, if it’s 1 it’s negative. There’s good reasons as to why this is one of the best ways to represent positive and negative numbers and it’s currently the main way to do so. Anyways, if we can accept this premise we can use “two’s complement”. The easiest way to do this is with an example.
-2’s “two’s complement” in this system is 1111111111111110, 10 is represented as 0000000000001010 as we’d expect. If we add these two numbers using our 16-bit adder we get 0000000000001000 which represents 8 in binary. That’s pretty cool right?
How does this work? To get a negative number, all you need is to take the positive number’s form, and convert all the 0s to 1 and all the 1s to 0s. Then you add 1 to this new result and you get a negative number! Let’s do this using 2 as that’s the number we added above. Positive two in binary can be represented as 0000000000000010. Inverting the numbers we then get 1111111111111101, now if we remember 1+1 in binary results in a sum of 0 and a carry of 1. So the rightmost digit becomes 0 and the one next to it gets the 1 carried to it. Since the next digit is 0, that one remains. This results in 1111111111111110 which is the same as the number above!
After that it’s as simple as adding two numbers together! Congrats again, you’ve created a system that not only adds positive integers together, but negative ones too! That’s the incredible power of two’s complement.