Как преобразовать массив int, используемый как своего рода BigInteger, в «читаемую человеком» строку? - PullRequest
Новая
       13

Как преобразовать массив int, используемый как своего рода BigInteger, в «читаемую человеком» строку?

2 голосов
/ 17 января 2012

Я пытаюсь реализовать некоторые функции BigInteger s как личное упражнение по программированию.

Как и во многих реализациях, я использую int[] в качестве целого числа без знака.

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

Я чувствую, что застрял.Я не уверен, что мои алгоритмы верны, но у меня нет возможности проверить это.

Я рассмотрел некоторые реализации, такие как Apache Harmony или OpenJDK, но алгоритмы, которые они используют для создания String, выглядят более сложнымичем фактическая реализация плюс, минус, ... и т. д.

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

Может кто-нибудь предложить простую реализацию, которая преобразует int[] в строку?

Пример: new int[]{Integer.MAX_VALUE, 1} должен рассматриваться как один большой, без знакачисло и печать: 8589934590 (так в основном 2³³).

Ответы [ 2 ]

2 голосов
/ 17 января 2012

Я бы использовал этот подход:

  • Вы не упоминаете, как храните ноль; может потребоваться специальная обработка, в этом случае вы можете выполнить специальный случай, прежде чем продолжить работу с остальным алгоритмом.
  • Сделайте копию int[]; назовите это iArr. Остальная часть этого алгоритма будет работать на iArr.
  • Создать char[] & mdash; назовите это s & mdash; это достаточно большой. Поскольку int может содержать до десяти цифр, вы можете использовать s = new char[iArr.length * 10].
  • Начать с позиции int i = s.length - 1. Пройдите через iArr, разделив на десять, и сохраните остаток плюс '0' в s[i]. Затем уменьшите i. Повторяйте этот процесс, пока iArr не станет равным нулю. (Логика деления на десять примерно такова: разделите каждый элемент на десять, отметив остаток. Добавьте этот остаток, умноженный на Integer.MAX_INT + 1, к следующему элементу, прежде чем делить этот элемент на десять. , вам нужно сделать математику, используя long.)
  • Ваш результат new String(s, i, s.length - i).

Для эффективности:

  • Вы можете делить на степень десяти, например, 1000000 или еще что-нибудь, чтобы получить сразу несколько цифр (очевидно, что это делает обработку char более сложной, хотя).
  • Когда вы обнуляете ведущие элементы iArr, вы можете отслеживать, где находится первый ненулевой элемент, и игнорировать любые элементы до этого.

но ни один из них на самом деле не нужен.

Отредактировано для добавления фактического кода. Эта программа: 

public class Main
{
    private static final long RADIX = -2L * (long)Integer.MIN_VALUE;

    public static void main(final String... args)
    {
        System.out.println(stringify(new int[]{0})); // 0
        System.out.println(stringify(new int[]{1})); // 1
        System.out.println(stringify(new int[]{Integer.MAX_VALUE})); // 2^31-1
        System.out.println(stringify(new int[]{Integer.MIN_VALUE})); // 2^31
        System.out.println(stringify(new int[]{-1})); // 2^32-1
        System.out.println(stringify(new int[]{1, 0})); // 2^32
        System.out.println(stringify(new int[]{1, -1})); // 2^33-1
        System.out.println(stringify(new int[]{-1, -1})); // 2^64-1
        System.out.println(stringify(new int[]{1, 0, 0})); // 2^64
    }

    private static String stringify(final int[] _iArr)
    {
        final int[] iArr = new int[_iArr.length];
        System.arraycopy(_iArr, 0, iArr, 0, _iArr.length);
        final char[] ret = new char[10 * iArr.length];
        int retIndex = ret.length;
        while(true)
        {
            boolean isZero = true;
            int carry = 0;
            for(int i = 0; i < iArr.length; ++i)
            {
                long val = unsignedInt2Long(iArr[i]);
                if(val != 0L)
                    isZero = false;
                val += carry * RADIX;
                carry = (int) (val % 10L);
                val /= 10L;
                iArr[i] = long2UnsignedInt(val);
            }
            if(isZero)
            {
                if(retIndex == ret.length)
                    return "0";
                else
                    return new String(ret, retIndex, ret.length - retIndex);
            }
            assert(retIndex > 0);
            ret[--retIndex] = (char) (carry + (int)'0');
        }
    }

    private static long unsignedInt2Long(final int unsignedInt)
    {
        if(unsignedInt >= 0)
            return unsignedInt;
        else
            return unsignedInt + RADIX;
    }

    private static int long2UnsignedInt(final long _long)
    {
        assert(_long >= 0L);
        assert(_long < RADIX);
        if(_long <= (long) Integer.MAX_VALUE)
            return (int) _long;
        else
            return (int) (_long - RADIX);
    }
}

печатает это: 

0
1
2147483647
2147483648
4294967295
4294967296
8589934591
18446744073709551615
18446744073709551616

(Но вам придется изучить метод main с его комментариями, чтобы подтвердить, что я правильно понял, как вы собираетесь хранить эти целые числа.)

1 голос
/ 17 января 2012

Начните с реализации конвертера в гекс, и используйте гекс в качестве вашего удобочитаемого формата на начальных этапах разработки.Делать HEX легко, потому что вам не нужно реализовывать деление: просто преобразуйте отдельные элементы в HEX, склейте их вместе, и все готово.

Как только ваш алгоритм деления будет на месте, вы можете реализовать преобразование в десятичное числоформатировать по обычному подходу «получить остаток% 10 и разделить».

...