Decimal to Binary: flowchart, algorithm and program
This program reads an integer n and prints its binary form. It divides n by 2 again and again, saves each remainder in the bits array, and then prints the saved remainders in reverse order.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set i = 0, bits[32].
- Step 3: Read n.
- Step 4: If n == 0, go to step 5; otherwise go to step 6.
- Step 5: Set bits[i++] = 0.
- Step 6: If n > 0, go to step 7; otherwise go to step 10.
- Step 7: Set bits[i] = n % 2.
- Step 8: Set n = n / 2.
- Step 9: Increase i by 1. Go to step 6.
- Step 10: Print "Binary: ".
- Step 11: Set j = i - 1.
- Step 12: If j >= 0, go to step 13; otherwise go to step 15.
- Step 13: Print bits[j].
- Step 14: Decrease j by 1. Go to step 12.
- Step 15: Print newline.
- Step 16: Stop.
Pseudocode
BEGIN
i ← 0, bits[32]
READ n
IF n == 0 THEN
bits[i++] ← 0
END IF
WHILE n > 0 DO
bits[i] ← n % 2
n ← n / 2
i++
END WHILE
PRINT "Binary: "
j ← i - 1
WHILE j >= 0 DO
PRINT bits[j]
j--
END WHILE
PRINT newline
END
Program in C, Python and Java
Decimal to Binary program in C
#include <stdio.h>
int main() {
int n, i = 0, j;
int bits[32];
printf("Enter n: ");
scanf("%d", &n);
if (n == 0) {
bits[i++] = 0;
}
while (n > 0) {
bits[i] = n % 2;
n = n / 2;
i++;
}
printf("Binary: ");
for (j = i - 1; j >= 0; j--) {
printf("%d", bits[j]);
}
printf("\n");
return 0;
}Decimal to Binary program in Python
n = int(input("Enter n: "))
bits = []
if n == 0:
bits.append(0)
while n > 0:
bits.append(n % 2)
n = n // 2
print("Binary: ", end="")
for j in range(len(bits) - 1, -1, -1):
print(bits[j], end="")
print()Decimal to Binary program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] bits = new int[32];
int i = 0;
System.out.print("Enter n: ");
int n = sc.nextInt();
if (n == 0) {
bits[i++] = 0;
}
while (n > 0) {
bits[i] = n % 2;
n = n / 2;
i++;
}
System.out.print("Binary: ");
for (int j = i - 1; j >= 0; j--) {
System.out.print(bits[j]);
}
System.out.println();
}
}
Sample input: n = 13
Output: Binary: 1101
How it works
- n % 2 gives the last binary digit of n, so each pass of the while loop stores it in bits[i] and then does i++.
- n = n / 2 drops that digit, and the loop keeps going while n > 0. When n reaches 0, all the digits have been collected.
- The remainders come out from the least significant bit to the most significant bit, so the output loop runs j from i - 1 down to 0 to print them in the right order.
- For n = 13: remainders are 1, 0, 1, 1 (13 -> 6 -> 3 -> 1 -> 0). Printed in reverse this gives 1101.
- The special case n == 0 stores a single 0 in bits[0] so the program prints 0. Without it the while loop would not run and nothing would print.
Dry run (trace table)
| Step | Line | Box | i | n | bits[0] | bits[1] | bits[2] | bits[3] | j | Output |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||||
| 2 | 4 | i = 0, bits[32] | 0 | |||||||
| 3 | 8 | Read n | 0 | 13 | Enter n: | |||||
| 4 | 10 | n == 0? | 0 | 13 | ||||||
| 5 | 14 | n > 0? | 0 | 13 | ||||||
| 6 | 15 | bits[i] = n % 2 | 0 | 13 | 1 | |||||
| 7 | 16 | n = n / 2 | 0 | 6 | 1 | |||||
| 8 | 17 | i++ | 1 | 6 | 1 | |||||
| 9 | 14 | n > 0? | 1 | 6 | 1 | |||||
| 10 | 15 | bits[i] = n % 2 | 1 | 6 | 0 | |||||
| 11 | 16 | n = n / 2 | 1 | 3 | 0 | |||||
| 12 | 17 | i++ | 2 | 3 | ||||||
| 13 | 14 | n > 0? | 2 | 3 | ||||||
| 14 | 15 | bits[i] = n % 2 | 2 | 3 | 1 | |||||
| 15 | 16 | n = n / 2 | 2 | 1 | 1 | |||||
| 16 | 17 | i++ | 3 | 1 | ||||||
| 17 | 14 | n > 0? | 3 | 1 | ||||||
| 18 | 15 | bits[i] = n % 2 | 3 | 1 | 1 | |||||
| 19 | 16 | n = n / 2 | 3 | 0 | 1 | |||||
| 20 | 17 | i++ | 4 | 0 |
Time and space complexity
Time: O(log n) · Space: O(1). n is halved each iteration, so the loops run about log2(n) times; the bits array has a fixed size of 32.
Common mistakes
- Printing the bits in the order they were stored (j from 0 up to i - 1). This prints the binary number reversed, 1011 instead of 1101 for 13.
- Forgetting the n == 0 case. The while loop never runs, i stays 0, and the program prints no digits at all.
- Using the value of n after the loop. By then n has been divided down to 0, so keep a copy of the original if you need it later.
- Entering a negative number. The while (n > 0) condition fails, so nothing is printed; this program is meant for non-negative integers.
Viva questions
Q1. Why is the variable i initialised to 0, and what does it represent at the end of the while loop?
i is the index where the next remainder is stored, so it must start at the first array position, 0. After the loop it equals the number of bits, so the last stored bit is at i - 1.
Q2. Why do you print the array from i - 1 down to 0 instead of from 0 upwards?
The first remainder we get is the least significant bit and the last one is the most significant bit. Binary is written with the most significant bit first, so we print in reverse order.
Q3. What is the purpose of the if (n == 0) block on lines 10-12?
If n is 0 the while loop never runs, so nothing would be stored and nothing would be printed. The if block stores a single 0 and sets i to 1, so the output is 0.
Q4. What does n % 2 give and what does n / 2 do here? Why does integer division work for this?
n % 2 gives the last binary digit (the remainder), and n / 2 drops that digit by removing the fractional part, since both operands are integers. Repeating this until n becomes 0 extracts all the bits.
Q5. What will the program output for a negative input such as -5, and why?
It prints just 'Binary: ' with no digits. n == 0 is false and n > 0 is false, so no bits are stored and i stays 0, so the printing loop does not run. The program does not handle negative numbers.
Q6. Why is the array size 32? Can it overflow?
A positive int has at most 31 value bits on a typical 32-bit system, so 32 slots are enough. Since only positive values pass the while condition, there is no overflow.
Q7. What is the time complexity of this program?
O(log n), since n is halved every iteration, so the while loop runs about log2(n) times. The printing loop runs the same number of times, so the total is still O(log n).
Q8. What would you change to convert to octal or hexadecimal instead of binary?
Replace 2 with the new base (8 or 16) in n % base and n / base. For hex, the remainders 10 to 15 must be printed as the letters A to F, for example using a lookup string or printf with %X, and the array size could be smaller.
Frequently asked questions
Why do we print the remainders in reverse order?
The first remainder you get is the lowest bit (the rightmost one), and the last remainder is the highest bit. Reading the array from i - 1 down to 0 puts the highest bit first, as in normal binary notation.
Why is the bits array size 32?
A positive int is at most 31 bits long on typical systems, so 32 slots are enough to hold every remainder with room to spare.
What does the program print for n = 0?
It prints Binary: 0. The if (n == 0) block stores 0 in bits[0] and sets i to 1, so the output loop prints that single 0.