CODEWITHSUNDEEP
c++vectorbinarydecimal
Mike
Mike

Reputation: 141

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 represent 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.

Upvotes: 2

Views: 3051

Answers (3)

Guy Sirton
Guy Sirton

Reputation: 8401

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.

Upvotes: 3

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272487

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.

Upvotes: 4

bratao
bratao

Reputation: 2070

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;
}

Upvotes: -3

Related Questions