Czarodziejskie lusterko - SPOJ

Witam. Czy może mi ktoś pomóc zoptymalizować mój program? Otrzymywane wyniki są prawidłowe, jednak algorytm działa zbyt wolno, żeby SPOJ mógł go przyjąć.
Link do zadania http://pl.spoj.com/problems/AL_05_01/

#include <iostream>
using namespace std;



int main()
{
    unsigned long long int liczba;
    int t = 1000001;
    while(t--)
    {
        string str_bin = "";
        cin>>liczba;
        while(liczba!=0)
        {
            if(liczba%2==0) str_bin+='0';
            else str_bin+='1';
            liczba/=2;

        }
      unsigned long long int wynik = 0;
      int dlugosc = str_bin.size()-1;
      unsigned long long int potega = 1;
      for(dlugosc;dlugosc>=0;dlugosc--)
      {
          if(str_bin[dlugosc]=='1')wynik+=potega;
          potega*=2;
      }
      cout<<wynik<<endl;
}

}

Na pewno to jest złe:

 int t = 1000001;
    while(t--)

reszta - to ew (ale przy malych liczbach to nie wiem) jakies przyspieszenie może być zmieniając string na bardziej zaawansowana strukturę (np std::stringstream). Ale przy niewielkiej ilości cyfr może nie być widać zbytnio rezultatu.

1. źle wczytujesz dane
2. nie robi się tego na stringach, w końcu komputer trzyma liczby w postaci binarnej, więc konwersja do napisu jest zbędna

Kod na wczytywanie danych:

#include <iostream>
using namespace std;

typedef unsigned long long int ullong;

ullong reverseSignificantBits(ullong x) {
   …
}

int main()
{
    unsigned long long int x;
    while(cin >> x)
    {
        cout << reverseSignificantBits(x) << endl;
    }
    return 0;
}

Użyj operacji bitowych

Dobra uwaga od @MarekR22 - komputer trzyma liczby w postaci binarnej, on tylko pokazuje je w postaci dziesiętnej. Więc wczytujesz liczbę normalnie, robisz czary mary bitowe i już
http://guidecpp.cal.pl/cplus,operators-bits

tu jest podpowiedź, ale penie namąci ci ona w głowie, więc czytaj ostrożnie.

Nie wiem, jakim sposobem ale rozkminiłem taki oto algorytm. SPOJ zaliczył zadania, natomiast ja nie wiem, czym się różnił od moich poprzednich zgłoszeń :D. Ale dzięki za pomoc, jakoś wpadłem na ten pomysł dzięki Wam :D

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;



int main()
{

    unsigned long long int liczba;
    while(cin>>liczba)
    {
        vector<int>bin;
        while(liczba!=0)
        {
            if(liczba%2==1)bin.push_back(1);
            else bin.push_back(0);
            liczba/=2;
        }

        unsigned long long int wynik = 0;
        unsigned long long int potega = 1;
        for(int i=bin.size()-1; i>=0; i--)
        {
            wynik+=bin[i]*potega;
            potega*=2;
        }
        cout<<wynik<<endl;
    }
}

Witam,
również walczę z tym programem czy jest szansa, abyście podpowiedzieli mi co zrobiłem źle?

#include <iostream>

using namespace std;

string DecToBin(unsigned long long int liczba)
{
    if ( liczba == 0 ) return "0";
    if ( liczba == 1 ) return "1";

    if ( liczba % 2 == 0 )
        return DecToBin(liczba / 2) + "0";
    else
        return DecToBin(liczba / 2) + "1";
}
int BinToDec(string liczba)
{
    unsigned long long int wynik = 0, pow = 1;
    for ( int i = liczba.length() - 1; i >= 0; --i, pow <<= 1 )
       {
        wynik += (liczba[i] - '0') * pow;
       }

    return wynik;
}

string odwracanieDecToBin(string liczba)
{
    string liczbyOdworcone;
    for (int i =liczba.length()-1; i >=0; i--)
    {
        liczbyOdworcone += liczba[i];
    }

    return liczbyOdworcone;
}

int main()
{
    unsigned long long int liczbaDec;
    int liczbaOdwrocona;

    while(cin >> liczbaDec)
    {
        string zDziesNaBin = DecToBin(liczbaDec);
        string odwracanie = odwracanieDecToBin(zDziesNaBin);
        liczbaOdwrocona = BinToDec(odwracanie);
        cout << liczbaOdwrocona << endl;
    }


    return 0;
}

A tak? https://www.geeksforgeeks.org/reverse-bits-using-lookup-table-in-o1-time/

Witam
mam problem z zadaniem Czarodziejskie lusterko. Program działa lecz sędzia nie przyjmuje mojego rozwiązania. Czy mógłby mi ktoś powiedzieć gdzie jest błąd? Poniżej mój kod:

#include <iostream>

using namespace std;

string DecToBin (unsigned long long int liczbaDziesietna)
{
unsigned long long int wynik;
string liczbaDwojkowaLiteraPOM, liczbaDwojkowaLitera;

while(liczbaDziesietna!=0)
{
    wynik = liczbaDziesietna%2;
    liczbaDziesietna = liczbaDziesietna/2;
    liczbaDwojkowaLiteraPOM += wynik + 48;
}

int dlugosc=liczbaDwojkowaLiteraPOM.length();
for (int j=0; j<dlugosc; j++)
{
    liczbaDwojkowaLitera += liczbaDwojkowaLiteraPOM[dlugosc-j-1];
}

return liczbaDwojkowaLitera;

}

string odbicieLiczby (string liczbaDwojkowaLitera)
{
string odwroconaLiczbaDwojkowa;
int dlugosc = liczbaDwojkowaLitera.length();

for(int j=0; j<dlugosc; j++)
{
    odwroconaLiczbaDwojkowa += liczbaDwojkowaLitera[dlugosc-j-1];
}

return odwroconaLiczbaDwojkowa;

}

long int potega(long int podstawa, int wykladnik)
{
int wynik = 1;

for (int i = 0; i<wykladnik; i++)
    wynik*=podstawa;

return wynik;

}

unsigned long long int BinToDec (string odwroconaLiczbaDwojkowa)
{
unsigned long long int odwroconaLiczbaDziesietna=0, odwroconaLiczbaDziesietnaPOM=0;
int dlugosc = odwroconaLiczbaDwojkowa.length();

for (int i=0; i<dlugosc; i++)
{
    odwroconaLiczbaDziesietnaPOM = odwroconaLiczbaDwojkowa[dlugosc-i-1]-'0';
    odwroconaLiczbaDziesietna += odwroconaLiczbaDziesietnaPOM * potega(2,i);
}

return odwroconaLiczbaDziesietna;

}

int main()
{
unsigned long long int liczbaDziesietna;

while(cin >> liczbaDziesietna)
{
    cout << BinToDec(odbicieLiczby(DecToBin (liczbaDziesietna))) << endl;
}

return 0;

}