Ganze Zahl aufrunden zu 2er-Potenz

net 0

SeppSchrot schrieb:

Ich hab auch schon überlegt, das mit einer Schleife abzufragen und zu schauen, ob nach dem größten Bit noch weitere kommen.

so ähnlich, nach dem höchsten gesetzten bit löschte alle weg (nächst kleinere zweierpotenz) und dann alles einmal links shiften (die nächste grössere)

Windalf

das problem hatte ich leztens auch brauchte ich für nen ezw-encoder/decoder...

habs so gemacht

size_t next2pow(size_t num){
	size_t i;
	if(!num)return 1;
	for(i=8*sizeof(size_t)-1;!(num&(1<<i));--i);
	if(num&((1<<i)-1))++i;
	return 1<<i;

}

lookias

int fkt(float n,int k)
{
if(n>2)
  ftk(n/2,k++);
if(n==2)
  return k-1;
if(n<2)
  return k;
}

Ach du lieber Schreck Windalf Da bleib ich dann doch lieber bei meinem Einzeiler.
Naja, hatte nur vermutet, ich hätt was übersehen, weil das Problem so einfach wär.

Doch danke für eure Vorschläge.

In lookias´ Algo steckt Kapital*, den werde ich morgen mal mit "? :" bearbeiten.

* Ich versteh ihn nur noch nicht.
Naja, mal Blatt und Stift rauskram.

Windalf

@SeppSchrot
Seh gerad du bist ja auch Berliner (gruss aus Spandau... )

hmm eigentlich hab ich doch genau das gemacht was du vorher erzählt hast

Ich hab auch schon überlegt, das mit einer Schleife abzufragen und zu schauen, ob nach dem größten Bit noch weitere kommen

genau das war jedenfalls auch meine intention dabei...

lookias

oh das liegt daran dass zwischen einer zahl und seinem doppelten immer genau eine soclche potenz von 2 steckt
halbiert man die zahl bis man unter 2 liegt so hat man die potenz der nexten 2er potenz der zahl

nur ist ja die 2er potenz um einen hoeher dann sonst waere man nicht unter 2

da man bei 1 anfaengt ist sie dann um eins niedriger wenn man bei 2 landet

aber das ganze gelingt vlt nicht bis zur maximalen float zahl

weil vielleicht schon auf 1 gerundet wird bei 4 millarden

btw was isn "?:" ?

MFK

Dafür eine Rekursion an den Start zu bringen, halte ich für Overkill.

unsigned int nextpoweroftwo(unsigned int n)
{
	int i=0;
	for(;n;++i,n>>=1);
	return 1 << i;
}

lookias schrieb:

btw was isn "?:" ?

Jaja, mit Satzzeichen hast du's ja offenbar nicht

Windalf

jo die lösung von MFK sieht am besten aus... was du dir noch überlegen musst ist ob du im falle einer zweierpotenz auch wirklich die nächste haben willst oder die zahl selber... indem fall dann noch 1 abziehen...

lookias

erklaehr mal bitte:

return 1 << i;

for(;n;++i,n>>=1);

dat sieht mir irgendwie neu aus besonders das << kenn ich nur von cout
(bzw >> von cin)
und ;n ist doch best ein schreibfehler oder?

nman

lookias schrieb:

dat sieht mir irgendwie neu aus besonders das << kenn ich nur von cout

Das ist der Shift-Operator, danach kann man besser googeln als nach "<<"

und ;n ist doch best ein schreibfehler oder?

Nein, er will wohl nichts initialisieren.

MFK

lookias schrieb:

erklaehr mal bitte:

Solange deine Beiträge so schlecht zu lesen sind, nein. Bitte benutz Satzzeichen und vielleicht sogar Großbuchstaben, lass solche Sachen wie "dat" und "best", sonst tu ich mir das nicht an. Nur so viel: Schreibfehler sind da nicht drin, was du durch Ausprobieren auch rausgefunden hättest.

lookias

Nun den shift-Operator konnte ich bis jetzt verstehen

und was heisst nun n>>=1 ?

;n ist mir auch net gelaeufig

nman

lookias schrieb:

und was heisst nun n>>=1 ?

Analog zu (a+=2) == (a=a+2) heißt das n=n>>1.

;n ist mir auch net gelaeufig

Naja, for-Schleifen sehen so aus:

for (initialisierung; bedingung; durchlaufaktion)

Wenn Du nichts initialisieren möchtest, dann schreibst Du einfach

for (;bedingung; durchlaufaktion)

lookias

Gut ok danke, hatte das Komma uebersehen.

++i,n>>=1

Also das mit dem Komma hab ich auch noch nie gesehen,

ist das so Konvention fuer for Schleifen oder wo kann man das noch machen?

Wird n irgendwie false wenn man es lang genug durch 2 teilt, oder ebend die bits verschiebt?

Braunstein

Es wird irgendwann 0 und das bedeutet false.

Bashar

lookias schrieb:

Also das mit dem Komma hab ich auch noch nie gesehen,

Das ist der Komma-Operator.

lookias

Danke vielmals ich muss doch immer wieder feststellen, wie wenig ich doch kann

Ich denke auch, dass MFK's Loesung die Bessere ist, da meine ja schliesslich das Selbe bedeutet, als wenn man die 2 solange potenziert bis man ueber n liegt.

MFK

lookias schrieb:

Danke vielmals ich muss doch immer wieder feststellen, wie wenig ich doch kann

Das würde ich als gutes Zeichen deuten. Solange man das noch merkt, kann man lernen.

Ich denke auch, dass MFK's Loesung die Bessere ist, da meine ja schliesslich das Selbe bedeutet, als wenn man die 2 solange potenziert bis man ueber n liegt.

Sie hat aber gegenüber der Aufgabenstellung noch ein Obiwanproblem, denn bei einer Zweierpotenz als Eingabewert sollte derselbe Wert rausgegeben werden. Meine Funktion gibt die nächste Zweierpotenz aus.

Jester

Wenn es vor allem darum geht, daß die Lösung effizient ist könnte man auch folgendes machen:

der bsr-Befehl (Assembler) sagt einem das größte gesetzte Bit.

Also müßte man einfach nur 1<<r liefern, wobei r der Wert sein sollte, den bsr liefert. Jetzt fehlt nur noch der Fall, daß die eingegebene Zahl schon eine Zweierpotenz ist. Das kann man aber leicht abfangen, denn:

x ist 2er-Potenz <=> x & (x-1) == 0

Dann kommt man ohne schleifen aus, auch wenn man auf Grund des inline-Assemblers nicht mehr so schön portabel ist. Läßt sich aber vielleicht mit nem ifdef lösen und je nach Anwendungsfall bringt's vielleicht was.

MfG Jester

Effizenz muss nicht sein, Portabilität auch nicht.
Bloß ältere Grafikkarten vertragen nur diese Texturgrößen, dafür brauch ichs.

if (x & (x-1)) ...

Genial!

Den werd ich mal mit MDKs Lösung kombinieren.