Reverse Bits - 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(n) {
    startBatch();
    let res = 0;
    makeVisVariable(res).options({
        label: 'res (reversed bits)',
        labelExtractionPolicy: val => `${val} (bin: ${formatBits(val)})`,
        maxElementLabelWidth: null
    }).createVis();

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

    endBatch();

    for (let i = 0; i < 32; i++) {
        startPartialBatch();
        explainStep(n, res);
        res = (res << 1) | (n & 1);
        n = n >> 1;
        endBatch();
    }
    
    notification(`
        🏁 <b>Completed.</b><br>
        Result at the end of the loop: ${res} (${formatBits(res)})✅
    `);

    return res;
}

function explainStep(n, res) {
    const nBits = formatBits(n);
    const resBits = formatBits(res);
    const bitToPlace = n & 1;

    const placeColor = 'purple';         // Color for the bit being placed into res
    const shiftedZeroColor = 'lightgreen'; // Color for the zero introduced by shifting

    const highlightedNBits = highlightLastBitWithColor(nBits, placeColor);

    const resAfterShift = res << 1;
    const resAfterShiftBits = formatBits(resAfterShift);
    const highlightedResShiftBits = highlightLastBitWithColor(resAfterShiftBits, shiftedZeroColor);

    const resAfterPlace = resAfterShift | bitToPlace;
    const resAfterPlaceBits = formatBits(resAfterPlace);
    const highlightedResAfterPlaceBits = highlightLastBitWithColor(resAfterPlaceBits, placeColor);

    const newN = n >> 1;
    const newNBits = formatBits(newN);

    notification(`
        🔄 <b>Processing current n = ${n}, and current res = ${res}</b>:
        <ul>
            <li>
                <b>Current n in binary:</b> ${highlightedNBits}
            </li>

            <li>
                <b>Bit to place (<code>n &amp; 1</code>):</b> 
                This extracts the <b>last bit</b> of the current <code>n</code> to place into the result — 
                ${makeColoredSpan(bitToPlace, placeColor)}.
            </li>

            <li>
                <b>res before shift in binary:</b> ${resBits}
            </li>

            <li>
                <b>res after shift in binary (<code>res << 1</code>):</b> 
                ${highlightedResShiftBits}<br>
                This left shift moves all bits one position to the left and 
                places ${makeColoredSpan(0, shiftedZeroColor)} at the end.
            </li>

            <li>
                <b>res in binary after setting the last bit to 
                ${makeColoredSpan(bitToPlace, placeColor)}:</b> 
                ${highlightedResAfterPlaceBits} 
                (decimal: <code>${resAfterPlace}</code>)<br>

                We compute <code>res = (res << 1) | (n &amp; 1)</code>, where  
                <code>res << 1</code> is the <b>res after shift</b> and  
                <code>n &amp; 1</code> is the <b>last bit of n (the bit to place)</b>.  
                This operation replaces the trailing 
                ${makeColoredSpan(0, shiftedZeroColor)} introduced by the shift with 
                ${makeColoredSpan(bitToPlace, placeColor)}, the last bit of <code>n</code>.<br><br>

                Using <code>|</code> ensures the correct placement of 
                ${makeColoredSpan(bitToPlace, placeColor)}, because the shift always places a 
                <code>0</code> in the last bit position, and <code>x | 0</code> evaluates to <code>x</code>.
            </li>

            <li>
                <b>n in binary after right shift (<code>n >> 1</code>):</b> 
                ${newNBits} (decimal: <code>${newN}</code>)  
                — we discard the last bit we just used and move on to the next one.
            </li>
        </ul>
    `);
}

function highlightLastBitWithColor(bits, color) {
    const lastIndex = bits.length - 1;
    return [...bits].map((bit, idx) =>
        idx === lastIndex
            ? `<span style="color:${color}"><b>${bit}</b></span>`
            : bit
    ).join('');
}

function formatBits(val) {
    return (val >>> 0).toString(2).padStart(32, '0');
}

Approach

We want to reverse the bits of the 32-bit signed integer provided in the parameter n. To do this, we construct the reversed number bit-by-bit in a variable res, starting from 0. We update n at each step so that it always reflects the remaining bits still to be extracted.
Main idea:
Because the input is a 32-bit integer, we must process all 32 bits — including any leading zeros — to form the correctly reversed 32-bit result. In each of the 32 iterations, we:
- Shift res left by 1 to make room for the next bit.
- Take the last bit of n using n & 1.
- Place that extracted bit at the end of res using res = (res << 1) | (n & 1).
- Right shift n by 1 to remove the used bit.
By the end of 32 iterations, res contains the fully reversed 32-bit pattern so we return it.
Why the formula works:
- res << 1 shifts existing bits left and places a guaranteed 0 at the end.
- n & 1 extracts the last bit of n (the bit to place).
- | correctly inserts this bit, because x | 0 = x and x | 1 = 1.

Time Complexity

The loop always runs for exactly 32 iterations, regardless of the input value. Each iteration performs only constant-time bitwise operations. Therefore, the overall time complexity is O(1).

Space Complexity

We maintain only two integers (n and res) and use no additional data structures. Therefore, the space complexity is O(1).

Input-1

Reverse Bits - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity