Adding without adding

add_no_add.js

/**
 * Performs 4-bit integer addition using direct, unrolled carry-lookahead logic.
 * This function serves as a building block for the 32-bit adder.
 *
 * @param {number} nibbleA The first 4-bit input (0-15).
 * @param {number} nibbleB The second 4-bit input (0-15).
 * @param {number} carryIn The carry-in from the previous 4-bit block (0 or 1).
 * @returns {{sum: number, carryOut: number}} An object containing the 4-bit sum and the carry-out.
 */
function add4BitCarryLookahead(nibbleA, nibbleB, carryIn) {
    // Ensure inputs are treated as 32-bit for bitwise ops, then masked to 4 bits
    nibbleA = (nibbleA | 0) & 0xF;
    nibbleB = (nibbleB | 0) & 0xF;
    carryIn = (carryIn | 0) & 0x1;

    // --- Step 1: Calculate G_i (Generate) and P_i (Propagate) for each bit ---
    // G_i = A_i & B_i
    // P_i = A_i ^ B_i

    // Bit 0 (LSB)
    const A0 = (nibbleA >> 0) & 1;
    const B0 = (nibbleB >> 0) & 1;
    const P0 = A0 ^ B0;
    const G0 = A0 & B0;

    // Bit 1
    const A1 = (nibbleA >> 1) & 1;
    const B1 = (nibbleB >> 1) & 1;
    const P1 = A1 ^ B1;
    const G1 = A1 & B1;

    // Bit 2
    const A2 = (nibbleA >> 2) & 1;
    const B2 = (nibbleB >> 2) & 1;
    const P2 = A2 ^ B2;
    const G2 = A2 & B2;

    // Bit 3 (MSB for 4-bit)
    const A3 = (nibbleA >> 3) & 1;
    const B3 = (nibbleB >> 3) & 1;
    const P3 = A3 ^ B3;
    const G3 = A3 & B3;

    // --- Step 2: Calculate Carries (C) using unrolled lookahead equations ---
    const C1 = G0 | (P0 & carryIn);
    const C2 = G1 | (P1 & C1);
    const C3 = G2 | (P2 & C2);
    const C4 = G3 | (P3 & C3); // This is the carry-out from this 4-bit block

    // --- Step 3: Calculate Sum bits (S_i = P_i ^ C_i) ---
    const S0 = P0 ^ carryIn;
    const S1 = P1 ^ C1;
    const S2 = P2 ^ C2;
    const S3 = P3 ^ C3;

    // --- Step 4: Combine sum bits into the final 4-bit sum ---
    const sum = (S0 << 0) |
                (S1 << 1) |
                (S2 << 2) |
                (S3 << 3);

    return { sum: sum, carryOut: C4 };
}

/**
 * Performs 32-bit integer addition by explicitly calling 8 instances
 * of the 4-bit carry-lookahead adder. This is the "unraveled" version
 * of the loop-based hierarchical adder.
 *
 * @param {number} a The first 32-bit integer.
 * @param {number} b The second 32-bit integer.
 * @returns {number} The 32-bit sum.
 */
function add32BitHierarchicalUnraveled(a, b) {
    // Ensure numbers are treated as 32-bit signed integers for bitwise operations
    a |= 0;
    b |= 0;

    let finalSum = 0;
    let currentCarry = 0; // Initial carry-in for the LSB block is 0

    // --- Block 0 (Bits 0-3) ---
    const nibbleA0 = (a >> 0) & 0xF;
    const nibbleB0 = (b >> 0) & 0xF;
    const result0 = add4BitCarryLookahead(nibbleA0, nibbleB0, currentCarry);
    finalSum |= (result0.sum << 0);
    currentCarry = result0.carryOut;

    // --- Block 1 (Bits 4-7) ---
    const nibbleA1 = (a >> 4) & 0xF;
    const nibbleB1 = (b >> 4) & 0xF;
    const result1 = add4BitCarryLookahead(nibbleA1, nibbleB1, currentCarry);
    finalSum |= (result1.sum << 4);
    currentCarry = result1.carryOut;

    // --- Block 2 (Bits 8-11) ---
    const nibbleA2 = (a >> 8) & 0xF;
    const nibbleB2 = (b >> 8) & 0xF;
    const result2 = add4BitCarryLookahead(nibbleA2, nibbleB2, currentCarry);
    finalSum |= (result2.sum << 8);
    currentCarry = result2.carryOut;

    // --- Block 3 (Bits 12-15) ---
    const nibbleA3 = (a >> 12) & 0xF;
    const nibbleB3 = (b >> 12) & 0xF;
    const result3 = add4BitCarryLookahead(nibbleA3, nibbleB3, currentCarry);
    finalSum |= (result3.sum << 12);
    currentCarry = result3.carryOut;

    // --- Block 4 (Bits 16-19) ---
    const nibbleA4 = (a >> 16) & 0xF;
    const nibbleB4 = (b >> 16) & 0xF;
    const result4 = add4BitCarryLookahead(nibbleA4, nibbleB4, currentCarry);
    finalSum |= (result4.sum << 16);
    currentCarry = result4.carryOut;

    // --- Block 5 (Bits 20-23) ---
    const nibbleA5 = (a >> 20) & 0xF;
    const nibbleB5 = (b >> 20) & 0xF;
    const result5 = add4BitCarryLookahead(nibbleA5, nibbleB5, currentCarry);
    finalSum |= (result5.sum << 20);
    currentCarry = result5.carryOut;

    // --- Block 6 (Bits 24-27) ---
    const nibbleA6 = (a >> 24) & 0xF;
    const nibbleB6 = (b >> 24) & 0xF;
    const result6 = add4BitCarryLookahead(nibbleA6, nibbleB6, currentCarry);
    finalSum |= (result6.sum << 24);
    currentCarry = result6.carryOut;

    // --- Block 7 (Bits 28-31) ---
    const nibbleA7 = (a >> 28) & 0xF;
    const nibbleB7 = (b >> 28) & 0xF;
    const result7 = add4BitCarryLookahead(nibbleA7, nibbleB7, currentCarry);
    finalSum |= (result7.sum << 28);
    currentCarry = result7.carryOut; // This is the final carry-out from the 32-bit addition

    return finalSum;
}

// --- Test Cases ---
console.log("--- 32-bit Hierarchical Unraveled Addition ---");

console.log(`5 + 3 = ${add32BitHierarchicalUnraveled(5, 3)} (expected: 8)`);
console.log(`-5 + 3 = ${add32BitHierarchicalUnraveled(-5, 3)} (expected: -2)`);
console.log(`7 + 10 = ${add32BitHierarchicalUnraveled(7, 10)} (expected: 17)`);
console.log(`0 + 0 = ${add32BitHierarchicalUnraveled(0, 0)} (expected: 0)`);
console.log(`-1 + 1 = ${add32BitHierarchicalUnraveled(-1, 1)} (expected: 0)`);
console.log(`-10 + -5 = ${add32BitHierarchicalUnraveled(-10, -5)} (expected: -15)`);

const MAX_INT = 2147483647; // 2^31 - 1
const MIN_INT = -2147483648; // -2^31

console.log(`${MAX_INT} + 1 = ${add32BitHierarchicalUnraveled(MAX_INT, 1)} (expected: ${MIN_INT})`);
console.log(`${MIN_INT} + (-1) = ${add32BitHierarchicalUnraveled(MIN_INT, -1)} (expected: ${MAX_INT})`);
console.log(`${1000000000} + ${1500000000} = ${add32BitHierarchicalUnraveled(1000000000, 1500000000)} (expected: -1794967296)`);