ADT Целочисленные вопросы класса
Я довольно новичок в программировании, и мне нужно сделать абстрактный тип данных (ADT) для целых чисел.
Я просмотрел в Интернете несколько советов, примеров, учебных пособий, но не смог найти ничего полезного, поэтому надеюсь, что получу здесь несколько ответов.
Я много думал о том, как мне отформатировать ADT, в котором хранится мое целое число, и я думаю о чем-то вроде этого:
int lenght; // stores the length of the number(an limit since this numbers goes to infinite)
int[] digits; // stores the digits of my number, with the dimension equal to length
Теперь я запутался в том, как мне следует заняться представлением знака. Можно ли держать знак в char something лайк: char sign?
Но тогда возникает вопрос, что делать, когда мне нужно сложить и умножить два целых числа, как насчет случаев, когда у меня возникают переполнения в этих операциях.
Итак, если у некоторых из вас есть идеи о том, как мне представить число (формат) и как мне сделать умножение и сложение, я был бы очень хорош. Мне не нужен код, я на стадии обучения, только некоторые идеи. Спасибо.
Решение
Хороший способ сделать это — хранить знак как bool (например, bool is_neg;). Таким образом, совершенно ясно, что означают эти данные (порок с символом, где не совсем ясно.
Возможно, вы захотите сохранить каждую цифру в коротком без знака (или если вы хотите быть точным в отношении знака, uint16_t). Затем, когда вы умножаете две цифры, вы можете просто умножить их на целые числа без знака (uint32_t), и тогда младшие 16 бит будут вашим результатом, а переполнение — старшими 16 битами. Затем вы можете легко добавить это в массив результатов. Вы знаете, что умножение n-битного числа на k-битное число имеет длину не более n + k битов, поэтому вы можете предварительно распределить массив по этому размеру, а затем позаботиться об удалении лишних нулей.
Надеюсь, это поможет, и дайте мне знать, если вы хотите больше советов.
Другие решения
Первое дизайнерское решение, которое вы должны принять, — это выбор основы.
Вы, кажется, склоняетесь к простой десятичной дроби. Может быть распакован (один полный байт на цифру, числовое представление или представление ASCII) или пары упакованных цифр (десятичное кодированное двоичное число, дважды четыре бита в байте).
Другие схемы более удобны для более быстрых операций: основание, являющееся степенью 2 или степенью 10, вписывающееся в байт, короткое, целое …
Полномочия 10 имеют преимущество в том, что преобразование в основание 10 и обратно может осуществляться слово за словом.
Дополнение легко: добавьте слова попарно и обработайте переносы. То же самое для вычитания, с заимствованиями.
Умножения — это совсем другая история, если вы заботитесь об эффективности. Можно использовать метод письменных вычислений, который преподают в школе, но он требует операций длина 1 x длина 2. Для длинных чисел предпочтительны более эффективные методы (http://en.wikipedia.org/wiki/Multiplication_algorithm#Karatsuba_multiplication). Они также более сложны.