0

Никак не могу найти алгоритм, только обратный нашел Перевод в двоичную систему счисления больших чисел

3
  • 2
    Переведите в BCD с помощью "дабл дабл", в нем на каждую деятичную цифру полбайта. потом уже раздвиньте до нужного представления. en.wikipedia.org/wiki/Double_dabble Обратите внимание, сдвиги там чаще чем прибавление, так что можно двигать небольшую часть исходного числа, вовремя подхватывая новые байты. Только при add 3 придется подумать как перенос делать (который то же можно было бы накапливать что бы не проводить его постоянно по всему числу. С другой стороны перенос все равно на первом же 0 бите остановится
    – Mike
    11 апр 2017 в 21:45
  • Алгоритм такой: делим число на 10 получаем остаток и целый результат. остаток деления (от '0' до '9') записываем вначало строки. Если целый результат деления больше 0, повторяем операцию.
    – nick_n_a
    12 апр 2017 в 7:51
  • 1
    @Mike: алгоритм похоже для чисел, которые в регистре помещаются (в железе реализовать). Для больших чисел возможно лучше "разделяй и властвуй" sub-quadratic подход из GMP использовать
    – jfs
    13 апр 2017 в 13:46

2 ответа 2

1

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

С практической точки зрения, делить длинное число на 10 - не лучший вариант. Лучше использовать промежуточную систему счисления (например, по основанию 1 000 000 или 1 000 000 000), что сокращает количество "длинных" делений.

2
1

Алгоритм приходит легко, если понимать запись двоичного числа. Например, рассмотрим двоичное число ниже:

введите сюда описание изображения

В десятичной форме оно будет выглядеть так:

dec_num = 2^0 + 2^5 + 2^7 = 161

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

На каждой итерации нашего алгоритма мы должны знать:

1)позицию элемента(в общем-то это есть значение нашего счётчика цикла)

2)цифру числа в данной позиции

Чтобы узнать последнюю цифру числа достаточно взять остаток от деления по модулю 10(операция bin_num%10). Но как тогда узнать предпоследнюю? Очень просто! Достаточно модифицировать наше бинарное число в конце каждой итерации следующим образом bin_num/=10. Применяя эту операцию, мы как бы сдвигаем число вправо, делая его предпоследнюю цифру последней, чтобы операция bin_num%10 давала нужный результат.

введите сюда описание изображения

Надеюсь этих рассуждений достаточно, чтобы найти верное решение:)

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.