Convert Decimal Numbers to Binary Numbers

In this article, we will write the code to count the number of bits present for a given input.

Introduction

Given a decimal number, continue dividing it by 2 until it reaches either 0/1 and record the remainder at each step. The resulting list of remainders is the equivalent binary number for your decimal number.

Example:

Input: 125

Output: 1111101

Repeatedly do the modulo operation until n becomes 0 using

“%” and “division” operations.

So, using the modulo and division method, we calculate the binary representation of a decimal number. Let’s represent the binary by considering the remainder column from bottom to top.

(125)₁₀ becomes (1111101)₂

Illustration

The illustration below explains the process of counting the digits in an integer.

Let's visualize the math:

Problem statement

Given an integer, return the number of bits present in an integer input.

Example #1:

Input:  n = 125

Output: 7 (1, 1, 1, 1, 1, 0, 1)

Example #2:

Input:  n = 129

Output: 8 (1, 0, 0, 0, 0, 0, 0, 1)

Intuition

There are a few ways we can solve this problem.

1. Bit shifting
2. Using Stack data structure
3. Bit shifting (optimal)

Bit-shifting

This is an example problem for converting from decimal to an integer. Solving this problem helps us to understand how bits are stacked together to form a decimal number. Let’s see some of the approaches to solving this algorithmic problem.

We used the right-shift operator here >>. It divides the number 2^k times, so k = 1.

Right Shift Formula:

num >> 1 is equivalent to num/2

Implementation

We only count the number of bits present in the number.

Solutions

Java

class DecimalToBinary {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            ++count;
            n >>= 1; // this is equivalent to (n = n >> 1) OR (n = n/2);
        }
        return count;
    }

     public static void main(String[] args) {
        int number = 125;
        System.out.println("Number of bits : " + helper(number));
    }
}

// Output: Number of bits : 7

Python

def DecimalToBinary(n):
    count=0
    while(n>0):
        count+=1
        n>>=1
    return count

n=125
print("Number of bits : ",DecimalToBinary(n))

JavaScript

const DecimalToBinary = (n) => {
    let count = 0;
    
    while (n > 0) {
        ++count;
        n >>= 1; // this is equivalent to (n = n >> 1) OR (n = n/2);
    }
    
    return count;
}

console.log ('Number of bits', DecimalToBinary (125));

// Output: Number of bits 7

C++

#include <iostream>
using namespace std;

int helper(int n) {
  int count = 0;
  
  while (n > 0) {
    ++count;
    n >>= 1;
  }
  
  return count;
}

int main() {
  int number = 125;
  cout << "Number of bits : " << helper(number);
  return 0;
}

// Output:Number of bits // Output: 

TypeScript

export const DecimalToBinary = (n: number): number => {
    let count: number = 0;

    while (n > 0) {
        ++count;
        n >>= 1; // this is equivalent to (n = n >> 1) OR (n = n/2);
    }

    return count;
}

console.log('Number of bits', DecimalToBinary(125));

// Output: Number of bits 7

Using Stack data structure

Let’s represent the bits present in the number in an array of integers.

Solutions

Java

import java.util.Arrays;
import java.util.Stack;

class DecimalToBinary {
    private static String helper(int n) {
        Stack<Integer> stack = new Stack<>();

        while (n > 0) {
            int remainder = n % 2; // remainder gives either 0 OR 1
            stack.push(remainder); // store the remainder value in stack
            n >>= 1; // this is equivalent to n = n/2;
        }
        
        //loggers
        for (String s : Arrays.asList("while loop breaks only when \"number\" terminates to : " + n, "  ")) {
            System.out.println(s);
        }

        int[] bits = new int[stack.size()];
        int k = 0;

        while (!stack.isEmpty()) {
            //each bit is popped and stored in array of integers
            bits[k++] = stack.pop();
        }

        return Arrays.toString(bits);
    }

     public static void main(String[] args) {
        int number = 125;
        System.out.println("Binary representation of number : \"" + number + "\" is : " + helper(number));
    }
}

/*
Output:

while loop breaks only when "number" terminates to : 0
  
Binary representation of number : "125" is : [1, 1, 1, 1, 1, 0, 1]
*/

Python

def convertDecimal(num):
    stack = []
    while num > 0:
        remainder = num % 2
        stack.append(remainder)
        num  >>= 1
    print("while loop breaks only when n terminates to :  0 \n")    

    binary = ""
    while len(stack) != 0:
        binary += str(stack.pop())
    
    return binary

num=125
print("Binary representation of number : \"" ,num , "\" is : ",convertDecimal(num))

JavaScript

const DecimalToBinary = (n) => {
    
    const array = [];
    
    while (n > 0) {
        let remainder = n % 2;
        array.push (remainder);
        n >>= 1; // this is equivalent to n/2;
    }
    
    //loggers
    console.log ('while loop breaks only when "n" terminates to : ', n);
    console.log ('  ');

    return array.reverse ();
}

console.log('Binary representaion of number', 125 , 'is', DecimalToBinary(125));

// Output:
// while loop breaks only when "n" terminates to :  0
// Binary representaion of number 125 is [ 1, 1, 1, 1, 1, 0, 1 ]

C++

#include <iostream>
#include <stack>
using namespace std;

void convertDecimal(int number){
    stack<int> stack;
    while (number > 0){
        int remainder = number % 2;
        stack.push(remainder);
        number >>= 1;
    }

    cout << "while loop breaks only when n terminates to :  0 \n";
    
    while (!stack.empty()){
        int item = stack.top();
        stack.pop();
        cout << item;
    }
}


int main() {
    int number = 125;
    convertDecimal(number);
    return 0;
}

// Output:
// while loop breaks only when n terminates to :  0 
// 1111101

TypeScript

export const DecimalToBinary = (n: number): number[] => {

    const array: number[] = [];

    while (n > 0) {
        let remainder: number = n % 2;
        array.push(remainder);
        n >>= 1; // this is equivalent to n/2;
    }

    //loggers
    console.log('while loop breaks only when "n" terminates to : ', n);
    console.log('  ');

    return array.reverse();
}

console.log('Binary representaion of number', 125, 'is', DecimalToBinary(125));

/*
Output:

while loop breaks only when "n" terminates to :  0
  
Binary representaion of number 125 is [ 1, 1, 1, 1, 1, 0, 1 ]
*/

As we receive the bits in reverse order, we use a stack for popping them one by one and storing them in an array of integers. So, the resultant bits array is { 1, 1, 1, 1, 1, 0, 1 } for the number 125.

Complexity analysis:

Time complexity: O(logn)

The run time for this algorithm is: O(log N).

With each iteration, we halve the number until we reach either 0 or 1. You only divide a number n recursively into halves at most log2(n) times, which is the boundary of the recursion.

2·2·…·2·2 = 2x ≤ n ⇒ log2(2^x) = x ≤ log2(n)

Hence, the time complexity takes logarithmic time.

To understand this logarithmic approach, please search for “Master Theorem”.

Space complexity:`O(n/2​)` or O(n)

The space complexity is O(n + m).

The extra space required depends on the number of items stored in the stack, which stores exact n/2​ elements. We also used an Integer array to store the bits, and the extra space required depends on the number of items stored in the int[] array, which stores exact m/2​ elements.

Hence, the overall space used is n/2 + m/2​, which is O(n+m).

Bit shifting - optimal

Using Bit-shifting is fast and easy.

We have already seen how the bits are stacked together for the number 125 using the stack approach.

Now, imagine the binary 2 powers from right to left, which are arranged like below.

2³² . . . . . 2⁷, 2⁶, 2⁵, 2⁴, 2³, 2², 2¹, 2⁰

So, the binary representation of 125 is { 1, 1, 1, 1, 1, 0, 1 }.

Note: Left shifting any number results in multiplying it with powers of 2.

1 << 0 = 1 x 2⁰ = 1 x 1 = 1

1 << 1 = 1 x 2¹ = 1 x 2 = 2

1 << 2 = 1 x 2² = 1 x 4 = 4

So, on each iteration, we get 1, 2, 4, 8, 16, 31, 64, 128, and so on.

So, until 64, the loop runs, and when 128 is encountered, the loop terminates as 128 <= 125 fails.

Solutions

Java

class DecimalToBinary {
    private static int helper(int n) {
        int bitsCounter = 0;

        while ((1 << bitsCounter) <= n) {
            bitsCounter += 1;
        }

        return bitsCounter;
    }

    public static void main(String[] args) {
        int number = 125;
        System.out.println("Number of bits : " + helper(number));
    }
}

// Output: Number of bits : 7

Python

def DecimalToBinary(n):
    bitCounter=0
    while((1 << bitCounter) <= n):
        bitCounter+=1
    return bitCounter

number = 125
print("Number of bits : ",DecimalToBinary(number))

JavaScript

const bitLength = (n) => {
    let bitsCounter = 0;

    while ((1 << bitsCounter) <= n) {
        bitsCounter += 1;
    }

    return bitsCounter;
}

console.log ('Number of bits', bitLength (125));

// Output: Number of bits : 7

C++

#include <iostream>
using namespace std;

int helper(int n){
  int bitsCounter = 0;

  while ((1 << bitsCounter) <= n){
      bitsCounter += 1;
  }
  
  return bitsCounter;
}

int main() {
  int number = 125;
  cout << "Number of bits : " << helper(number);
  return 0;
}

// Output: Number of bits : 7

TypeScript

export const bitLength = (n: number): number => {
    let bitsCounter: number = 0;

    while ((1 << bitsCounter) <= n) {
        bitsCounter += 1;
    }

    return bitsCounter;
}

console.log('Number of bits', bitLength(125));

// Output: Number of bits : 7