Aufgrunden auf nächste 2er Potenzzahl

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 :)

ichvonhier schrieb:
> while(a>>=out) out<<=1;

Sollte das nicht "while(a>=out) out<<=1;" heißen?

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.

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.

mh schrieb:
> mal noch __builtin_ctz vom

es war __builtin_clz gemeint

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

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;

Y = Potenz (2; GANZZAHL ( LOG(X;2)+0,999999999999 ) )

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. ;)

https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

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))