Sum of Two Integers - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

function visMainFunction(a, b) {
    startBatch();
    makeVisVariable(a).options({
        label: 'a',
        labelExtractionPolicy: val => `${val} (bin: ${formatBinary(val)})`,
        maxElementLabelWidth: null
    }).createVis();

    makeVisVariable(b).options({
        label: 'b',
        labelExtractionPolicy: val => `${val} (bin: ${formatBinary(val)})`,
        maxElementLabelWidth: null
    }).createVis();
    endBatch();

    explanationNotification();

    notification(`
        ▶️ <b>Starting the iterative process</b><br>
        In each iteration we decompose the addition into:<br>
        • <b>sumWithoutCarries</b> = <code>a ^ b</code> (this becomes the next <b>a</b>)<br>
        • <b>missingCarryContribution</b> = <code>(a &amp; b) &lt;&lt; 1</code> (this becomes the next <b>b</b>)<br><br>
        We keep repeating this until <b>b</b> becomes <code>0</code> — meaning no carry bits remain.<br>
        At that point, adding <code>0</code> changes nothing, so <b>a</b> is the final result.
    `);

    while (b !== 0) {
        startPartialBatch();

        const missingCarryContribution = (a & b) << 1;
        explainStep(a, b);

        a = a ^ b; // sumWithoutCarries
        b = missingCarryContribution;

        endBatch();
    }

    notification(`
        🏁 <b>Done!</b><br>
        <code>b</code> has become <b>0</b>.<br>
        Adding <b>0</b> to <code>a</code> leaves it unchanged.<br>
        Therefore, the final result is the current value of <code>a</code>, which is <b>${a}</b>. ✅
    `);
    return a;
}

function explainStep(a, b) {
    const missingCarryBeforeShift = a & b;
    const missingCarryContribution = missingCarryBeforeShift << 1;
    const sumWithoutCarries = a ^ b;

    const bitLength = Math.max(
        formatBinary(a).length,
        formatBinary(b).length,
        formatBinary(missingCarryContribution).length,
        formatBinary(sumWithoutCarries).length
    );

    const aBits = highlightBits(formatBinary(a).padStart(bitLength, '0'));
    const bBits = highlightBits(formatBinary(b).padStart(bitLength, '0'));
    const carryBits = highlightBits(formatBinary(missingCarryBeforeShift).padStart(bitLength, '0'));
    const shiftedCarryBits = highlightBits(formatBinary(missingCarryContribution).padStart(bitLength, '0'));
    const sumBitsWithoutCarries = highlightBits(formatBinary(sumWithoutCarries).padStart(bitLength, '0'));

    notification(`
        🔄 <b>Processing a = ${a}, b = ${b}</b>
        <pre style="white-space: pre-wrap;">
a                      = ${aBits} (the binary representation of <code>a</code> at the beginning of this iteration)
b                      = ${bBits} (the binary representation of <code>b</code> at the beginning of this iteration)
a & b                  = ${carryBits} (the carry bits before shifting them to their carried locations)
(a & b) << 1           = ${shiftedCarryBits} (the binary representation of <code>missingCarryContribution</code>, formed by the carry bits after shifting them to their carried locations — <b>this becomes the new <code>b</code></b>)
a ^ b                  = ${sumBitsWithoutCarries} (the binary representation of <code>sumWithoutCarries</code> — <b>this becomes the new <code>a</code></b>)
        </pre>
    `);
}

function highlightBits(bits) {
    return [...bits]
        .map(bit => bit === '1' 
            ? makeColoredSpan('<b>1</b>', 'green')
            : makeColoredSpan('0', 'gray')
        )
        .join('');
}

function formatBinary(val) {
    return (val >>> 0).toString(2);
}

Approach

Language note (Python vs fixed-width ints):
This explanation assumes a fixed-width, two’s-complement integer model (as in Java, C/C++, or JavaScript). In Python, integers have arbitrary precision and do not wrap to a fixed number of bits, so this exact implementation will not behave correctly for negative numbers in Python as-is.
We are given two signed integers a and b, and we want to compute their sum without using + or -. Instead, we simulate how binary addition works at the bit level.
Intuition — Break the Addition into Two Independent Pieces:
In binary addition, each bit-position produces:
- a sum bit (the current column’s result)
- a carry bit into the next higher position
Instead of directly adding a and b, we form two new numbers whose sum is exactly equal to the intended total:
- sumWithoutCarries:
  This is the result you would get if you ignored all carries. The truth table per bit-position is:
  - 0 + 0 → 0
  - 0 + 1 → 1
  - 1 + 0 → 1
  - 1 + 1 → 0 (carry is ignored here)
  This behavior matches XOR, so a ^ b is the sumWithoutCarries.
- missingCarryContribution:
  Carry occurs only when both bits are 1:
  - 1 + 1 is the only case that produces carry (1).
  Bitwise AND finds these positions: a & b. Since the carry belongs to the next higher bit, we shift it left: (a & b) << 1.
These two numbers,
- sumWithoutCarries = a ^ b
- missingCarryContribution = (a & b) << 1
satisfy the identity:
sumWithoutCarries + missingCarryContribution = a + b So we can replace a and b with these values and repeat.
Iterative Process — Resolve All Remaining Carries:
After each decomposition:
- a holds the sumWithoutCarries.
- b holds the missingCarryContribution that still needs to be added.
In each iteration:
- a = a ^ b — new sumWithoutCarries
- b = (a & b) << 1 — new missingCarryContribution
The “missing carry” bits keep moving left and getting re-applied until no bit-position produces a carry anymore.

When b finally becomes 0:
- No more carry bits remain.
- Adding 0 to a leaves it unchanged.
- Thus, a now holds the final answer.
Why the loop always terminates (finite number of iterations):
On every iteration, b becomes the new missingCarryContribution: (a & b) << 1. This implies:
- Carry bits always shift left toward higher bit-positions.
- Some carry bits may also disappear early whenever the next iteration’s a has a 0 in that bit-position (because a & b clears such bits).
A carry cannot persist indefinitely — it can only:
- keep shifting left until it moves beyond the most significant bit, or
- be removed earlier when ANDing produces 0 at that position.
Once all carry bits have either been absorbed or shifted out of range, b becomes 0, and the loop terminates.

Time Complexity

O(1) The loop can run only a bounded number of times because carry bits can shift left at most through a fixed number of bit-positions.

Space Complexity

O(1) Only a few integer variables are used.

Input-1

Sum of Two Integers - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity