How to convert a vector of int representing binary to and vector of int representing the decimal number? C++

I am making a big integer library and i have a STL vector of int that re开发者_运维知识库present a binary number.

the binary vector would contain {0,0,1,1} and i need the decimal representation of this number to be stored in another vector like this {2,1}

What i want to know is what would be the best way to do this?

Also i can't use functions like pow because this needs to work with big numbers.

The most direct way to do this is to simply sum the decimal representation of each power-of-2 by mimicking decimal addition.

You could obtain the decimal representation of each power-of-2 iteratively, i.e. pow(2,n+1) = pow(2,n) + pow(2,n).

So basically, once you've got decimal addition nailed, everything should be pretty easy. This may not be the most efficient method (it's O(n^2) in the number of digits), but it should certainly work.

Knuth's "The Art of Computer Programming" Vol 2. is an excellent reference for arbitrary precision arithmetic.

A simple way to get a base 10 representation is to continously divide your number by 10, each division extracts one digit (the remainder). This obviously requires being able to divide by 10 in whatever base you already have.

For example, if your number is 321 decimal or 101000001 binary, we can divide:

10100001 binary by 1010 binary

100000 with remainder 1 (so first digit is 1 decimal)

divide 100000 by 1010 binary

11 with remainder 10 (so next digit is 2 decimal)

divide 11 by 1010 binary

0 with remainder 11 (so last digit is 3 decimal)

According to: http://people.cis.ksu.edu/~rhowell/calculator/comparison.html this is the radix conversion algorithm used in Sun's Java BigInteger class and is O(n^2) complexity. The authors in this link have implemented an O(n logn) algorithm based on an algorithm described in Knuth p. 592 and credited to A. Shönhage.

Something like that:

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

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