Как преобразовать вектор int, представляющий двоичный код, и вектор int, представляющий десятичное число? C ++

Question

Я делаю большую целочисленную библиотеку, и у меня есть вектор STL int, который представляет двоичное число.

двоичный вектор будет содержать {0,0,1,1} и мне нужно, чтобы десятичное представление этого числа было сохранено в другом векторе, как это {2,1}

Что я хочу знать, что было бы лучшим способом сделать это?

Также я не могу использовать такие функции, как pow, потому что это должно работать с большими числами.

Answer 1

Самый прямой способ сделать это - просто сложить десятичное представление каждой степени-2, имитируя десятичное сложение.

Вы можете получить десятичное представление каждой степени-2 итеративно,то есть pow (2, n + 1) = pow (2, n) + pow (2, n).

Таким образом, в принципе, после того, как вы прибили десятичное сложение, все должно быть довольно просто.Это может быть не самый эффективный метод (это O (n ^ 2) по количеству цифр), но он, безусловно, должен работать.

Answer 2

«Искусство компьютерного программирования» Кнута, том 2. является отличным справочником по арифметике произвольной точности.

Простой способ получить представление с основанием 10 - это непрерывно делить число на 10, извлекается каждое делениеодна цифра (остаток).Это, очевидно, требует умения делить на 10 в любой базе, которая у вас уже есть.

Например, если ваш номер 321 десятичный или 101000001 двоичный, мы можем разделить:

10100001 двоичный на 1010 двоичный

100000 с остатком 1 (поэтому первая цифра равна 1 десятичному знаку)

разделите 100000 на 1010 двоичных данных

11 с остатком 10 (поэтому следующая цифра - 2 десятичных знака)

делим 11 на 1010 двоичных

0 с остатком 11 (поэтому последняя цифра - 3 десятичных)

Согласно: http://people.cis.ksu.edu/~rhowell/calculator/comparison.html это алгоритм преобразования радиуса, используемый в SunКласс Java BigInteger и сложность O (n ^ 2).Авторы в этой ссылке реализовали алгоритм O (n logn) на основе алгоритма, описанного в Knuth p.592 и зачислено А. Шёнхаге.

Answer 3

Примерно так:

int a;
int temp;
a = 21;
vector<int> vet;

while(a>0)
{
temp = a % 10;
vet.push_back(temp);
a = a/10;
}