Convert decimal number to binary number

Problem to convert decimal number to binary representation is a very trivial one and asked only in very start of interview process. However, this problem explains couple of concept very effectively.

There are three ways to get binary representation of a decimal number.

decimal number to binary : Using stacks
Idea is to divide number by 2 each time till number becomes 1 and store remainder of each division in a stack. Why in stack? Because the last 1 or 0 will be most significant bit of binary number.

Example: Let’s say we want to convert 27  to binary number.

27/2 =13  Remainder 1
13/2 =6   Remainder 1
6/2 = 3   Remainder 0
3/2 = 1   Remainder 1.
1/2 = 0   Remainder 1.

When remainder is printed in reverse order it’s 11011 which is binary representation of 27.

#include <stdio.h>
 
#define N 32
 
typedef struct stack {
  short top;
  short items[N];
} stack;
 
void initializeStack( stack *s){
	s->top = -1;
}
 
void push( stack *s, short element ){
	s->items[++s->top] = element;
}
 
short isEmpty( stack *s ){
	return s->top < 0;
}
short pop (stack *s ){
	if(!isEmpty(s)){
		return s->items[s->top--];
	}
	return -1;
}
void main(){
 
    stack bitStack;
    initializeStack(&bitStack);
 
    int n;
 
    printf("Enter the number :");
    scanf("%d", &n);
 
    while(n){
    	/* Pushing the remainder to top of stack */
        push(&bitStack, n%2);
        n = n/2;
    }
 
    printf("\nBinary representation is :");
    while(!isEmpty(&bitStack)){
    	/* Popping all remainders in reverse order from stack */
        printf("%d ", pop(&bitStack));
    }
    printf("\n");
 
    return 0;
}

Complexity of algorithm to convert a decimal number to binary representation is log(n).

decimal number to binary : Using recursion

Method 1 can be implemented using recursion also and since we know that depth of stack will never be more than size of largest number that can be represented in machine, we can safely discard risk of stack overflow.

#include <stdio.h>
 
void convertToBinary(unsigned int N){

	if( N == 1 || N == 0 ) { 
		printf("%d", N); 
		return;
	}
 
	convertToBinary(N/2);
	printf("%d", N%2);
} 
int main(){
 
    int n;
 
    printf("Enter the number :");
    scanf("%d", &n);
 
    convertToBinary(n);
 
    return 0;
}

decimal number to binary: A tricky one

Divide by two operation on a number is nothing but right shift of a number. And also checking if divide by 2 will give us remainder 0 or 1 is to just check last bit of number. Using this information we can easily find binary representation of a number.

Idea is to right shift number till it becomes 0 and check each time if last if bit is 0 or 1 by and number with 1 and output bit.

#include <stdio.h>
 
void convertToBinary(unsigned int N){
	while(N){
		if( N & 1) printf("%d", 1);
		else printf("%d", 0);
 
		N = N>>1;
	}
 
} 
int main(){
 
    int n;
 
    printf("Enter the number :");
    scanf("%d", &n);
 
    convertToBinary(n);
 
    return 0;
}

Please share if something is wrong or missing in post. If you are interested in contributing to website, please contact us.