Transforma într-un șir de caractere

Sarcina de conversie a unui număr la un șir de caractere ar trebui întotdeauna, atunci când doriți să afișați rezultatele numerice ale programului. Procesoarele ne desfășurăm activitatea pe date binare, om-si dau ca zecimale. De fapt, problema este de a converti numărul de bază. Ce să fac, există modalități? Scopul acestei lucrări este de a descrie și a compara numărul maxim de moduri de a converti un număr la un șir de caractere. Problema, desigur, luând în considerare din punctul de vedere al punerii în aplicare pe microcontrolere, pe dimensiunea și viteza sunt importante. Pentru simplificare, considerăm doar fără a-semnat pe 32 de biți și numere de 16 biți (nu cu mult mai dificilă cu semnul).

1. sprintf

Primul lucru care vine în minte este un sprintf funcție în biblioteca C standard. Utilizați-l pur și simplu:

Apoi, în matrice tampon este necesară în linia noastră.
Dar problema este, este sprintf formatat funcția de ieșire, care este o mulțime de lucruri se poate trage și o mulțime de alte funcții ale bibliotecii standard de. Dimensiunea codului mașină atunci când acesta este utilizat în mod semnificativ crește. De exemplu, chiar și versiunea minimă a sprintf AVR-libc (aceasta este ceea ce este o parte din WinAVR / AVR Toolchain) adaugă un pic mai puțin de 2 kilobytes.

2. utoa, ultoa

Compoziția bibliotecilor livrate cu compilatoare includ adesea o funcție de transformare a unui șir itoa, ltoa, utoa, ultoa. În general, aceste caracteristici nu sunt standard, picioarele sunt adesea disponibile, și, în contrast cu sprintf, nu fac nimic în plus.

3. Numerele de extract prin împărțirea de 10.

standard, gata și aspect de moda nu foarte. Acum este timpul să reinventeze bicicletele lor. Primul mod cel mai evident este, desigur, împărțit la 10, iar restul în ciclul de calcul.

Restul diviziei ne dă cifre zecimale în ordine inversă, începând cu cei mai tineri, așa că scrie din memoria tampon începând de la sfârșitul anului, astfel încât să nu implementați șirul rezultat.
Totul pare a fi doar frumos, nimic mai mult, dar există un singur lucru. De fapt diviziune, chiar și calcularea soldului. În cazul în care procesorul nu este divizia de hardware-ul, este foarte lent.

4. Eliminarea numerelor de divizare 10 prin intermediul funcției div

Pot încerca să utilizeze div funcția standard, care revine imediat câtul și restul?

Dar divizia rămâne încă. Avantajele acestei și metoda anterioară este faptul că acestea pot converti numărul într-un șir de caractere pentru orice motiv (dacă Yoh ușor modificat), nu neapărat 10.

5. Impartirea cu 10 ture și adăugare.

În cazul în care procesorul țintă nu are suport hardware pentru divizia de 32 de biți, cele două metode anterioare sunt destul de lent. Divizia 10 poate fi înlocuită cu o serie de schimbări și completări. Inspirat de cartea „trucuri algoritmice pentru programatori“ (este «deliciu hacker» același), scoate funcția diviziunea 10 utilizând permutări și completările ulterioare, înlocuind existente acolo, înmulțită cu 10 (este prea „scump“ pentru AVR, cel puțin) ca schimbare și adăugare. Am modificat, astfel încât acesta se întoarce și câtul și restul:

Se pare groaznic și nu este clar, dar este de fapt ușor. În primul rând, vom multiplica numărul inițial de 0,8 sau 1100 1100 1100 .1100 1100 1100 1100 1100 în reprezentarea binară. Este foarte convenabil faptul că fracțiunea periodică și a reușit să facă toate cele cinci ture și patru completări. În continuare împărți ceea ce sa întâmplat la 8, deplasarea spre dreapta de 3 descărcare. Se pare numărul inițial împărțit la 10, până la unitatea din cauza erorilor de rotunjire. După ce vom găsi reziduul obținut prin înmulțirea câtul cu 10, și scăzând-l din numărul inițial. În cazul în care restul este mai mare de 9, atunci și privat se adapteze.
Funcția folosește diviziunea „rapid“ nu diferă în aparență de la predecesorii săi.

6. Subtract 10 grade.

O altă metodă populară pentru transformarea unui număr la un șir de caractere, se scade din numărul inițial de serie de 10 de grade, pornind de la un maxim. Veți avea nevoie de un tabel cu aceste grade 10:

40 octeți în dimensiune. Și funcția în sine:

Works este simplu, atâta timp cât numărul actual este mai mare de 10 de grade ea scade din numărul de 10 grade și ia în considerare cât de mult timp a fost scăzută. Apoi, du-te la un grad mai mic de 10. Deci, până când ajunge la 1. Cifrele sunt obținute direct în ordinea dorită, trebuie doar să eliminați zerouri la început.

Metode BCD numere.

Următoarele trei metode se bazează pe operațiuni cu packed binar zecimal codificat - zecimale codificate binar (BCD). În această reprezentare, fiecare ciuguli (4 biți) stochează o cifră zecimală. În variabila pe 32 de biți, astfel, pot stoca 8 cifre zecimale. Reprezentarea binară a unei variabile de 2 biți este de 10 cifre zecimale. Prin urmare, aceste metode dau rezultate bordurate pentru un număr mai mare 99999999. numărul BCD este foarte ușor convertite într-un șir de caractere:

De fapt, din operațiunile de BCD, trebuie să adăugați și se înmulțește cu 2, care a fost înlocuit cu succes prin adăugarea numărului cu el însuși. Prin urmare, trebuie doar adăugarea de:

Se pare groaznic și nu este clar - din nou unele bitmap complicat Mojo. De fapt, pentru a adăuga două BCD pur și simplu adăugați-le ca numere binare convenționale - linia a + b =. Și apoi, pentru fiecare ciugulesc valoarea care a fost mai mult de 9 trebuie să adăugați numărul de corecție 6 cu transferul de biți în cele mai semnificative ciuguli. Și pentru fiecare ciuguli din care a fost transferul de biți în cea mai semnificativă ronțăit, trebuie să adăugați, de asemenea, numărul de corecție 6. Toate celelalte linii funcționează - este tocmai această corecție. Primele două rânduri, definim toți biții suma a + b + 0x66666666ul. care a schimbat valoarea sa datorita transferului de LSB biți. În al treilea rând vom adăuga cele două numere. În al patrulea - selectați biții cei mai puțin de transfer pentru fiecare tetrada. In alta - 6 adaugam la tetradelor din care a fost transferat biți. Acesta este modul în care - fără un transfer condiționat.

7. Adăugarea de puteri de două.

Prima metodă este bine familiară tuturor de la școală lecțiile de informatică, - adăugarea de reprezentări zecimale ale puterilor de două corespunzând unui singur bit în numărul convertit:

7. Adăugarea de puteri de două cu masa.

În metoda anterioară utilizează două numere însumării BCD. Una dintre ele pot fi eliminate prin a lua o putere de două din tabel:

Tabelul elmentov conține 30 - 120 octeți.

8. Metoda lui Horner

În această metodă, la fiecare pas de dublare a rezultatului zecimal acumulat, în cazul MSB numărului binar unu, apoi se adaugă la o unitate de rezultat, în care numărul binar este înmulțit cu 2 (deplasare per bit spre stânga).

Aici operațiunea două BCD plus, dar unul dintre ele cu adaos de 1 și de la ea se poate scăpa de.

În acest caz, primul argument bcd_add nu poate fi BCD valabil, în cazul în care mai tineri rontaie o cifră mai mare de 9. Dar bcd_add noastră este în mod normal, mestecă da rezultatul corect. Dar, dacă adăugați această unitate în plus la al doilea argument, rezultatul nu mai este corectă.
Numărul de iterații din ciclul acestei metode va fi întotdeauna egal cu numărul de biți, spre deosebire de cele anterioare, în cazul în care ciclul se va încheia de îndată ce vor fi cele de biți individuali.

9. Numerele de extracție multiplicată cu 10.

Acum, de fapt, partea pentru care totul a fost început - o comparație a vitezei. Prima platformă va fi testată folosind AVR compilator GCC.
Pentru metode de tipuri diferite de timp va depinde de diferiți factori, cum ar fi metodele bazate pe diviziunea de 10 timp va depinde în mare măsură de numărul de cifre zecimale ale valorii absolute este numărul și foarte puțin de ei înșiși aceste numere. Scădeți 10 grade în ciclul va fi mai rapid pentru a opera decât suma mai mică de cifre zecimale alcătuiesc numere. Aceasta este mult mai rapid manipulate 1000000 decât 999999. Metoda se bazează pe numărul binar-zecimale va funcționa mai rapid în cazul în care numărul inițial de biți individuale mici - cel mai rapid de către puterile de două. acesta din urmă metoda timpului de lucru va depinde numai de valoarea absolută a numărului convertit, dar mai puțin decât metodele de divizare prin 10. Deci, în kit-ul de testare ar trebui să fie mici Chila, numere mari, puterea de două până la zece grade, în cazul în care o mulțime de nouari.
Tot felul de teste pentru AVR este efectuată în mod convenabil la Simulavr simulator - nu au nevoie de nici un fier, și numeroase pereproshivok.
Pentru a măsura timpul de execuție a funcțiilor noastre folosim un timer de 16 biți ticăie la frecvența de bază. Consola de ieșire prin portul emulator de depanare. cod de optimizare pentru viteza maximă.
Iată ce sa întâmplat ca urmare a unor numere pe 32 de biți:

* După dependența plus dimensiunea - o funcție de masă sau împărțirea
** în paranteze sunt rezultatele pentru varianta cu ansamblul inline.

Liderul în acest indicator de referință, cu care nu o metodă de marjă mare pentru a divid rapid 10 ture și adăugarea. Pentru a-l obține grade de scădere apropiate 10. După înmulțirea prin metoda 10. Metodele cu diviziune onest (inclusiv utoa), cum era de așteptat, foarte lent, mai ales una care utilizează funcția ldiv. dar, de asemenea, cel mai compact. Executarea metodei Horner este practic independent de numărul convertit. sprintf funcționează relativ repede, în comparație cu utoa. Și nu e de mirare - a folosit într-o metodă similară cu utoa_fast_div, dar aeriene de parsare șirul de format și de ieșire lent la un tampon prin fputc se fac simțite.

UPDATE.
Rezultate pentru numere de 16 biți:

Aici, din nou, cu un avantaj vizibil de a conduce diviziune rapidă schimburi / pliat. Cel mai prost rezultat acum sprintf, pentru că în interiorul ea încă folosește un număr de 32 de biți.

UPDATE # 2. Rezultate pentru MSP430.

Rezultate pentru numere de 16 biți:

Pentru că, în plus față de MSP430 Launcpad și cu o piatră MSP430G2231 alt MSP430 nu am avut să-l testeze. Toate funcțiile, desigur, nu se potrivește, pe inundate și testate unul câte unul, folosind un script.
După cum puteți vedea o împărțire corectă aici este aproape de două ori mai lent decât AVR.
UPDETE # 3

Rezultate pentru STM32.

discutarea rezultatelor

Outsider peste tot o funcție de utilizarea funcției de bibliotecă diviziune div. În ciuda faptului că se întoarce într-un singur apel, iar reziduul și coeficientul, chiar și divizia de hardware STM32, este implementat în software-ul și se execută foarte lent. Evident, nu trebuie utilizat în această metodă. Cu toate acestea, funcția utilizează o divizie operator de utoa_builtin_div built-in. împletească la sfârșitul anului pe AVR și MSP430, pe STM32 - în plumb. Nu este surprinzător, pentru că în cortex M3 are o divizie de hardware, mulți spun, și nu sunt destul de dreapta - divizarea ceva acolo, dar nu este o astfel de rapidă (în paranteze pentru timp utoa_builtin_div specificat în cazul în care compilatorul pentru a genera o împărțire echitabilă). Faptul că CCG dificil atunci când împărțit prin utilizarea constantă a unui truc inteligent - Înlocuiesc diviziune prin înmulțire cu o astfel de constantă încât 32 de biți superiori din produsul pe 64 de biți pentru a conține dividendului inițial împărțit la 10.

Acest cod este echivalent cu aproximativ următoarele:
uint32_t tmp = valoare;

O astfel de metodă este, de asemenea, descrisă în cartea „trucuri algoritmice pentru programatori.“ Cu toate acestea, AVR și MSP430 acest număr nu va funcționa - există o multiplicare a 32 * 32 => 64 lucrări de divizare necuviincios lung, lung echitabil.
Un alt utoa_builtin_div are întotdeauna o dimensiune minimă.
Întotdeauna rezultat bun și de multe ori mai bine dă diviziunea de 10 ture și utoa_fast_div plus. Este practic lider de necontestat în viteză și este de multe ori dimensiuni destul de modeste. Această metodă este întotdeauna o alegere bună.
Mi-a plăcut cu multe grade scade zece utoa_cycle_sub în mărime cu tabelul de aproximativ aceeași sutoa_fast_div. dar întotdeauna dă un pic de viteză. In asemenea, nu este o alegere generală, rău.
Metoda se bazează pe numerele zecimale binare nu funcționează foarte repede, nu au cea mai mică dimensiune și la aceeași problemă doar rezultatul 8 cifre (în punerea în aplicare a mea, puteți obține toate cele 10 numere, dar va fi chiar mai lent). Este mai bine să nu utilizeze pentru a converti numere întregi binare pentru siruri de caractere și pentru conversia numerelor binare în binar zecimal ambalate, decolare pentru lucrările ulterioare.
În afară este metoda de multiplicare cu 10 utoa_fract. El nu arata foarte atractiv, în timp, cu toate acestea, este cel mai prost moment este adesea mai mică decât cele mai grave liderii de timp. În această metodă, diferența dintre cel mai bun și cel mai rău este relativ mică - este stabilă.

UPDATE.
Am găsit o altă metodă interesantă și foarte repede. Aici aici.

O descriere a modului în care funcționează din link-ul de mai sus în limba engleză. Din păcate, rezultatele corecte, această metodă produce numai valori de 15 biți, dar foarte repede:
pentru AVR cel mai bun timp - 133 de cicluri, cel mai rău - 167 media - 146.

Coming următor.

Partea 2: fixă ​​și virgulă mobilă.

PS. Poate cineva știe încă ce unele metode de conversie a numerelor într-un șir de caractere?

Inventat mai multe metode bazate pe fracții sau rânduri, nu știu cum să spun. Dacă veți obține - voi sublinia materialul (este necesar sau nu - Speak). Dar rezultatele preliminare, fără a salva partea fracționară mai rău.
neiver. va testa modul în care să descrie, dacă încă prisutsvuete pe site?

5 testat metoda din nou pe toată gama de uint32_t. s-au găsit Abaterile.
codepad.org/AZcD1P5Y

Hmm ... Se pare, am început nu am înțeles prea bine algoritmul este: nu ciuguli (niibly, 4-biți) copiați și dublează de fiecare dată când numărul de biți folosiți pentru suma de acumulare. Sly!

Greșeala pe care ați trece rezultatul automat de corecție.
Adăugarea unui alt schimbare la 32 și folosind valori pe 64 de biți a fost, de asemenea, valori corecte. Se pare ca o eroare de rotunjire este compensat în suma rezultată nu este destul de clar pentru mine mod, deoarece cu notebook-uri separate (în acest caz coincide cu perioada de benei fracție (1100)), eroarea se acumulează.
Vă mulțumesc foarte mult pentru articol!

Permiteți-mi să explic despre ce am scris, și se simte alarmist. La 52 (dec) și este limitată la 8 biți.
După cum se dovedește, succesiunea de acțiuni este importantă, adică, nu poți nasdvigat, iar apoi se adaugă rezultatele modificărilor, este necesar din acumularea de pe fiecare schimb. Cam ca echivalentul trebuie k.m.k.