How to convert large integer number to binary?

Question

Sorry for a possible duplicate post, I saw many similar topics here but none was exactly I needed. Before actually posting a question I want to explicitly state that this question is NOT A HOMEWORK.

So the question is: how to convert a large integer number into binary representation? The integer number is large enough to fit in primitive type (Java long cannot be used). An input might be represented as a string format or as an array of digits. Disclaimer, This is not going to be a solution of production level, so I don't want to use BigInteger class. Instead, I want to implement an algorithm.

So far I ended up with the following approach: Input and output values represented as strings. If the last digit of input is even, I prepend the output with "0", otherwise - with "1". After that, I replace input with input divided by 2. I use another method - divideByTwo for an arithmetical division. This process runs in a loop until input becomes "0" or "1". Finally, I prepend input to the output. Here's the code:

Helper Method

/**
* @param s input integer value in string representation
* @return the input divided by 2 in string representation
**/
static String divideByTwo(String s)
{
    String result = "";
    int dividend = 0;
    int quotent = 0;
    boolean dividendIsZero = false;

    while (s.length() > 0)
    {
        int i = 1;          
        dividend = Character.getNumericValue(s.charAt(0));

        while (dividend < 2 && i < s.length())
        {
            if (dividendIsZero) {result += "0";}
            dividend = Integer.parseInt(s.substring(0, ++i));
        }

        quotent = dividend / 2;
        dividend -= quotent * 2;            
        dividendIsZero = (dividend == 0);

        result += Integer.toString(quotent);
        s = s.substring(i);

        if (!dividendIsZero && s.length() != 0)
        {
            s = Integer.toString(dividend) + s;
        }
    }
    return result;      
}

Main Method

/**
* @param s the integer in string representation
* @return the binary integer in string representation
**/
static String integerToBinary(String s)
{
    if (!s.matches("[0-9]+"))
    {
        throw new IllegalArgumentException(s + " cannot be converted to integer");
    }

    String result = "";
    while (!s.equals("0") && !s.equals("1"))
    {
        int lastDigit = Character.getNumericValue(s.charAt(s.length()-1));
        result = lastDigit % 2 + result; //if last digit is even prepend 0, otherwise 1
        s = divideByTwo(s);
    }
    return (s + result).replaceAll("^0*", "");
}

As you can see, the runtime is O(n^2). O(n) for integerToBinary method and O(n) for divideByTwo that runs inside the loop. Is there a way to achieve a better runtime? Thanks in advance!

Answer 1

In wikipedia, it is said:

For very large numbers, these simple methods are inefficient because they perform a large number of multiplications or divisions where one operand is very large. A simple divide-and-conquer algorithm is more effective asymptotically: given a binary number, it is divided by 10^k, where k is chosen so that the quotient roughly equals the remainder; then each of these pieces is converted to decimal and the two are concatenated. Given a decimal number, it can be split into two pieces of about the same size, each of which is converted to binary, whereupon the first converted piece is multiplied by 10^k and added to the second converted piece, where k is the number of decimal digits in the second, least-significant piece before conversion.

I have tried, this method is faster than conventional one for numbers larger than 10,000 digits.

Answer 2

Among the simple methods there are two possible approaches (all numbers that appear here decimal)

1. work in decimal and divide by 2 in each step as you outlined in the question
2. work in binary and multiply by 10 in each step for example 123 = ((1 * 10) + 2) * 10 + 3

If you are working on a binary computer the approach 2 may be easier.

See for example this post for a more in-depth discussion of the topic.

Answer 3

Try this:

new BigDecimal("12345678901234567890123456789012345678901234567890").toString(2);

Edit:

For making a big-number class, you may want to have a look at my post about this a week ago. Ah, the question was by you, never mind.

The conversion between different number systems in principle is a repeated "division, remainder, multiply, add" operation. Let's look at an example:

We want to convert 123 from decimal to a base 3 number. What do we do?

Take the remainder modulo 3 - prepend this digit to the result.
Divide by 3.
If the number is bigger than 0, continue with this number at step 1

So it looks like this:

123 % 3 == 0. ==> The last digit is 0.
123 / 3 == 41.
41 % 3 == 2 ==> The second last digit is 2.
41 / 3 == 13
13 % 3 == 1 ==> The third digit is 1.
13 / 3 == 4
4 % 3 == 1 ==> The fourth digit is 1 again.
4 / 3 == 1
1 % 3 == 1 ==> The fifth digit is 1.

So, we have 11120 as the result.

The problem is that for this you need to have already some kind of division by 3 in decimal format, which is usually not the case if you don't implement your number in a decimal-based format (like I did in the answer to your last question linked above).

But it works for converting from your internal number format to any external format.

So, let's look at how we would do the inverse calculation, from 11120 (base 3) to its decimal equivalent. (Base 3 is here the placeholder for an arbitrary radix, Base 10 the placeholder for your internal radix.) In principle, this number can be written as this:

1 * 3^4 + 1 * 3^3 + 1*3^2 + 2*3^1 + 0*3^0

A better way (faster to calculate) is this:

((((1 * 3) + 1 )*3 + 1 )*3 + 2)*3 + 0 1 3 4 12 13 39 41 123 123

(This is known as Horner scheme, normally used for calculating values of polynomials.)

You can implement this in the number scheme you are implementing, if you know how to represent the input radix (and the digits) in your target system.

(I just added such a calculation to my DecimalBigInt class, but you may want to do the calculations directly in your internal data structure instead of creating a new object (or even two) of your BigNumber class for every decimal digit to be input.)