конвертировать очень большой int (записанный в виде строки) в двоичную строку в c / Stack Overflow
У меня есть номер в базе 10, которая имеет около 10 тыс. Цифр. Я хочу преобразовать его в базу 2 (1010101001 …). Все, что я могу думать, это примитивный алгоритм:
take last digit mod 2 -> write down bit
number divide by 2;
Это не должно быть трудно реализовать начальное школьное разделение на строку, но я думаю, что это очень неэффективно. Если я прав, это будет O(l^2), где l означает длину числа в базе 10. Это можно сделать быстрее?
Решение
Из того, что я понимаю, ваше большое число представлено в виде последовательности десятичных цифр. Если это так, вы можете вычислить «двоичное» представление, используя умножение и сложение:
значение = сумма (я в 0 … n-1) 10я * цифрая
Это вычисление может быть разбито на части по принципу «разделяй и властвуй», хотя я не уверен, что вы можете прийти к алгоритму O (n log n).
Другие решения
Если вы работаете с большими числами, я действительно рекомендую вам использовать библиотеку с высокой точностью. Попробуйте GMP или MPRF или что-то подобное.
-Øystein
Деление на 2 аналогично умножению на 1/2. Для последнего вы можете использовать некоторые из хорошо известных алгоритмов быстрого умножения (Toom – Cook, Schönhage – Strassen и т. Д.).
detector