Wednesday, April 29, 2009

Algorithm: Bitwise operation: convert decimal into binary number


Share at Facebook

We can easily convert from decimal to binary number using the built-in functions from the programming languages. Also we can do this conversion task using division method that we learned at our class.

I'm going to tell you how to convert a decimal number into binary number using Bitwise operations. I'm going to use bit-wise shift, and Bit wise AND(&) operation to achieve the goal.

How the bitwise operation works?

You can ask, how this decimal to binary conversion can achieve using bitwise operations. Here is a small example that will help you to understand the algorithm behind the process. Let say you have a number 12, and you want to get the binary number of this. If you consider the number is 4 bit, it used to stay at Memory as 1100. So lets follow the steps.

Our number 12 = 1100
The Constant 8 = 1000

step-1
======
1 1 0 0 = 12
1 0 0 0 = 8
----------- Doing logical AND operation
1 0 0 0 = 8 is non-zero, so print 1 on screen.

Also divide the constant with 2 using Right Shift(>>) bitwise operation
So our constant will be = 4

step-2
======
1 1 0 0 = 12
0 1 0 0 = 4
----------- Doing logical AND operation
0 1 0 0 = 4 is non-zero, so print 1 on screen.

Also divide the constant with 2 using Right Shift(>>) bitwise operation
So our constant will be = 2

step-3
======
1 1 0 0 = 12
0 0 1 0 = 2
----------- Doing logical AND operation
0 0 0 0 = 0 is zero, so print 0 on screen.

Also divide the constant with 2 using Right Shift(>>) bitwise operation
So our constant will be = 1

step-4
======
1 1 0 0 = 12
0 0 0 1 = 1
----------- Doing logical AND operation
0 0 0 0 = 0 is zero, so print 0 on screen.

So the overall output will be 1100 = 12

Using AND operation, it just checking whether the bit of that position is SET or not.
Using Right Shift operation, it just shifting the bit one step right.(or you can call divide by 2)

Since the bitwise operations are faster than the usual Multiplication, addition, Division, so this process will be much faster than usual number conversion. Remember Its only require the Ligical AND(&) and Logical right shift(>>) operation.

This is just an example that I provided considering the number system is 4 bit on computer memory. But this is the basic process, and this will work for your 8, 16, 32 bit number system. Just need to change the initial value of your constant.

For 8 bit, the initial constant will be decimal of (10000000)
For 16 bit, the initial constant will be decimal of (1000000000000000)
For 32 bit, the initial constant will be decimal of (100000000000000000000000)

And also you need to increase the steps number into (8,16,32) depending upon the bit size.




5 comments:

Anonymous said...

the world is amazing indeed. you just helped me with my mips homework. thanks!

sree said...

very nice illustration..Thanx especially for the example. It helped me to understand this concept better..

sree said...

very nice illustration..Thanx especially for the example. It helped me to understand this concept better..

test said...

Thank you very much for your explanation , I have found a formula of converting decimal to binary in a website that works for me but I really don't understand how it works (it uses shift and || ):

my $number = shift || $decNumber;

Could you please explain how this works ?
Thanks in advance.

Sundaramoorthi.N said...

simple code for decimal to binary numbers in c

#include
main()
{
unsigned char num;
int i,x=128; //x=10000000
//x=0b10000000;
system("clear");
printf("Enter the number : ");
scanf("%d",&num);
printf("Binary Eqivalent : ");
while(x>0)
{
if((num&x)==0)
printf("0");
else
printf("1");
x=x>>1;
}
printf("\n");
}