# Convert Decimal Numbers to Binary Numbers

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

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)10 becomes (1111101)2

## Illustration

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

n(value) n n/2 (Quotient) n%2 (Quotient)
n is 125 125 62 1
n/2 is 62 62 31 0
n/2 is 31 31 15 1
n/2 is 15 15 7 1
n/2 is 7 7 3 1
n/2 is 3 3 1 1
n/2 is 1 1 0 1

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 2k 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(2x) = 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.

232 . . . . . 27, 26, 25, 24, 23, 22, 21, 20

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 20 = 1 x 1 = 1

1 << 1 = 1 x 21 = 1 x 2 = 2

1 << 2 = 1 x 22 = 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``````
Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}