# 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.

## Table of Contents

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.

- Bit shifting
- Using Stack data structure
- 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 **array, which stores exact**

**int[]***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^{32} . . . . . 2^{7}, 2^{6}, 2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 2^{0}

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^{0} = 1 x 1 = 1

1 << 1 = 1 x 2^{1} = 1 x 2 = 2

1 << 2 = 1 x 2^{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
```

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.