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 2k times, so k = 1
.
Right Shift Formula:
num >> 1
is equivalent tonum/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
Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.