Decimal/Binary Conversion Using “Deci-Binary”

I read about an interesting method for decimal/binary conversion in chapter two of Gerald R. Rising’s book “Inside Your Calculator”. Unlike the standard string-oriented conversion algorithms, the algorithms in his book perform arithmetic on an encoding I’ve dubbed “deci-binary”. Using this encoding, binary numbers are input and output as decimal strings consisting of only ones and zeros, exploiting built-in language facilities for decimal input and output. I will demonstrate this conversion process with Java code I have written.

This Method Is Not Practical

Let me say at the outset that you will not use the deci-binary based method in practice. Unless you implement it with big integers, it can convert only small numbers. Also, there are built-in functions — particularly in Java — that will do decimal/binary conversion for you. In any case, I find the method interesting, so I wanted to discuss it.

Traditional String-Based Conversion Algorithms

For our purposes, decimal/binary conversion entails converting a decimal string to a binary string and vice versa. For decimal to binary conversion, you want to input a decimal number and output a binary number; for binary to decimal conversion, you want to input a binary number and output a decimal number. (We will deal only with integers.)

Traditionally, for decimal to binary conversion, you first convert the decimal string to numeric binary (e.g., integer type) through the programming language, either by using a decimal literal (e.g., long num = 133;) or a function call (e.g., in C, scanf() or sscanf(); e.g., in Java, nextLong() or Long.parseLong()). Then you use arithmetic to convert the numeric binary value to a binary string, one bit at a time.

For binary to decimal conversion, you first convert the binary string to numeric binary by reading each bit from the string and building up the numeric binary value. Then you convert the numeric binary value to a decimal string with a function call — for example, printf() in C or System.out.println() or Long.toString() in Java.

(If you want more detail on how traditional decimal/binary conversion works, see my article Base Conversion in PHP Using BCMath, sections dec2bin_i() and bin2dec_i(). Don’t get confused though — just focus on the algorthmic details; the code in that article actually does everything with strings.)

Here is Java code I wrote to demonstrate this traditional method (the ‘_i’ suffix indicates that the conversion applies only to integers):

import java.util.Scanner;

public class ConversionUsingString {
    public static String dec2bin_i (String dec) {
        long number = Long.parseLong(dec);
        String dig;
        String bin = "";
		
        while (number > 0) {
           if (number % 2 == 1)
              dig = "1";
           else
              dig = "0";
           bin = dig + bin;
           number /= 2;
        }
        return bin;
    }
	
    public static String bin2dec_i (String bin) {
        long number = 0;
        int dig;
        
        for (int i = 0; i < bin.length(); i++){
            dig = bin.charAt(i) - '0';
            number = 2 * number + dig;
        }
        return Long.toString(number);
    }
	
    public static void main(String[] args) {
    	String dec;
    	String bin;
        Scanner in = new Scanner(System.in);
		
        System.out.println("Enter a decimal integer");
        dec = in.next();
        bin = dec2bin_i(dec);
        System.out.println("Converted to binary: " + bin);
        
        System.out.println("Enter a binary integer");
        bin = in.next();
        dec = bin2dec_i(bin);
        System.out.println("Converted to decimal: " + dec);
        
        in.close();
    }
}

Deci-Binary Based Conversion Algorithms

For deci-binary based decimal to binary conversion, you first convert the decimal string to numeric binary through the programming language, as we did for the traditional method. Then you use arithmetic to convert the numeric binary value to numeric deci-binary. You do this by repeatedly dividing by two to get the next bit and multiplying that bit by the appropriate power of ten for that position. Finally, you convert the numeric deci-binary to a deci-binary string with a programming language function.

For deci-binary based binary to decimal conversion, you first convert the deci-binary string to numeric deci-binary through the programming language. Then you use arithmetic to convert the numeric deci-binary value to numeric binary: you repeatedly divide by ten to get the next decimal digit and multiply that digit (0 or 1) by the appropriate power of two for that position. Finally, you convert the numeric binary value to a decimal string with a programming language function.

Here is Java code I wrote to demonstrate this deci-binary based method:

import java.util.Scanner;

public class ConversionUsingDeciBinary {
    public static String dec2bin_i (String dec) {
        long number = Long.parseLong(dec);
        long bin = 0;
        long po10 = 1;
        long dig;
        
        while (number > 0) {
           dig = number % 2;
           bin += dig * po10;
           number /= 2;
           po10 *= 10;
        }
        return Long.toString(bin);
    }
	
    public static String bin2dec_i (String bin) {
        long number = Long.parseLong(bin);
        long dec = 0;
        long po2 = 1;
        long dig;
		
        while (number > 0) {
           dig = number % 10;
           dec += dig * po2;
           number /= 10;
           po2 *= 2;
        }
        return Long.toString(dec);
    }
	
    public static void main(String[] args) {
    	String dec;
    	String bin;
        Scanner in = new Scanner(System.in);
		
        System.out.println("Enter a decimal integer");
        dec = in.next();
        bin = dec2bin_i(dec);
        System.out.println("Converted to binary: " + bin);
        
        System.out.println("Enter a binary integer");
        bin = in.next();
        dec = bin2dec_i(bin);
        System.out.println("Converted to decimal: " + dec);
        
        in.close();
    }
}

The Deci-Binary Encoding Is Too Inefficient

The main problem with the deci-binary method is that the encoding is too inefficient; it takes large decimal integers to represent small binary integers. Even using longs, which are 64-bit signed integers, the maximum binary number we can represent is 19 bits: 2¹⁹ – 1 = 1111111111111111111 = 524287. This means the maximum input to bin2dec_i() is 1111111111111111111 and the maximum input to dec2bin_i() is 524287. The maximum using ints, which are 32-bit signed integers, is 2¹⁰ – 1 = 1111111111 = 1023.

Contrast this with the traditional string-based method, which gives you up to 2⁶³ – 1 = 111111111111111111111111111111111111111111111111111111111111111 = 9223372036854775807 for longs, and for ints, 2³¹ – 1 = 1111111111111111111111111111111 = 2147483647.

Deci-Binary Based Conversion Using Big Integers

Deci-binary conversions will work for any-sized integer, as long as you’re willing to use arbitrary-precision arithmetic. Here is my deci-binary code rewritten to use the BigInteger type:

import java.util.Scanner;
import java.math.BigInteger;

public class ConversionUsingDeciBinaryBigInt {
    public static String dec2bin_i (String dec) {
    	BigInteger number = new BigInteger(dec);
    	BigInteger bin = new BigInteger("0");
    	BigInteger po10 = new BigInteger("1");
    	BigInteger dig = new BigInteger("0");
    	BigInteger zero = new BigInteger("0");
    	BigInteger two = new BigInteger("2");
    	BigInteger ten = new BigInteger("10");
        
        while (number.compareTo(zero) > 0)  {
           dig = number.remainder(two);
           bin = bin.add(dig.multiply(po10));
           number = number.divide(two);
           po10 = po10.multiply(ten);
        }
        return bin.toString();
    }
	
    public static String bin2dec_i (String bin) {
    	BigInteger number = new BigInteger(bin);
    	BigInteger dec = new BigInteger("0");
    	BigInteger po2 = new BigInteger("1");
    	BigInteger dig = new BigInteger("0");
    	BigInteger zero = new BigInteger("0");
    	BigInteger two = new BigInteger("2");
    	BigInteger ten = new BigInteger("10");
    	
        while (number.compareTo(zero) > 0)  {
           dig = number.remainder(ten);
           dec = dec.add(dig.multiply(po2));
           number = number.divide(ten);
           po2 = po2.multiply(two);
        }
        return dec.toString();
    }
	
    public static void main(String[] args) {
    	String dec;
    	String bin;
        Scanner in = new Scanner(System.in);
		
        System.out.println("Enter a decimal integer");
        dec = in.next();
        bin = dec2bin_i(dec);
        System.out.println("Converted to binary: " + bin);
        
        System.out.println("Enter a binary integer");
        bin = in.next();
        dec = bin2dec_i(bin);
        System.out.println("Converted to decimal: " + dec);
        
        in.close();
    }
}

One Line Conversions Using Built-In Functions

We did the conversions above by hand for “fun”. But as I mentioned in the introduction, you’d be better served using existing functions. Java has built-in methods that convert to and from binary strings directly. For example, you can implement dec2bin_i() as

    public static String dec2bin_i (String dec) {
        return Long.toBinaryString(Long.parseLong(dec));
    }

or with BigIntegers,

    public static String dec2bin_i (String dec) {
        return new BigInteger(dec).toString(2);
    }

You can implement bin2dec_i() as

    public static String bin2dec_i (String bin) {
    	return Long.valueOf(Long.parseLong(bin,2)).toString();
    }