Transformarea numerelor in baza 2...O problema de timp

[•VisuianMihai]

Buna... am o intrebare... stie cineva o metoda eficienta de a transforma numere in baza 2 in cap sau foarte repede pentru a nu pierde vremea la operatii pe biti?

mersi anticipat...

[•scipianus]

Buna... am o intrebare... stie cineva o metoda eficienta de a transforma numere in baza 2 in cap sau foarte repede pentru a nu pierde vremea la operatii pe biti?

mersi anticipat...

In primul rand,numerele memorate sunt deja in baza 2,asa le retine calculatorul pentru a lucra cu ele.Si de aceea operatiile pe biti sunt cele mai rapide pentru a lucra cu bitii acelui numar   Ca sa afisezi de exemplu un numar n in baza 2 (presupunand ca e un int pe 32 biti) faci asa :

Cod:

for(i=31;i>=0;i--)
		cout<<((n>>i)&1);

[•S7012MY]

pentru transformatul in cap nu stiu nici o metoda. Totusi dupa ce faci cateva probleme cu operatii pe biti in general o sa le gandesti mult mai rapid. Nu cred ca e ceva mai bun decat algoritmul prin impartiri.

[•MciprianM]

Te ajuta daca memorezi puteri ale lui 2 (daca nu le-ai memorat deja): 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
Apoi gasesti cea mai mare putere a lui 2 care "incape" in numarul de transformat. Scrii un 1. Pe urma scazi din numarul de transformat 2 la puterea gasita, imparti puterea la 2, scrii 1 daca incape in ce a mai ramas, 0 altfel si tot asa.
Exemplu:
710
512 e cel mai mare numar, putere a lui 2 care incape in 710 => 1
scadem 512 din 710 si ne ramane 198
continuam cu 256 > 198                                                => 0
continuam cu 128 <= 198                                                => 1
198 - 128 = 70, continuam cu 64 <= 70                             => 1
scadem, ramanem cu 6, continuam cu 32 > 6                    => 0
16 > 6                                                                       => 0
8 > 6                                                                        => 0
4 <= 6 scadem si ramanem cu 2                                       =>1
continuam cu 2 <= 2                                                      =>1
2 - 2 = 0, continuam cu 1 > 0                                         => 0
Deci 710 se scrie in baza 2: 1011000110

Daca transformam invers observam ca 710 = 2 + 4 + 64 + 128 + 512.
Ideea e ca fiecare numar in baza 10 se scrie unic ca suma de puteri ale lui 2, daca fiecare putere a lui 2 este folosita cel mult o data.