Как преобразовать большое целое число в двоичный файл?

Question

Извините за возможный двойной пост, я видел много подобных тем здесь, но ни одна не была точно мне нужна. Перед тем, как отправлять вопрос, я хочу прямо заявить, что этот вопрос НЕ РАБОТАЕТ.

Итак, вопрос: как преобразовать большое целое число в двоичное представление? Целое число достаточно велико, чтобы вписаться в примитивный тип (Java долго не может использоваться). Входные данные могут быть представлены в виде строкового формата или в виде массива цифр. Отказ от ответственности, это не будет решением производственного уровня, поэтому я не хочу использовать класс BigInteger. Вместо этого я хочу реализовать алгоритм.

До сих пор я использовал следующий подход: входные и выходные значения представлены в виде строк. Если последняя цифра ввода четная, я добавляю вывод к "0", в противном случае - к "1". После этого я заменяю ввод на вход, разделенный на 2. Я использую другой метод - divByTwo для арифметического деления. Этот процесс выполняется в цикле, пока на входе не появится "0" или "1". Наконец, я добавляю ввод к выводу. Вот код:

Вспомогательный метод

/**
* @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;      
}

Основной метод

/**
* @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*", "");
}

Как видите, время выполнения равно O(n^2). O(n) для метода integerToBinary и O (n) для метода divByTwo, который выполняется внутри цикла. Есть ли способ добиться лучшего времени выполнения? Заранее спасибо!

Answer 1

Попробуй это:

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

Редактировать:

Для создания класса с большим числом, вы можете посмотреть мой пост об этом неделю назад. Ах, вопрос был у вас, неважно.

Преобразование между различными системами счисления в принципе является повторяющейся операцией "деление, остаток, умножение, сложение". Давайте посмотрим на пример:

Мы хотим преобразовать 123 из десятичного в базовое число 3. Что мы делаем?

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

Так это выглядит так:

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.

Итак, у нас есть 11120 в результате.

Проблема в том, что для этого вам нужно иметь какое-то деление на 3 в десятичном формате, что обычно не происходит, если вы не реализуете свое число в десятичном формате (как я сделал в ответе на ваш последний вопрос связан выше).

Но он работает для преобразования из вашего внутреннего формата чисел в любой внешний формат.

Итак, давайте посмотрим, как мы будем делать обратный расчет, от 11120 (основание 3) до его десятичного эквивалента. (База 3 является здесь заполнителем для произвольного радиуса, База 10 - заполнителем для вашего внутреннего радиуса.) В принципе, это число можно записать так:

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

Лучший способ (быстрее рассчитать) заключается в следующем:

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

(Это известно как схема Хорнера, обычно используемая для вычисления значений полиномов.)

Вы можете реализовать это в числовой схеме, которую вы реализуете, если вы знаете, как представить входной радиус (и цифры) в вашей целевой системе.

(Я только добавил такой расчет в мой класс DecimalBigInt, но вы можете захотеть выполнять вычисления непосредственно в вашей внутренней структуре данных вместо создания нового объекта (или даже двух) из вашего класса BigNumber для каждой десятичной цифры, которую нужно ввести.)

Answer 2

Среди простых методов есть два возможных подхода (все числа, которые появляются здесь, десятичные)

1. работать в десятичном формате и делить на 2 на каждом шаге, как вы обрисовали в общих чертах в вопросе
2. работать в двоичном и умножить на 10 на каждом шаге, например 123 = ((1 * 10) + 2) * 10 + 3

Если вы работаете на двоичном компьютере, подход 2 может быть проще.

Смотрите, например, этот пост для более глубокого обсуждения темы.

Answer 3

В википедии сказано:

Для очень больших чисел эти простые методы неэффективны, поскольку они выполняют большое количество умножений или делений, когда один операнд очень велик. Простой алгоритм «разделяй и властвуй» асимптотически более эффективен: при заданном двоичном числе оно делится на 10 ^ k, где k выбирается так, чтобы частное примерно равнялось остатку; затем каждая из этих частей преобразуется в десятичную, и они объединяются. Если задано десятичное число, его можно разделить на две части примерно одинакового размера, каждую из которых преобразовать в двоичную, после чего первую преобразованную часть умножить на 10^k и прибавить ко второй преобразованной части, где k — число десятичных цифр во второй, наименее значащей части перед преобразованием.

Я пробовал, этот метод быстрее обычного для чисел больше 10000 цифр.