forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
fullAdder.js
70 lines (63 loc) · 2.1 KB
/
fullAdder.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import getBit from './getBit';
/**
* Add two numbers using only binary operators.
*
* This is an implementation of full adders logic circuit.
* https://en.wikipedia.org/wiki/Adder_(electronics)
* Inspired by: https://www.youtube.com/watch?v=wvJc9CZcvBc
*
* Table(1)
* INPUT | OUT
* C Ai Bi | C Si | Row
* -------- | -----| ---
* 0 0 0 | 0 0 | 1
* 0 0 1 | 0 1 | 2
* 0 1 0 | 0 1 | 3
* 0 1 1 | 1 0 | 4
* -------- | ---- | --
* 1 0 0 | 0 1 | 5
* 1 0 1 | 1 0 | 6
* 1 1 0 | 1 0 | 7
* 1 1 1 | 1 1 | 8
* ---------------------
*
* Legend:
* INPUT C = Carry in, from the previous less-significant stage
* INPUT Ai = ith bit of Number A
* INPUT Bi = ith bit of Number B
* OUT C = Carry out to the next most-significant stage
* OUT Si = Bit Sum, ith least significant bit of the result
*
*
* @param {number} a
* @param {number} b
* @return {number}
*/
export default function fullAdder(a, b) {
let result = 0;
let carry = 0;
// The operands of all bitwise operators are converted to signed
// 32-bit integers in two's complement format.
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#Signed_32-bit_integers
for (let i = 0; i < 32; i += 1) {
const ai = getBit(a, i);
const bi = getBit(b, i);
const carryIn = carry;
// Calculate binary Ai + Bi without carry (half adder)
// See Table(1) rows 1 - 4: Si = Ai ^ Bi
const aiPlusBi = ai ^ bi;
// Calculate ith bit of the result by adding the carry bit to Ai + Bi
// For Table(1) rows 5 - 8 carryIn = 1: Si = Ai ^ Bi ^ 1, flip the bit
// Fpr Table(1) rows 1 - 4 carryIn = 0: Si = Ai ^ Bi ^ 0, a no-op.
const bitSum = aiPlusBi ^ carryIn;
// Carry out one to the next most-significant stage
// when at least one of these is true:
// 1) Table(1) rows 6, 7: one of Ai OR Bi is 1 AND carryIn = 1
// 2) Table(1) rows 4, 8: Both Ai AND Bi are 1
const carryOut = (aiPlusBi & carryIn) | (ai & bi);
carry = carryOut;
// Set ith least significant bit of the result to bitSum.
result |= bitSum << i;
}
return result;
}