Binärt till decimalt - algoritm

ett binärt representerat tal kan representeras i godtycklig annan bas.

låt T = {b_n, b_{n-1}, ... , b_3, b_2, b_1, b_0}
exempelvis 100101
då skulle b_0 = 1, b_2=1, b_5=1 och alla andra b_n = 0.

För att räkna ut för basen 10 så räknar du ut: (b_0)*2^0 + (b_1)*2^1 + ... +(b_{n-1})*2^(n-1) + (b_n)*2^n

alltså 100101 ==> 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 + 0*2^4 + 1*2^4 = 1 + 4 + 16 = 21

waaou!

Är det påhittarN^ som är på gång?

100101 är ju för fan 37!

Puss!

hur räknar man då?

Det är ganska lätt att se felet:

5, 32 och 37 skall det vara.

Det lättaste är att skriva upp det.

128 64 32 16 8 4 2 = Binära
0 1 0 0 1 0 1

Då är det 64+8+2=74 i det decimala

Detta är så vi lärde oss i skolan, Men ni snackar om 256bitar. Har kanske fel då.

template <int T>
char* bin2string(bitset<T> b)
{
	...
	return "12000312381378281239812398124"; //eller vad det blir
}

Det finns inte inbyggt i C++ eller STL att kunna hantera godtygligt stora heltal.

Tredjepartsbibliotek eller att skriva en egen "BigInt"-klass (internt representera siffrorna i en vektor?) är lösningen här.

Algoritmerna för att implementera multiplikation och addition för en "BigInt"-klass? Tja... hur gör du när du räknar med papper och penna?

Använder du en annan bas än bas 10 i din BigInt klass?

I så fall är heltalsdivision och modulos-räkning den sökta lösningen.

Med andra ord; något i stil med:

string getBase10(BigInt num)
{
    string digits;

    // Räkna ut entals-siffran först, sedan tiotals-siffran, hundratals-siffran, o.s.v.
    while(num > 0)
    {
        int digit = num % 10;

        digits.push_back(digit + '0');

        num /= 10;
    }

    // Entals-siffran ligger i digits[0], tiotals-siffran i digits[1], o.s.v.
    // Kan vara en god idé att vända på alla siffrorna då!
    reverse(digits.begin(), digits.end());

    return digits;
}