Number of 1 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 count = 0;

    makeVisVariable(n).options({ label: 'n' }).createVis();
    makeVisVariable(count).options({ label: 'count' }).createVis();
    endBatch();

    explanationNotification();
    notification(`
        ▶️ <b>Starting the bit-clearing process</b><br>
        Each iteration applies <code>n = n & (n - 1)</code>,  
        which clears the <b>lowest set bit</b> of <code>n</code>  
        (see the approach section for why this works).<br>
        Every time a bit is cleared, we increment <b>count</b> by 1.<br>
        When <code>n</code> becomes <b>0</b>, all 1-bits have been counted.
    `);

    while (n > 0) {
        startPartialBatch();
        explainBitwiseStep(n);
        n = n & n - 1;
        count += 1;
        endBatch();
    }

    notification(`
        🏁 <b>Done!</b><br>
        All set bits have been cleared, so the process is complete.<br>
        The total number of <b>1</b>-bits in the original number is <b>${count}</b>. ✅
    `);
    return count;
}

let step = 1;

function explainBitwiseStep(n) {
    const nMinus1 = n - 1;
    const result = n & nMinus1;
    const bitLength = Math.max(n, nMinus1, result).toString(2).length;
    const nBinRaw = n.toString(2).padStart(bitLength, '0');
    const nMinus1BinRaw = nMinus1.toString(2).padStart(bitLength, '0');
    const resultBinRaw = result.toString(2).padStart(bitLength, '0');

    const nHighlighted = highlightDifferences(nBinRaw, nMinus1BinRaw);
    const nMinus1Highlighted = highlightDifferences(nMinus1BinRaw, nBinRaw);
    const resultHighlighted = highlightDifferences(resultBinRaw, nBinRaw);

    notification(`
        🔄 <b>Step ${step}</b>:  
        <pre style="white-space: pre-wrap;">
    n           =  ${nHighlighted}   (${n})
    n - 1       =  ${nMinus1Highlighted}   (${nMinus1})
    <hr style="margin: 0;">
    n & (n - 1) =  ${resultHighlighted}   (${result})
        </pre>
        ✅ <b>Lowest set bit cleared.</b> Incrementing <b>count</b>.
    `);

    step++;
}

function highlightDifferences(binStr, compareStr) {
    return binStr.split('')
        .map((char, i) => char !== compareStr[i]
            ? makeColoredSpan(`<b>${char}</b>`, char === '1' ? 'green' : 'orange')
            : char)
        .join('');
}

Approach

We are given an integer n, and we want to compute how many bits in its binary representation are set to 1.
Key Idea — Use the trick n & (n - 1):
Rather than inspecting every bit-position one by one, we repeatedly remove the lowest set bit from n and count how many such removals we can make before n becomes 0.
- Consider the binary form of n. Let the rightmost 1-bit be at position i. All bits to the right of position i are 0, and bit i itself is 1.
- When we compute n - 1:
  - Bit i (the lowest set bit) flips from 1 to 0.
  - All bits to the right of i flip from 0 to 1.
  - Bits to the left of i stay the same.
- Now apply n & (n - 1):
  - At bit i: 1 & 0 = 0 → this bit is cleared.
  - To the right of i: 0 & 1 = 0 → these bits stay 0.
  - To the left of i: both numbers have the same bits, so they remain unchanged.
  Therefore, n & (n - 1) clears exactly the lowest set bit of n and leaves all other bits untouched.
Algorithm Using This Trick:
We maintain an integer count initialized to 0, then:
- While n > 0:
  - Assign n to n & (n - 1) to remove its current lowest set bit.
  - Increment count by 1, because we have just cleared a single 1-bit from n.
- When n becomes 0, there are no more 1-bits left, and count is exactly the number of bits that were set to 1 in the original value.
Why This Approach Avoids Unnecessary Work:
Let k be the number of set bits in n.
- Each execution of n = n & (n - 1) removes exactly one set bit.
- Therefore, the loop performs exactly k iterations — one for each 1-bit.
- A straightforward bit-scanning method would inspect every bit-position from the most significant 1 down to the least significant bit, including positions that contain 0.
Time and Space Complexity:
- Time: O(k), where k is the number of bits set to 1 in n, because each iteration clears exactly one set bit.
- Space: O(1), since we only use a constant amount of extra storage (n, count, and a few temporaries in explanations).

Time Complexity

O(1) Let k be the number of set bits in n.
Each iteration clears exactly one 1-bit using n = n & (n - 1), so the loop runs exactly k times. Each iteration takes O(1) work, giving an overall time of O(k).
Since the problem restricts n to 0 ≤ n ≤ 2³¹ − 1, k can be at most 31, so this is effectively constant time.

Space Complexity

The algorithm uses only a few scalar variables. Each of these variables occupies constant space regardless of the input. Therefore, the space usage is O(1) constant space.

Input-1

Number of 1 Bits - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity