Binary String to Decimal String

Good afternoon,

How would you go about converting to a decimal string a binary string with more characters than bits in a language's largest integer type? In other words, supposing that you have the string

1110011开发者_如何学编程01001110100100(...)1001001111011100100

and that you can't convert it to an integer first, how would you go about writing it in base 10?

Thank you very much.

You can use an algorithm like:

// X is the input
while ( X != "0" )
  compute X' and R such that X = 10 * X' + R  (Euclidean division, see below)
  output R    // least significant decimal digit first
  X = X'

The Euclidean division of X by 10 is computed like this:

R = 0  // remainder in 0..9
X' = ""
for (b in bits of X)  // msb to lsb
  R = 2*R + b
  if R >= 10
    X' += "1"
    R -= 10
  else
    X' += "0"

Remove leading "0" from X'
The remainder is R in 0..9

Write your own arithmetic in base 10. Only addition is needed. Example implementation in Python:

from math import log, ceil

def add(a, b):
    """Add b to a in decimal representation."""
    carry = 0
    for i in range(len(b)):
        carry, a[i] = divmod(a[i] + b[i] + carry, 10)
    while carry:
        i += 1
        carry, a[i] = divmod(a[i] + carry, 10)

# an example string
s = bin(3 ** 120)[2:]

# reserve enough decimal digits
res = [0] * int(ceil(len(s) * log(2) / log(10)))

# convert
for c in s:
    add(res, res)
    if c == "1":
        add(res, [1])

#print output
print str.join("", map(str, reversed(res)))

This uses lists of intergers to represent numbers in base 10. The list items correspond to the digits of the base 10 number. The item at index 0 corresponds to the ones, the item at index 1 to the tens, and so on.

10 is not a power of 2, thus a digit at any place of a binary representation may affect the least significant digit in the decimal representation. You have to store the entire decimal representation to transform the bit string.

If you can't find a long decimal data class / library for your language, you can construct it yourself, it's not hard. Just store enough decimal digits, e.g. as a list, and do the math. You only need addition for this task, so it's extra easy to implement.

I'd use an arbitrary precision numeric (bignum) library, like GMP.

GMP has a "gmp_scanf" function that does just what you are asking for.

Assuming that you do not have an arbitrary precision math package at your disposal, but you do have a set of basic string manipulation routines, you could do the following:

Construct a list of powers of 2 then deconstruct the binary string in reverse order one bit at a time by adding in the appropriate power of 2 for every '1' bit in the string.

The only arbitrary precision arithmetic function you need to do this is addition, and this is fairly easy to implement using long-hand arithmetic.

Suppose you did implement an arbitrary arithmetic add function called: ADD taking 2 strings containing decimal numbers as input and returning the decimal sum as a string. Something like:

  SumString = ADD(DecimalString1, DecimalString2)

SumString is a string of decimal digits representing the sum of DecimalString1 and DecimalString2.

Step1: Construct a powers of 2 list as follows:

  BitString is string           /* String of '1' and '0' values... */
  BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */

  PowerOf2 is array of string  /* Array of strings containing powers of 2 */
  PowerOf2[1] = '1'            /* 2**0 to get things started... */
  /* Build as many powers of 2 as there are 'bits' in the input string */   
  for i from 2 to length(BitString) by +1  
    PowerOf2[i] = ADD(PowerOf2[i-1], PowerOf2[i-1])  
    end 

Note: Above assumes arrays/strings are 1 based (as opposed to zero based).

Step 2: Deconstruct the BitString accumulating the sum as you go:

  DecimalValue is string        /* Decimal value of BitString */
  BitString is string           /* Your input set of bits as a string... */
  ReverseBitString is string    /* Reversed input */

  DecimalValue = ''             /* Result */  
  BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */  
  ReverseBitString = reverse(BitString) /* Reverse so we process lsb to msb */  

  for i from 1 to length(ReverseBitString) by +1  
     if substr(ReverseBitString, i, 1) == '1' then  /* Bit at position i */  
        DecimalValue = ADD(DecimalValue, PowerOf2[i])  
        end   
     end    

  if DecimalValue = '' then DecimalValue = '0' /* bit string was all zero */   
  Display DecimalValue /* This is the result */  

How to build an arbitrary precision ADD function? It goes something like:

  function ADD (DecVal1 is string, DecVal2 is string) return string  
     SumVal is string   
     Rev1 is string  
     Rev2 is string      
     DigitSum is integer
     CarryDigit is integer

     SumVal = ''               /* Result so far... */
     Rev1 = reverse(DecVal1)   /* Reverse digit order */
     Rev2 = reverse(DecVal2)   /* Reverse digit order */

     /* Pad shorter reversed sting with trailing zeros... */
     if length(Rev1) > length(Rev2) then
        Rev2 = concat(Rev2, copies(length(Rev1) - length(Rev2), '0')
        end
     else
        Rev1 = concat(Rev1, copies(length(Rev2) - length(Rev1), '0')
        end

     /* Sum by digit position, least to most significant */
     CarryDigit = 0    
     for i from 1 to length(Rev1) by + 1
        DigitSum = CtoI(substr(Rev1, i, 1)) + CtoI(substr(Rev2, i, 1)) + CarryDigit
        if DigitSum > 9 then
           DigitSum = DigitSum - 10
           CarryDigit = 1
           end
        else
           CarryDigit = 0
           end 

        SumVal = concat(ItoC(DigitSum), SumVal)
        end

      if CarryDigit > 0 then
        SumVal = concat(ItoC(CarryDigit), SumVal)
        end

      return SumVal  

Assumed built in string functions:

• reverse(String): Returns the string in reverse order
• length(String): Returns length of a given string
• concat(String, String): Returns concatenation of two strings
• substr(String, start, length): Returns substring of string from start for length characters (1 based)
• CtoI(String): Returns decimal integer value of given character (eg. '1' = 1, '2' = 2, ...)
• ItoC(Integer): Returns decimal character representation of integer (eg. 1 = '1', 2 = '2', ...)
• copies(count, string): Returns count concatinated copies of string

Here you go...

void toBCD1( char *p ) {
    const int decSize = 120; // Arbitrary limit of 10^119.
    static binByte decDgt[ decSize ]; // decimal digits as binary 'nibbles'.
    int curPow10 = 0;

    memset( decDgt, 0, sizeof(decDgt) );

    for( char *cp = p; *cp; cp++ ) {

        for( int ii = curPow10; ii >= 0; ii-- ) {
            if( decDgt[ ii ] >= 5 ) // Algorithm step
                decDgt[ ii ] += 3;

            decDgt[ ii ] <<= 1;

            if( decDgt[ ii ] & 0x10 ) { // Carry high bit?
                decDgt[ ii + 1 ] |= 0x1;
                if( ii == curPow10 ) // new power of 10?
                    curPow10++;
                decDgt[ ii ] &= 0xF; // dealing in 'nibbles'
            }
        }
        decDgt[ 0 ] |= ( *cp == '1' ); // truth value 0 or 1
    }
    for( int ii = curPow10; ii >= 0; ii-- )
        putchar( decDgt[ ii ] + '0' );
    putchar( '\n' );
}

void demo_toBCD( void ) {
    char *bp =  "11100110"
                "10011101"
                "00100100"
                "10011110"
                "11100100"
                "01001001"
                "11101110"
                "01000100"
                "10011110"
                "11100100";
    toBCD1( bp );
}