Making Logic Gates in JavaScript

Everyone knows that computer programs are made of bits - the ones and zeros that hold all the information that keeps our modern life running.

But how do you get from numbers to programs - how simple ones and zeros do anything?

The answer is logic gates (as well as a whole bunch of stuff about how electronics are built - you need to actually make these logic gates on out of circuits in order for our logic structures to be enacted; but I'm a programmer, not an electrical engineer, so let's not go there).  A logic gate is what's known as a Boolean function, a mathematical operation that takes in bits and spits out more bits.

Each logic gate takes in two bits of information (as mentioned before, generally denoted as a 1 (also sometimes represented as true) or a zero (also sometimes represented as false)), so there are four possible inputs to a logic gate: {0, 0}, {0, 1}, {1, 0}, and {1, 1}.  For each of these inputs, a logic gate can spit out either a 1 or a 0, so there are 2^4 possible output combinations.  However, since {0, 1} and {1, 0} are regarded as equivalent, this gives us 2^3 possible output combinations, of which we ignore the always-true combination and the always-false combination, giving us six possible logic gates:




Our regular logic gates are AND, OR, and XOR, and each of these has a corresponding negated form - NAND stands for "NOT-AND".

AND and NAND

And is easy as it conforms to our regular usage of the word "and".  If we have two statements and we link them together in a sentence with an "and", the sentence will be true if and only if both of the statements are true.  "Pizza is delicious and hamburgers are delicious" is a true sentence, but "Pizza is delicious and hamburgers are not delicious" is a false sentence.  Hence, the AND logic gate gives a true output when both of the inputs are true and false either of them are false.  The NAND gate is the opposite and gives a false output when both inputs are true and true when both are false.

Here's a simple implementation of AND and NAND in JavaScript. Note that we can take advantage of the fact that 0 is false in JavaScript and use 1s and 0s as inputs.  Also note that for NAND, we can either simply negate the return from AND, or we can simply state the input conditions required.

unction AND(a, b) {
return a && b ? true : false
}

console.log(AND(false, false))
//outputs false
console.log(AND(false, true))
//outputs false
console.log(AND(true, false))
//outputs false
console.log(AND(true, true))
//outputs true
console.log(AND(0,0))
//outputs false
console.log(AND(0,1))
//outputs false
console.log(AND(1,0))
//outputs false
console.log(AND(1,1))
//outputs true

function NAND(a, b) {
return !AND(a, b)
}

console.log('=====')
console.log(NAND(false, false))
//outputs true
console.log(NAND(false, true))
//outputs true
console.log(NAND(true, false))
//outputs true
console.log(NAND(true, true))
//outputs false
console.log(NAND(0,0))
//outputs true
console.log(NAND(0,1))
//outputs true
console.log(NAND(1,0))
//outputs true
console.log(NAND(1,1))
//outputs false

function NAND2(a, b) {
    return !(a && b) ? false : true
}

console.log('=====')
console.log(NAND2(false, false))
//outputs true
console.log(NAND2(false, true))
//outputs true
console.log(NAND2(true, false))
//outputs true
console.log(NAND2(true, true))
//outputs false
console.log(NAND2(0,0))
//outputs true
console.log(NAND2(0,1))
//outputs true
console.log(NAND2(1,0))
//outputs true
console.log(NAND2(1,1))
//outputs false

OR

The word "or" is tricky.  Sometimes, when we say "or", we mean one or the other, as in "You can go left or you can go right."  Sometimes, we mean "either one or both", as in "You can have cheese or bacon on your burger."  The logic gate OR corresponds to the "either or both" meaning.  So, the OR gate gives a true output when one or both of the input values are true, and false when neither of the inputs are true.  Correspondingly, the NOR gate only gives a true output when both inputs are false, and gives true the rest of the time.

function OR(a, b) {
return a || b ? true : false
}

function NOR(a, b) {
return !OR(a, b)
}

function NOR2(a, b) {
return !(a || b) ? true : false
}

XOR

XOR covers the other meaning of "or", where only one of the given options can be true.  The XOR gate outputs true if and only if one of the inputs is true, and outputs false both for the case of two true inputs and two false inputs.  XNOR reverses this.

I've covered the XOR bitwise operation before, and you might notice that it works the same way as the XOR gate.  Convenient!

function XOR(a, b) {
return a^b ? true : false
}

function XNOR(a, b) {
return !XOR(a, b)
}

function XNOR2(a, b) {
return !(a^b) ? true : false
}

What's fun about all these functions, since they both input and output booleans, you can call them upon themselves:

console.log(AND(AND(1,1), AND(1,1)))
//outputs true
console.log(OR(AND(0,1), AND(1,1)))
//outputs true
console.log(XOR(AND(0,0), OR(1,0)))
//outputs true

Furthermore, the NOR and NAND gates are what's known as universal gates - you can emulate the other gates using just NOR or just NAND.  So we can use our JavaScript NOR gate to re-make our other gates:

function ANDfromNOR(a,b) {
return NOR(NOR(a,a), NOR(b,b))
}

function NANDfromNOR(a,b) {
return NOR(
NOR(NOR(a,a), NOR(b,b)),
NOR(NOR(a,a), NOR(b,b))
)
}

function ORfromNOR(a,b) {
return NOR((NOR(a,b), NOR(a,b)))
}

function XORfromNOR(a,b) {
return NOR(
NOR(NOR(a,a), NOR(b,b)),
NOR(a,b)
)
}

function XNORfromNOR(a,b) {
return NOR(
NOR(a, NOR(a,b)),
NOR(b, NOR(a,b))
)
}

You can even make a NOR gate out of your NOR gates:

function NORfromNOR(a,b) {
return NOR(
NOR((NOR(a,b), NOR(a,b))),
NOR((NOR(a,b), NOR(a,b)))
)
}

A similar thing can be done in NAND:

function ANDfromNAND(a,b) {
return NAND(NAND(a,b), NAND(a,b))
}

function ORfromNAND(a,b) {
return NAND(NAND(a,a), NAND(b,b))
}

function NORfromNAND(a,b) {
return NAND(
NAND(NAND(a,a),NAND(b,b)),
NAND(NAND(a,a),NAND(b,b))
)
}

function XORfromNAND(a,b) {
return NAND(
NAND(a, NAND(a,b)),
NAND(b, NAND(a,b))
)
}

function XNORfromNAND(a,b) {
return NAND(
NAND(NAND(a,a), NAND(b,b)),
NAND(a,b)
)
}

And NAND can reproduce itself as well:

function NANDfromNAND(a,b) {
return NAND(NAND(a,a), NAND(b,b))
}

And, finally, this whole thing can eat its tail: since NAND can make NOR, and NOR can make anything else, we can make NAND from NOR from NAND:

function NANDfromNORfromNAND(a,b) {
return NORfromNAND(
NORfromNAND(NORfromNAND(a,a), NORfromNAND(b,b)),
NORfromNAND(NORfromNAND(a,a), NORfromNAND(b,b))
)
}


Ta-da!

Comments

Post a Comment

Popular posts from this blog

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...
Read more

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...
Read more