Skip to content

Instantly share code, notes, and snippets.

@nfeldman
Created July 20, 2011 03:25
Show Gist options
  • Save nfeldman/1094268 to your computer and use it in GitHub Desktop.
Save nfeldman/1094268 to your computer and use it in GitHub Desktop.
javascript 4-bit adder simulator written for Rosetta Code
/**
* ************************************************
* 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