Created
July 20, 2011 03:25
-
-
Save nfeldman/1094268 to your computer and use it in GitHub Desktop.
javascript 4-bit adder simulator written for Rosetta Code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* ************************************************ | |
* Rosetta Code: Four-Bit Adder Simulation | |
* http://rosettacode.org/wiki/Four_bit_adder | |
* ************************************************ | |
* The aim of this task is to "simulate" a four-bit adder "chip". This "chip" | |
* can be realized using four 1-bit full adders. Each of these 1-bit full | |
* adders can be with two half adders and an or gate. Finally a half adder can | |
* be made using a xor gate and an and gate. The xor gate can be made using two | |
* nots, two ands and one or. | |
* | |
* Not, or and and, the only allowed "gates" for the task, can be "imitated" by | |
* using the bitwise operators of your language. If there is not a bit type in | |
* your language, to be sure that the not does not "invert" all the other bits | |
* of the basic type (e.g. a byte) we are not interested in, you can use an | |
* extra nand (and then not) with the constant 1 on one input. | |
* | |
* Instead of optimizing and reducing the number of gates used for the final 4- | |
* bit adder, build it in the most straightforward way, connecting the other | |
* "constructive blocks", in turn made of "simpler" and "smaller" ones. | |
*/ | |
function acceptedBinFormat(bin) { | |
if (bin == 1 || bin === 0 || bin === '0') | |
return true; | |
else | |
return bin; | |
} | |
function arePseudoBin() { | |
var args = [].slice.call(arguments), len = args.length; | |
while(len--) | |
if (acceptedBinFormat(args[len]) !== true) | |
throw new Error('argument must be 0, \'0\', 1, or \'1\', argument ' + len + ' was ' + args[len]); | |
return true; | |
} | |
// basic building blocks allowed by the rules are ~, &, and |, we'll fake these | |
// in a way that makes what they do (at least when you use them) more obvious | |
// than the other available options do. | |
function not(a) { | |
if (arePseudoBin(a)) | |
return a === 1 ? 0 : 1; | |
} | |
function and(a, b) { | |
if (arePseudoBin(a, b)) | |
return a + b < 2 ? 0 : 1; | |
} | |
function nand(a, b) { | |
if (arePseudoBin(a, b)) | |
return not(and(a, b)); | |
} | |
function or(a, b) { | |
if (arePseudoBin(a, b)) | |
return nand(nand(a,a), nand(b,b)); | |
} | |
function xor(a, b) { | |
if (arePseudoBin(a, b)) | |
return nand(nand(nand(a,b), a), nand(nand(a,b), b)); | |
} | |
function halfAdder(a, b) { | |
if (arePseudoBin(a, b)) | |
return { carry: and(a, b), sum: xor(a, b) }; | |
} | |
function fullAdder(a, b, c) { | |
if (arePseudoBin(a, b, c)) { | |
var h0 = halfAdder(a, b), | |
h1 = halfAdder(h0.sum, c); | |
return {carry: or(h0.carry, h1.carry), sum: h1.sum }; | |
} | |
} | |
function fourBitAdder(a, b) { | |
if (typeof a.length == 'undefined' || typeof b.length == 'undefined') | |
throw new Error('bad values'); | |
// not sure if the rules allow this, but we need to pad the values | |
// if they're too short and trim them if they're too long | |
var inA = Array(4), | |
inB = Array(4), | |
out = Array(4), | |
i = 4, | |
pass; | |
while (i--) { | |
inA[i] = a[i] != 1 ? 0 : 1; | |
inB[i] = b[i] != 1 ? 0 : 1; | |
} | |
// now we can start adding... I'd prefer to do this in a loop, | |
// but that wouldn't be "connecting the other 'constructive blocks', | |
// in turn made of 'simpler' and 'smaller' ones" | |
pass = halfAdder(inA[3], inB[3]); | |
out[3] = pass.sum; | |
pass = fullAdder(inA[2], inB[2], pass.carry); | |
out[2] = pass.sum; | |
pass = fullAdder(inA[1], inB[1], pass.carry); | |
out[1] = pass.sum; | |
pass = fullAdder(inA[0], inB[0], pass.carry); | |
out[0] = pass.sum; | |
return out.join(''); | |
} | |
// test | |
fourBitAdder('1010', '0101'); // 1111 | |
parseInt(fourBitAdder('1010', '0101'), 10); // 15 | |
// really long test | |
var outer = inner = 16, a, b; | |
while(outer--) { | |
a = (8|outer).toString(2); | |
while(inner--) { | |
b = (8|inner).toString(2); | |
console.log(a + ' + ' + b + ' = ' + fourBitAdder(a, b)); | |
} | |
inner = outer; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment