Hallo, ich programmiere gerade ein Programm auf einen µC in C. Deshalb möchte ich das folgende Problem gerne ohne die Einbindung umfangreicher Bibliotheken lösen. Ich möchte eine Zahl immer zur nächsten 2er Potenzzahl aufrunden: Bsp: 1 -> 1 2 -> 2 3 -> 4 4 -> 4 5 -> 8 9 -> 16 19 -> 32 usw. Habt ihr einen Vorschlag wie ich das in meinem C-Code umsetzten kann? Viele Grüße Cris
1 | unsigned int zweierpoten(unsigned int a) |
2 | {
|
3 | out = 1; |
4 | while(a>>=1) out<<=1; |
5 | return out; |
6 | }
|
Bestimmt geht das eleganter und effizienter, als mir es spontan einfällt: Sei Dein Ausgangswert in der (o.B.d.A. unsigend) Variablen v abgelegt. Und sei in v mindestens das MSB 0. Dann setzt Du 'einfach' das am weitesten rechts stehende führende Null-Bit auf eins und alles rechts davon auf Null. Fertig.
Maker schrieb: > unsigned int zweierpoten(unsigned int a) > { > out = 1; > while(a>>=1) out<<=1; > return out; > } Der Duracell-Hase... der läuft und läuft und läuft...
1 | while(a>>=out) out<<=1; |
dann hörts hoffentlich irgendwann auf :)
Ohne Schleife, aber mit floating point Funktionen könnte es auch so gehen: out = pow(2.0,1.0+ceil(log(in))) Es kommt noch die "Sonderfallbehandlung" hinzu für Zahlen, die schon exakt Zweierpotenzen sind.
ichvonhier schrieb: > Duracell-Hase Nein. a >>= 1 ist die Kurzform von a = a >> 1 Murkser schrieb: > mit floating point Funktionen Das wollte der TO nicht.
Cris schrieb: > Ich möchte eine Zahl immer zur nächsten 2er Potenzzahl aufrunden: In Binärdarstellung sind das Zahlen mit nur einer einzigen Eins. Ist das nicht schon so, setzt man links von der vorhandenen höchstwertigen Eins das Bit auf Eins und den ganzen Rest auf Null. Schneller dürfte es nicht gehen. Georg
Da du nicht angegeben hast welcher µC, ist es schwer eine optimale Antwort zu geben. Ich werfe mal noch __builtin_ctz vom gcc in den Pott. Auf aktuellen x86 cpus wird daraus ein lzcnt "leading zero count". Ob es etwas vergleichbares für deinen Compiler und µC gibt, muss du selbst rausfinde.
1 | unsigned int round2(unsigned int input) |
2 | {
|
3 | for(unsigned int out = unsigned_int_max; out > 1; out = out >> 1) |
4 | if(out&input) |
5 | return out + ((out >> 1)&input)?1:0; |
6 | return 0; |
7 | }
|
unsigned_int_max bitte durch den maximal in einem unsigned int auf der jeweiligen Architektur speicherbaren Wert ersetzen Ist aber ungetestet
Es muss natürlich
1 | return ((out >> 1)&input)?(out<<1):out; |
heißen
"Bit Twiddeling Hacks" meint der folgende Code: siehe https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
1 | unsigned int v; // compute the next highest power of 2 of 32-bit v |
2 | |
3 | v--; |
4 | v |= v >> 1; |
5 | v |= v >> 2; |
6 | v |= v >> 4; |
7 | v |= v >> 8; |
8 | v |= v >> 16; |
9 | v++; |
ZigZeg
Maker schrieb: >
1 | > unsigned int zweierpoten(unsigned int a) |
2 | > { |
3 | > out = 1; |
4 | > while(a>>=1) out<<=1; |
5 | > return out; |
6 | > } |
7 | >
|
Danke dir! Ich bevorzuge diese Variante. Ist evtl als for Schleife noch übersichtlicher:
1 | int i = 1; |
2 | for (i = 1; i < Zahl; i <<= 1); |
3 | Zahl = i; |
Schlaumüller schrieb: > Y = Potenz (2; GANZZAHL ( LOG(X;2)+0,999999999999 ) ) Cris schrieb: > Deshalb möchte > ich das folgende Problem gerne ohne die Einbindung umfangreicher > Bibliotheken lösen. Bitte Aufgabenstellung beachten :-)
Murkser schrieb: > Sollte das nicht "while(a>=out) out<<=1;" heißen? Geht auch. Solange für den Sonderfall 0 keine Regel definiert ist, ist es sowieso nur eine Fingerübung. Da mache ich mir noch nicht mal die Mühe, alle Variablen zu deklarieren. ;)
Murkser schrieb: > Ohne Schleife, aber mit floating point Funktionen könnte es auch so > gehen: > > out = pow(2.0,1.0+ceil(log(in))) Und floating point auf "einen µC" kommt ohne die Einbindung umfangreicher Bibliotheken aus?
Cris schrieb: > Danke dir! Ich bevorzuge diese Variante. Ist evtl als for Schleife noch > übersichtlicher: Die Version ist aber hoffentlich nur für s Prinzip und wird nicht ernsthaft so irgendwo stehen, oder?
Achim S. schrieb: > Cris schrieb: >> Danke dir! Ich bevorzuge diese Variante. Ist evtl >> als for Schleife noch übersichtlicher: > > Die Version ist aber hoffentlich nur für s Prinzip > und wird nicht ernsthaft so irgendwo stehen, oder? Kommt auf die mittlere Größe der Zahlen an. Für kleine Zahlen ist die Schleife im Mittels sicher nicht langsamer als der "bit twiddling hack". Der gewinnt erst bei großen Zahlen -- dann allerdings deutlich.
Cris schrieb: > ich programmiere gerade ein Programm auf einen µC in C. Deshalb möchte > ich das folgende Problem gerne ohne die Einbindung umfangreicher > Bibliotheken lösen. > > Ich möchte eine Zahl immer zur nächsten 2er Potenzzahl aufrunden Da mußt du erstmal ein paar Randbedingungen definieren: 1) Was soll aus 0 werden. 0 oder 1? 2) Um welchen Zahlenraum geht es. Natürliche Zahlen oder Ganze Zahlen. Sprich: kann ein negatives Vorzeichen vorkommen? 3) Was soll passieren, wenn der durch den "Datentyp" vorgegebene Zahlenraum verlassen werden muss, um das korrekte Ergebnis liefern zu können? Für gelernte Assemblerprogrammierer ist das völlig trivialer Scheiss. Du bist offensichtlich keiner. Das entbindet dich allerdings nicht von Notwendigkeit, über all dies nachzudenken... Hochsprachen versprechen viel, können aber nur das Wenigste davon wirklich halten. Sobald es an den Rand der verwendeten "Datentypen" geht, sind Hochsprachen noch viel komplizierter als Assembler zu beherrschen...
c-hater schrieb: > Für gelernte Assemblerprogrammierer ist das völlig trivialer Scheiss Das habe ich ja viel weiter oben schon beschrieben, auch genau wie. Ich weiss natürlich nicht, ob der TO das gelesen hat, aber absolut sicher hat er es nicht verstanden. Abgesehen davon kann man Bit-Manipulationen ja auch in Hochsprachen ausführen, aber dazu müsste man das Prinzip begriffen haben. Das soll beim Programmieren ja öfters so sein. Es hilft deswegen hier sicher nicht weiter was anderes als for-Schleifen anzusprechen. Georg
Egon D. schrieb: > Kommt auf die mittlere Größe der Zahlen an. Für kleine > Zahlen ist die Schleife im Mittels sicher nicht langsamer > als der "bit twiddling hack". Der gewinnt erst bei großen > Zahlen -- dann allerdings deutlich. Mir geht es nicht um Laufzeit, sondern um den Überlauf, also dass alles > 0x8000 (bzw. 0x80000000) nicht funktioniert, je nach typ von Zahl sogar endlos läuft. Das 0-->1 liefert ist ja vermutlich so gewollt, ergibt sich nicht aus der Aufgabenstellung. Cris schrieb: > int i = 1; > for (i = 1; i < Zahl; i <<= 1); > Zahl = i;
c-hater schrieb: > Hochsprachen versprechen viel, können aber nur das Wenigste davon > wirklich halten. In welchen Hochsprachen programmiert denn der Herr, dass er es nicht versteht? Alles, was in Assembler (das niemand mehr benutzt) funktioniort, kann auch in Hochsprachen gemacht werden.
Probiere mal: /* round x up to y; y is a power of 2 */ #define ROUNDUP2(x,y) (((x) + ((y)-1)) & ~((y)-1))
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.