Decimal to Binary: The Divide-by-2 Algorithm, Explained

Every integer your program touches already lives in binary — the CPU stores 13 as 1101 and never thinks in decimal. Converting a number to its binary string by hand is the exercise that finally makes that click. It shows up as a warm-up interview question, as the guts of base-conversion utilities, and as the mental model behind every bitmask you'll ever write.

The whole thing reduces to one repeated question: is this number odd or even? Ask it, record the answer, halve the number, and repeat. The sequence of odd/even answers, read in the right direction, is the binary representation.

The problem#

Given a non-negative integer n, return its binary representation as a string. No leading zeros, and 0 maps to "0".

A binary string is just a number written in base 2. Each position is a power of two — ...16 8 4 2 1 — and each digit says whether that power is included in the sum. 13 uses the 8, the 4, and the 1, so its bits are 1101. Our job is to recover those on/off flags from the decimal value alone.

The brute force baseline#

One instinct is to precompute powers of two, then walk from the largest power that fits down to 1, subtracting whenever it fits:

This works, but it's fiddly. You need a separate pass just to find the starting power, you carry a running subtraction, and the two loops are easy to get off-by-one at the boundaries. It's the same asymptotic cost as the clean version but with more moving parts and more ways to introduce a bug.

The key insight: remainders read bottom-up#

Here's the reframe. You don't need to hunt for the top bit. Divide by 2 and the remainder hands you the bottom bit for free.

n % 2 is 1 when n is odd and 0 when n is even — that is exactly the least significant bit. Once you've recorded it, Math.floor(n / 2) shifts every remaining bit down by one position, so the next division exposes the next bit up. Keep dividing until nothing is left.

Because you discover bits from least significant to most significant, you have to reverse the order when you assemble the answer. The trick is to prepend each new bit instead of appending it — that way the newest (higher-order) bit lands in front, and the string reads correctly left to right without a separate reversal step.

The optimal solution#

This is exactly the algorithm the interactive visualizer steps through:

Three lines carry the whole idea. bit = n % 2 peels the lowest bit. binary = bit + binary pushes it onto the front of the growing string. n = Math.floor(n / 2) drops that bit and slides the rest down. The n === 0 guard is the one case the loop can't produce on its own — with n already zero the while never runs and you'd return an empty string, so "0" is handled up front.

Note that bit + binary relies on JavaScript coercing the number bit to a string during concatenation, so 1 + "101" becomes "1101", not 102. If you'd rather be explicit, write String(bit) + binary.

Walkthrough#

Tracing n = 13. Each row is one turn of the loop — read binary from top to bottom to watch the answer assemble back-to-front.

After step 4, n is 0, the while condition fails, and the loop returns "1101". Watch how each remainder slots in front of the previous string: the 1 from step 4 (the most significant bit) ends up leftmost, exactly where it belongs. The division sequence 13 → 6 → 3 → 1 → 0 is the number being repeatedly halved until every power of two has been accounted for.

Complexity#

There's no way to do fundamentally better: the output itself has log n bits, so any correct algorithm must produce at least that many characters. The divide-by-2 method hits that lower bound with constant work per bit.

Common mistakes#

• Appending instead of prepending. binary = binary + bit builds the string in reverse and returns "1011" for 13. Either prepend each bit or append and reverse at the end — pick one, don't mix.
• Forgetting the n === 0 case. With no guard, decimalToBinary(0) skips the loop entirely and returns "" instead of "0".
• Using n / 2 without Math.floor. JavaScript division is floating point, so 3 / 2 is 1.5. Skip the floor and n never cleanly reaches 0, sending the loop off into fractional territory. Use Math.floor(n / 2) or the bitwise n >> 1.
• Expecting it to work for negatives. This algorithm assumes n >= 0. Negative numbers need a two's-complement scheme with a fixed bit width, which is a different problem.
• Assuming bit + binary does math. It only concatenates because binary is a string. If you initialize binary as a number, bit + binary adds instead of joins.

Where this pattern shows up next#

The divide-and-collect-remainders idea isn't specific to base 2. Swap the 2 for any base b — use n % b for the digit and Math.floor(n / b) to advance — and the same loop converts a decimal number into octal, hexadecimal, or any positional system. The odd/even test you used here is the base-2 special case of "what's the remainder in this base?"

The n % 2 / n >> 1 pairing is also the backbone of bit-counting problems like counting set bits (Number of 1 Bits), where you inspect the low bit and shift instead of building a string. Once the "peel the bottom bit, then shift" motion is automatic, a whole family of bit-manipulation problems stops feeling like magic.

You can step through the conversion interactively to watch each division peel off a bit and the binary string assemble right to left.

FAQ#

Why do we divide by 2 to get binary?#

Binary is base 2, and dividing by the base is how you extract digits in any positional number system. The remainder n % 2 is the current lowest digit (0 or 1), and dividing by 2 discards that digit and shifts the rest down so the next division reveals the next digit up. Repeat until nothing remains and you've collected every bit. Divide by 8 instead and you'd get octal; divide by 16 and you'd get hex.

Why prepend the bit instead of appending it?#

Because division discovers bits from least significant to most significant — the first remainder you get is the rightmost bit of the answer. If you appended, the bits would come out reversed. Prepending each new bit puts the higher-order bits in front as you go, so the final string reads correctly left to right without a separate reversal step. Appending and then reversing at the end works too; just don't do both.

What is the time complexity of decimal-to-binary conversion?#

O(log n). Each loop iteration halves n, so the number of iterations equals the number of bits in n, which is about ⌊log₂ n⌋ + 1. Space is also O(log n) for the output string. You can't beat this asymptotically because the binary representation itself has log n characters, and any correct answer must emit all of them.

How do I handle 0 and negative numbers?#

Zero is a special case: the while loop never runs for n = 0, so guard it explicitly and return "0". Negative numbers aren't handled by this algorithm at all — it assumes n >= 0. Representing negatives in binary requires choosing a fixed bit width and a convention like two's complement, which is a separate problem from the plain magnitude conversion shown here.