Tags Perl
A few months ago I ran into a need to convert long decimal numbers (stored in a string) to binary representation.

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 powered by Disqus