Funnily, today I had the opposite task - converting long binary strings to their decimal representation, and again, not wanting to get involved in BigInt libraries, I looked for a simple solution.

So here's a solution I found that works nicely, is simple and efficient enough and doesn't require usage of heavy libraries (the code is Perl, but I first did in in C++ because that's where I needed it):

# Calculate a (arbitrarily large) decimal number from its # binary representation # sub bin2dec { my ($str) = @_; my $ret = ""; $ret = mul2($ret, $_) foreach split(//, $str); return $ret; } # Given a (arbitrarily large) decimal number N as a string, # returns 2N or 2N+1 # sub mul2 { my ($str, $add_one_f) = @_; defined($add_one_f) or $add_one_f = 0; my $ret = ""; foreach (my $i = length($str) - 1; $i >= 0; --$i) { my $c = substr($str, $i, 1) * 2; $c += 1 if ($add_one_f); $ret = ($c % 10) . $ret; $add_one_f = ($c >= 10); } return $add_one_f ? '1' . $ret : $ret; }

While converting between arbitrary bases can be difficult, converting from binary to decimal isn't. That's because the maximal carry from a multiplication of a digit by 2 is 1, even when a carry of 1 is added (9 * 9 + 1 = 19, that's 9, carry 1). So the `mul2` routine does just that: multiplies a decimal number given as a string by 2.

With this in hand, `bin2dec` becomes simple. Observe that if you traverse a binary number from msb to lsb, for each bit you only have to multiply the result by 2, and add 1 if that bit is 1. Try it ! That's what bin2dec does - and successfully converts binary numbers of any length to decimals.

I also started a Perlmonks thread about it here where I got some interesting responses and suggestions.

## Comments

comments powered by Disqus