In this article, let's build a 8-bit adder using only logic gates.
The first thing to do is to implement all the gates we need. Since these are just simple 0 and 1, we can just implement it directly.
type Bit = 0 | 1;
function not(x: Bit): Bit {
return x === 1 ? 0 : 1;
}
function and(x: Bit, y: Bit): Bit {
return x + y < 2 ? 0 : 1;
}
function or(x: Bit, y: Bit): Bit {
return x + y > 0 ? 1 : 0;
}
function nand(x: Bit, y: Bit) {
return not(and(x, y));
}
function xor(x: Bit, y: Bit) {
return x === y ? 0 : 1;
}
With all these logic gates, we can implment the half adder here. The input is just 2 bits and the output contains sum and carry. For example, the input can be 0
and 1
, so the calculation result should be 10
. Break it into 2 half, the left half we call it carry and the right half we call it sum. The carry actually the same carry we learned from elementary school.
/**
* add one bit
* 0 + 0 = 00
* 0 + 1 = 01
* 1 + 0 = 01
* 1 + 1 = 10
*
* so break it into two part:
* - sum: xor
* - carry: and
*/
type Sum = Bit;
type Carry = Bit;
type Result = {
sum: Bit;
carry: Bit;
};
function halfAdder(x: Bit, y: Bit): Result {
return { sum: xor(x, y), carry: and(x, y) };
}
As you can see from process, we can calculate the result directly from the logic gates. The sum is xor
of the inputs, the carry is the and
of the inputs. You can see that we call this function half adder because we are ignoring the carry previous calculation may give.
Now let's build the full adder, which has the ability to calculate inputs plus carry.
/**
*
* full adder
* x and y are input number
* carry is from previous calculation
*
* x y carry sum carry
* 0 0 0 = 0 0
* 0 1 0 = 1 0
* 1 0 0 = 1 0
* 1 1 0 = 0 1
* 0 0 1 = 1 0
* 0 1 1 = 0 1
* 1 0 1 = 0 1
* 1 1 1 = 1 1
*
*/
function fullAdder(x: Bit, y: Bit, carry: Bit): Result {
let out1 = halfAdder(x, y);
let out2 = halfAdder(out1.sum, carry);
return {
sum: out2.sum,
carry: or(out1.carry, out2.carry),
};
}
As you can see from above code comment, we list all the combinations of input bits and carry values. The final sum value can be calculated from two step half adder. The final carry value can be calculated from an or
operation between the carry from first half adder and the carry from second adder.
With this full adder, we can put it together and build a 8-bit adder.
function eightBitAdder(x: Bit[], y: Bit[]): Bit[] {
let sum: Bit;
let carry: Bit = 0;
let length = 8;
let result: Bit[] = Array.from({ length });
let bitIndex = length;
while (bitIndex-- > 0) {
({ sum, carry } = fullAdder(x[bitIndex], y[bitIndex], carry));
result[bitIndex] = sum;
}
return result;
}
As you can see from the code, we do a full adder operation from the least significant bit. For each calculation, we store the sum value into the result. After all full adder calculations we should get a result filled with right bit values.
Now let write 2 utility functions for helping test.
function number2Bits(n: number): Bit[] {
return n
.toString(2)
.padStart(8, "0")
.split("")
.map((c) => (c === "0" ? 0 : 1));
}
function bits2Number(bits: Bit[]): number {
return parseInt(bits.join(""), 2);
}
And finally, let do a simple test.
const x = 23;
const y = 49;
console.log(bits2Number(eightBitAdder(number2Bits(x), number2Bits(y))), x + y);
// 72 72
Works as expected.