C++ Program to Convert Decimal to Binary

Date: 10/26/1999 at 12:33:35
From: Kevin 
Subject: C++ Program Code to convert numbers to binary

I am looking for the C++ routine to convert decimal numbers to binary.

I have been told it is easy to do using an array that stores the DIV 
or MOD of the number when divided by 2 in order to display the array 
backwards.

I would also like to convert decimal numbers to hex as well.

Date: 10/26/1999 at 19:11:36
From: Doctor Jeremiah
Subject: Re: C++ Program Code to convert numbers to binary

Hi Kevin.

This does what you ask. If you need help understanding why it works 
please mail me back.

I used shifts instead of exponents so that I wouldn't have to include 
<math.h> to get pow()

  #include <stdio.h>

  short decimal2binary(unsigned long decimal_value, char binary_value[32])
  {
   short index,significant_digits=0;
   unsigned long temp_value;
    for(index=31;index>=0;index--)
    {
     // temp_value=decimal_value/pow(2,index)
     temp_value=decimal_value/(1<<index);
     if(temp_value>0)
     {
      binary_value[index]=(char)('0'+temp_value);
      // decimal_value=decimal_value%pow(2,index)
      decimal_value=decimal_value%(1<<index);
      if(!significant_digits)
       significant_digits=index;
     }
     else
     {
      binary_value[index]='0';
     }
    }
    return significant_digits;
   }  

  short decimal2hex(unsigned long decimal_value, char hex_value[8])
  {
   short index,significant_digits=0;
   unsigned long temp_value;
   for(index=7;index>=0;index--)
   {
    // temp_value=decimal_value/pow(16,index)
    temp_value=decimal_value/(1<<(index<<2));
    if(temp_value>9)
    {
     hex_value[index]=(char)('A'-10+temp_value);
     // decimal_value=decimal_value%pow(16,index)
     decimal_value=decimal_value%(1<<(index<<2));
     if(!significant_digits)
      significant_digits=index;
    }
    else if(temp_value>0)
    {
     hex_value[index]=(char)('0'+temp_value);
     // decimal_value=decimal_value%pow(16,index)
     decimal_value=decimal_value%(1<<(index<<2));
     if(!significant_digits)
      significant_digits=index;
    }
    else
    {
     hex_value[index]='0';
    }
   }
   return significant_digits;
  }

  void main()
  {
   short significant_digits,index;
   char hex_value[8];
   char binary_value[32];
   /*
    * Do the hex conversion first
    */
   significant_digits=decimal2hex(0x0123FEDC,hex_value);
   printf("0x0123FEDC = 0x");
   /*
    * If you want leading zeros use
    * for(index=8;index>=0;index--)
    */
   for(index=significant_digits;index>=0;index--)
    printf("%c",hex_value[index]);
   /*
    * Do the binary conversion next
    */
   significant_digits=decimal2binary(0x0123FEDC,binary_value);
   printf(" = 0b");
   /*
    * If you want leading zeros use
    * for(index=31;index>=0;index--)
    */
   for(index=significant_digits;index>=0;index--)
    printf("%c",binary_value[index]);
   printf("\n");
  }

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/25/2002 at 11:18:29
From: Bill
Subject: Explanation of C++ Program to Convert Decimal to Binary

I don't really understand how these functions work. Is there any 
chance that you might provide a walk-through explanation?

Thanks!

Date: 12/15/2002 at 03:19:56
From: Doctor Jeremiah
Subject: Re: Explanation of C++ Program to Convert Decimal to Binary

Hi Bill,

In the function decimal2binary() I pass a decimal value as a long and 
a buffer of 32 characters for the binary value. The reason I pass a 
string for the binary value is arbitrary but it makes it easy to print 
a value with many digits. The reason the string is 32 digits long is 
that an signed long can store positive values from 0 to (2^31)-1. The 
value (2^31)-1 in binary is 31 ones. So if we wanted to store (2^31)-1 
we would need 31 places and then an extra for the NULL character, 
which makes 32 in all.

The next thing I do is a loop of 32 times. In each iteration I strip 
off one of the binary digits. The way a decimal number is converted to 
binary is to divide the decimal number by a power of 2 and then keep 
the integer part as a binary digit, and the remainder becomes a 
smaller binary number.

For example:

  The number 93 is 1011101 in binary. So if we were to divide
  the number 93 by 2^6 (which is 64) we would get 1 with a
  remainder of 93-2^6 (which is 29).  This means that the binary
  digit in the seventh place is a 1 and we can convert 29 to
  binary to fill in the first 6 places.

So, if we do all the steps to convert 93 to binary it would look like 
this:

  93/2^6 = 1 remainder 29                   digit = 1
  29/2^5 = 0 remainder 29                   digit = 0
  29/2^4 = 1 remainder 13                   digit = 1
  13/2^3 = 1 remainder 5                    digit = 1
   5/2^2 = 1 remainder 1                    digit = 1
   1/2^1 = 0 remainder 1                    digit = 0
   1/2^0 = 1 remainder 0                    digit = 1

At this point we can see the binary number with the leftmost digit at 
the top and the rightmost digit at the bottom. But in the program I 
don't know that I should start with 2^6 and so I start with 2^31. The 
only difference that makes is that I get lots of leading zeros.

The completely optional part is the significant_digits stuff. That is 
there so that I can return the length of the binary number. I also end 
the string with a NULL character so really you don't need the return 
value at all because you could just do a strlen() on the binary 
number.

To convert binary numbers to decimals is a bit more complicated. I 
didn't include that in the archived answer. Basically what you do is 
to take the rightmost binary digit and multiply it by 2^0, take the 
second rightmost and multiply it by 2^1 and so on until you get to the 
leftmost digit.

Hex is just a number system where every four binary digits get a 
hexadecimal symbol. Basically it goes like this:

If we had the decimal number 93 then the binary number would be 
01011101 and we could write down the hex value just be looking at the 
binary value:

            binary         0101 1101
            BCD              5   13
            hexadecimal      5    D

So the hexadecimal value is 5D.

But in the decimal2hex() function I do it the same way as converting 
to binary. Same algorithm, different constant. Instead of dividing by 
2^n (which makes sense for binary because binary is base 2 and the 
base of the exponent is 2), for hexadecimal I use 16^n (which makes 
sense for hex because hex is base 16 and the base of the exponent is 
16).

So for 93 we could do this:

  93/16^1 =  5 remainder 13                 digit = 5
  13/16^0 = 13 remainder 0                  digit = D (13)

At this point we can see the hex number with the leftmost digit at the 
top and the rightmost digit at the bottom. But in the program I don't 
know that I should start with 2^1 and so I start with 2^7. The only 
difference that makes is that I get lots of leading zeros.

The way I get 16 for the base is  "1<<(index<<2)"  which is equivalent 
to 2^(index*4) but 2^(index*4) is the same as (2^4)^index, which 
equals 16^index.

Then I take the value that is returned and I decide if it is bigger 
than 9 (which would make it alphabetic) or not (in which case it's 
numeric) and then I add an appropriate character to the hex string.

The reason I use the left shifts is that I didn't want to use the math 
library. Engaging the floating point processor just makes the program 
slow, so if you can do it with integers, that is the thing to do.

Let me know if you need more in-depth explanation or if you have 
specific questions I can answer about these examples.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/
    

Date: 02/06/2004 at 09:43:27
From: Amit
Subject: recursive version of conversion?

Hello Doctor Jeremiah,

I saw your Decimal to Binary conversion.  The program is bit difficult 
for me to understand.  Could you please show the same conversion using
recursion? 

Thank you,
Amit

Date: 02/06/2004 at 22:07:14
From: Doctor Jeremiah
Subject: Re: recursive version?

Hi Amit,

Personally I think the iterative version is more intuitive. Generally 
recursive versions are harder to read and not as easy to understand.  
However, if I were going to write a recursive version it would look 
like this:

  // when we convert decimal to binary we always work left to
  // right and pull off the larger binary digits first.  The
  // reason for this is that dividing by a sufficiently large
  // power of two will give uw a single binary digit.

  void recurse(long count,char binary[32], long decimal)
  {
    // 0 through 31 are valid; -1 isn't
    if(count<0)return;
    // binary[31-count] is used because position 31 is at the left
    // (1<<count) is the same as 2 with an exponent of count
    binary[31-count] = decimal/(1<<count)?'1':'0';
    // modify decimal: it must not contain the digit we just extracted
    decimal%=(1<<count);
    // and then call recurse
    recurse(count-1,binary,decimal); 
  }

  void main(int argc, char *argv[])
  {
    // size of string is 33: positions 0 through 31 plus the NULL
    char binary[32+1] = {0};
    // am assuming here that we always get a command line parameter
    long decimal = atoi(argv[1]);
    // start at position 31 and pull off larger digits first
    recurse(31,binary,decimal);
    // print the binary value
    printf("%s",binary);
  }

I hope this helps.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/