#038 - Building a decimal-to-binary converter

This Nibble walks through a small program that converts a positive decimal integer into its binary representation.

What the walkthrough covers:

The division-by-2 algorithm and why it produces bits in reverse order.
A recursive implementation that uses stack unwinding to print bits in the correct order.
Two helpers that compute bit width and insert nibble spacing.

The division-by-2 algorithm

NOTE: There are other methods to perform decimal to binary conversion. This article is presenting one particular method.

Binary is a base-2 numbering system: every digit position carries a weight of 2ⁿ, where n is the bit’s distance from the least significant bit. Decomposing 13 into binary by powers of two:

To calculate the binary equivalent, we multiply the bit value by its weight then perform a summation of all the values. Consider converting 13 to binary:

13 = 8 + 4 + 0 + 1
   = (1 × 2³) + (1 × 2²) + (0 × 2¹) + (1 × 2⁰)
   = 1101₂

Our program will mimic this algorithm.

The program will navigate from MSB → LSB by repeatedly divide the number by 2 and recording the remainder. The remainders, read in reverse, are the binary representation:

Below is a simulation:

13 / 2 = 6  remainder 1   ← LSB
 6 / 2 = 3  remainder 0
 3 / 2 = 1  remainder 1
 1 / 2 = 0  remainder 1   ← MSB

Reading bottom to top: 1101₂

The algorithm generates bits LSB → MSB but we want to print them MSB → LSB. For this, we’ll use recursion to print the result in reverse via stack unwinding.

The framework for the program contains four steps:

Divide the number by 2.
Record the remainder.
Repeat with the quotient.
Print the remainders in reverse order.

The program

This program constructs the binary representation of a decimal number by continuously dividing the decimal number by two, recording the remainder then printing them in reverse order.

binary() performs the bulk of the conversion. The other functions are helper functions.

bitsRequired() calculates the minimum number of bits needed to represent the number.
addNibbleSpacing() inserts a space after every 4 bits for readability.

#include <iostream>
#include <string>
#include <cassert> 

// Forward declarations
std::string binary(int num, int depth);
int bitsRequired(int num);
std::string addNibbleSpacing(std::string bits);

int main() {    

    int dec {};
    while (true) {
        std::cout << "Enter a decimal number: ";
        std::cin >> dec;
        
        // Check if input is an actual integer
        if (!(std::cin)) {
            std::cout << "Invalid input. Please enter a numeric value.\\n";
            std::cin.clear(); 
            std::cin.ignore(1000, '\\n');
            continue;
        }

        // 2. Validate that number is positive
        if (dec <= 0) {
            std::cout << "Please enter a positive number!\\n";
        } else {
            break;
        }
    }
  
    int bits = bitsRequired(dec);
    int padded = ((bits + 3) / 4) * 4; // round up to nearest multiple of 4

    std::string result = binary(dec, padded);
    std::string formatted = addNibbleSpacing(result);
    std::cout << "\\nBinary: " << formatted << '\\n';
    
}

// Count minimum bits needed to represent num
int bitsRequired(int num) {
    if (num <= 0) return 1;
    int count = 0;
    while (num > 0) {
        count++;
        num /= 2;
    }
    return count;
}

// Fixed-depth recursion: builds binary string with leading zeros
std::string binary(int num, int depth) {
    if (depth == 0) {
        return "";
    }
    
    int rem = num % 2;
    return binary(num / 2, depth - 1) + std::to_string(rem);
}

// Insert a space after every 4 bits for readability
std::string addNibbleSpacing(std::string bits)
{
    std::string formatted{};

    for (std::size_t i{0}; i < bits.length(); ++i)
    {
        formatted += bits[i];

        if ((i + 1) % 4 == 0 && i + 1 != bits.length())
        {
            formatted += ' ';
        }
    }
    return formatted;
}

Simulating `binary(11, 4)`

The recursion is the heart of the program. Each call computes its own rem, recurses, and then appends rem to the result of the recursive call.

Let’s simulate the program running for 11.

Depth	`num`	`rem = num % 2`	Recursive call
4	11	1	`binary(5, 3)`
3	5	1	`binary(2, 2)`
2	2	0	`binary(1, 1)`
1	1	1	`binary(0, 0)`
0	0	—	returns `""` (base case)

The base case returns an empty string. Afterwards, the stack unwinds and std::cout << rem is called consecutively. 1 0 1 1

depth 1: ""    + "1" = "1"
depth 2: "1"   + "0" = "10"
depth 3: "10"  + "1" = "101"
depth 4: "101" + "1" = "1011"

The division-by-2 algorithm

The program

Simulating binary(11, 4)

Simulating `binary(11, 4)`