Optymalizacja algorytmu zmieniającego liczbę integer na liczbę binarną i odwrotnie

jackoi

2014-03-06T11:59:56+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Kraków
Postów: 124

Witam, jak można zoptymalizować poniższą funkcję zmieniającą Dec na Bin, aby działała szybciej? Na spoju cały czas wyrzuca przekroczenie czasu ? Zadanko: http://pl.spoj.com/problems/AL_05_01/ Trochę już ten kod uszczupliłem ale wciąż to samo. Zadanie polega na zamianie dec na bin, następnie odwroceniu kolejnosci liczby binarnej i wypisaniu jej jako dec. Dla małych liczb działa :)
Dzieki z góry za pomoc :)

Oto kod:

Kopiuj

 
#include <cstdio>
#include <sstream>
#include <bitset>

std::string DecToBin(unsigned long long number) {
    if ( number == 0 ) return "0";
    if ( number == 1 ) return "1";

	std::ostringstream oss;
	while(number > 0) {
		oss << number % 2;
		number = number / 2;
	}
	return oss.str();
}

int main() {
	unsigned long long n;
	
	while(scanf("%llu", &n)) {
		printf("%llu\n", std::bitset<64>( DecToBin(n) ).to_ulong());
	}
	
	return 0;
}

Shalom

2014-03-06T12:07:52+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Space: the final frontier
Postów: 26433

No ja bym jednak nie zamieniał tego na stringa tylko od razu odwrócił sobie bity ;]
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

_13th_Dragon

2014-03-06T12:58:18+01:00

Rejestracja: dni
Ostatnio: dni

Kopiuj

unsigned long long DecToBin(unsigned long long number)
  {
   unsigned long long ret;
   for(ret=0;number;number>>=1) ret=(ret<<1)|(number&1);
   return ret;
  }