Algorithm For Binary Addition
I recently wrote an algorithm to perform binary addition for a project I have been working on called CS Conversions.
If you’re not familiar with what binary addition is and how it works I wrote about it here.
I had a lot of fun writing this algorithm and wanted to share my approach.
Right out of the gate we need to figure out a way to accommodate adding two numbers of different lengths.
Say we’re adding 101111 + 101010101.
We need to alter the shorter number to be 000101111, so when we add them they both have an equal number of place values.
I wrote a few helper functions to achieve this.
// finds the shorter input value
const theShorterValue = (input1, input2) => {
if (input1.length < input2.length) {
return input1
}
return input2
}
// finds the difference in length between two input values
const differenceInLength = (input1, input2) => {
return Math.abs(input1.length - input2.length)
}
// appends zeroes accordingly to the input value that is shorter
const appendZeroesToShorterValue = (input1, input2) => {
const lengthDifference = differenceInLength(input1, input2)
let shortest = theShorterValue(input1, input2)
for (let i = 0; i < lengthDifference; i++) {
shortest = '0' + shortest
}
return shortest
}
Now that we’re working with two numbers of the same length it’s time to code in the logic of how we would actually go about adding them.
In binary addition there are four cases we have to account for.
0 + 0 = 0
0 + 1 = 1
1 + 1 = 10 (value of 0 with a carry of 1)
1+ 1 = 11 (value of 1 with a carry of 1)
We need some kind of holding variable to keep track of the values we are currently adding.
Based on the four cases above we need to evaluate what we’re currently adding in that holding variable, and push that to a result variable which is recording all of our sums.
const addInputs = (num1, num2) => {
// counts the amount of 0s
let zeroCount = 0
// counts the amount of 1s
let oneCount = 0
// keeps track of operations as they happen
let cue = []
// holds result of operations
let result = []
// addition happens from right to left
num1 = [...num1].reverse()
num2 = [...num2].reverse()
for (let i = 0; i <= num1.length; i++) {
// push num1s value to the cue
cue.push(num1[i])
// push num2s value to the cue
cue.push(num2[i])
// the amount of 1s and 0's in the cue are counted
cue.forEach(i => {
i == '1' ? oneCount++ : zeroCount++
})
// the conditionals for the cue length being 2
if (cue.length == 2) {
if (oneCount == 2) {
result.unshift('0')
cue = []
cue.push('1')
} else if (oneCount == 1) {
result.unshift('1')
cue = []
} else if (zeroCount == 2 && i != num1.length) {
result.unshift('0')
cue = []
}
// reset one and zero counts
oneCount = 0
zeroCount = 0
// the conditionals for the cue having 3 items in it
} else if (cue.length == 3) {
if (zeroCount == 2) {
result.unshift('1')
cue = []
} else if (oneCount == 2) {
result.unshift('0')
cue = []
// in this instance we will carry a 1
cue.push('1')
} else if (oneCount == 3) {
result.unshift('1')
// reset the cue
cue = []
// in this case we will carry a 1
cue.push('1')
}
// reset one and zero counts
oneCount = 0
zeroCount = 0
}
}
return result.join('')
}
The duration of the for loop is determined by the number of place values in one of the binary numbers we’re adding. Remember that we made the the number of places values for the smaller number equal to the number of place values in the larger number by appending 0s to the front in the appendZeroesToShorterValue function. It does not matter which binary numbers length we chose because they’re both the same.
For each place value we loop over we take the values from both binary numbers we’re adding and store them in a variable called cue.
The number of 1s and 0s inside of cue is then counted.
Whether the cue contains 2 or 3 values will determine how we proceed evaluating the sum.
Based on the combination of 1s and 0s inside the cue I push a value to result, which is keeping track of all the sums, and then I update the cue to reflect whether or not their was a carry of 1.
This wraps up the mechanics of how the actual adding will work. Let’s tie everything together now.
// return true if the input lengths are equal false if they're not
const isEqualLength = (input1, input2) => {
return input1.length == input2.length
}
// finds the longer input value
const theLongerValue = (input1, input2) => {
if (input1.length > input2.length) {
return input1
}
return input2
}
// finds the shorter input value
const theShorterValue = (input1, input2) => {
if (input1.length < input2.length) {
return input1
}
return input2
}
// finds the difference in length between two input values
const differenceInLength = (input1, input2) => {
return Math.abs(input1.length - input2.length)
}
// appends zeroes accordingly to the input value that is shorter
const appendZeroesToShorterValue = (input1, input2) => {
const lengthDifference = differenceInLength(input1, input2)
let shortest = theShorterValue(input1, input2)
for (let i = 0; i < lengthDifference; i++) {
shortest = '0' + shortest
}
return shortest
}
const addInputs = (num1, num2) => {
// counts the amount of 0s
let zeroCount = 0
// counts the amount of 1s
let oneCount = 0
// keeps track of operations as they happen
let cue = []
// holds result of operations
let result = []
// addition happens from right to left
num1 = [...num1].reverse()
num2 = [...num2].reverse()
for (let i = 0; i <= num1.length; i++) {
// push num1s value to the cue
cue.push(num1[i])
// push num2s value to the cue
cue.push(num2[i])
// the amount of 1s and 0's in the cue are counted
cue.forEach(i => {
i == '1' ? oneCount++ : zeroCount++
})
// the conditionals for the cue length being 2
if (cue.length == 2) {
if (oneCount == 2) {
result.unshift('0')
cue = []
cue.push('1')
} else if (oneCount == 1) {
result.unshift('1')
cue = []
} else if (zeroCount == 2 && i != num1.length) {
result.unshift('0')
cue = []
}
// reset one and zero counts
oneCount = 0
zeroCount = 0
// the conditionals for the cue having 3 items in it
} else if (cue.length == 3) {
if (zeroCount == 2) {
result.unshift('1')
cue = []
} else if (oneCount == 2) {
result.unshift('0')
cue = []
// in this instance we will carry a 1
cue.push('1')
} else if (oneCount == 3) {
result.unshift('1')
// reset the cue
cue = []
// in this case we will carry a 1
cue.push('1')
}
// reset one and zero counts
oneCount = 0
zeroCount = 0
}
}
return result.join('')
}
// This is where everything comes together
const binaryAddition = (input1, input2) => {
// We need to check if the lengths of the strings we are adding are equal or not
// if they're unequal we will have to apply some additional logic to make them equal
if (isEqualLength(input1, input2)) {
// the inputs are equal in length so we can just add them as is
return addInputs(input1, input2)
} else {
// This just assigns the value that is longer to a variable
let num1 = theLongerValue(input1, input2)
// This takes the shorter value and append 0's until it's length is equal to the bigger input
let num2 = appendZeroesToShorterValue(input1, input2)
// return the results of the addition as the final answer
return addInputs(num1, num2)
}
}
In the binaryAddition function we check to see if the both binary numbers have the same amount of place values.
If they do we can simply run our addInputs function and not have to worry about appending any 0s.
If the binary numbers we’re adding have an unequal amount of place values then we have to use the theLongerValue and appendZeroesToShorterValue functions.
This will allow us to assign the larger binary number to a variable and append 0s to the shorter binary number.
Once this step is complete we can pass these two variables into the addInputs function and calculate the sum.
I made a tool to do binary addition and teach students how it works. Feel free to check it out here.
Thanks for reading!