3. Von n auf die nächst größere 2er Potenz

Von n auf die nächst größere 2er Potenz

  • U

    ohne jetzt angeben zu wollen, aber meinen vorschlag finde ich immer noch am elegantesten.
    - keine schleifen
    - kein fliesskomma
    - keine sprünge
    - konstante laufzeit
    - lesbarer, verständlicher code (im gegensatz zu dem ersten template-gewurschtel)
    usw... 😉

    0
  • M

    Tja, Undertaker, die Laufzeit vom Template ist leider auch konstant, nämlich konstant 0.

    0
  • U

    Michael E. schrieb:

    Tja, Undertaker, die Laufzeit vom Template ist leider auch konstant, nämlich konstant 0.

    und was macht das template, wenn der input zur compilezeit noch nicht bekannt ist? 😃

    0
  • M

    Na auf deine Lösung ausweichen 😉 Die Vor- und Nachteile wurden doch schon bereits genannt. Ich wollte halt nur sagen, dass deine Lösung nicht in allen Fällen die beste ist.

    0
  • U

    Michael E. schrieb:

    Ich wollte halt nur sagen, dass deine Lösung nicht in allen Fällen die beste ist.

    kann schon sein, aber meine version lässt sich sehr leicht in jede programmiersprache umsetzten, die addition und bitoperationen kennt.
    ausserdem kann man sie sogar, wenn's denn sein muss, mit ein paar logikchips zusammenlöten.
    das versuch mal mit 'nem template... :p

    0
  • C

    Undertaker schrieb:

    - konstante laufzeit

    Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben 😉

    (btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

    0
  • U

    CStoll schrieb:

    Undertaker schrieb:

    - konstante laufzeit

    Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben 😉

    irgendwelche beschränkungen hat man bei computern doch immer.
    der wertebereich von z.b. 'double' ist auch nicht unendlich gross.

    CStoll schrieb:

    (btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

    das musst du nicht mir, sondern der programmiersprache C ankreiden 😉

    0
  • C

    Undertaker schrieb:

    CStoll schrieb:

    Undertaker schrieb:

    - konstante laufzeit

    Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben 😉

    irgendwelche beschränkungen hat man bei computern doch immer.
    der wertebereich von z.b. 'double' ist auch nicht unendlich gross.

    Wenn du es so siehst, hat jedes reale Programm konstante Laufzeit 😉 Aber der Punkt ist - dein Ansatz funktioniert nur für 32-Bit-Zahlen (und wenn du irgendwann mit größeren Werten rechnen willst, mußt du die Funktion in Handarbeit erweitern). Die Lösungen mit Schleifen und Templates funktionieren dagegen für jedes n (solange der Computer es im Speicher unterkriegen kann).

    (und der Unterschied zwischen O(1) und O(log n) macht sich idR erst für "große n" bemerkbar)

    CStoll schrieb:

    (btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

    das musst du nicht mir, sondern der programmiersprache C ankreiden 😉

    Nein, das hat nichts mit der Programmiersprache zu tun. Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

    0
  • U

    CStoll schrieb:

    Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

    ich könnte mit dir wetten, dass die meisten meinen code lesbarer finden als die templates...
    🙂

    0
  • C

    Undertaker schrieb:

    CStoll schrieb:

    Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

    ich könnte mit dir wetten, dass die meisten meinen code lesbarer finden als die templates...
    🙂

    Bei dem halbseitigen Konstrukt von hustbaer glaube ich das sofort, bei der Variante von camper nicht mehr (und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten und (b) es auch auf andere Basen erweitern).

    0
  • U

    CStoll schrieb:

    ...und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten...

    das bit-gebastel lässt sich auch mathematisch erfassen, allerdings muss man dafür einen anderen zweig der mathematik bemühen. 😉

    0
  • C

    Undertaker schrieb:

    CStoll schrieb:

    ...und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten...

    das bit-gebastel lässt sich auch mathematisch erfassen, allerdings muss man dafür einen anderen zweig der mathematik bemühen. 😉

    Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür 😉

    (PS: Du bist nicht zufällig mit einem gewissen net/ten/vista/pale dog verwandt?)

    0
  • U

    CStoll schrieb:

    Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür 😉

    ich lass das lieber, würde mir gewaltig einen abbrechen dabei. ich bin mir aber sicher dass es leute gibt, die das locker hinkriegen. 🙂

    CStoll schrieb:

    (PS: Du bist nicht zufällig mit einem gewissen net/ten/vista/pale dog verwandt?)

    sind das von dir besonders geschätzte forenteilnehmer?
    ...oder welche meiner dummen bemerkungen bringt dich zu der vermutung?

    0
  • C

    Undertaker schrieb:

    CStoll schrieb:

    Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür 😉

    ich lass das lieber, würde mir gewaltig einen abbrechen dabei. ich bin mir aber sicher dass es leute gibt, die das locker hinkriegen. 🙂

    Und da erwartest du, daß ein 08/15-Programmierer den Sinn dieses Fragments auf einen Blick erfassen kann?

    CStoll schrieb:

    (PS: Du bist nicht zufällig mit einem gewissen net/ten/vista/pale dog verwandt?)

    sind das von dir besonders geschätzte forenteilnehmer?

    "geschätzt" ist bei ihm wohl die falsche Bezeichnung.

    ...oder welche meiner dummen bemerkungen bringt dich zu der vermutung?

    Keine bestimmte - es war eher dein Auftreten im Allgemeinen (und dein Timing)

    0
  • B

    Wenn es wirklich schnell sein muss dann geht folgendes:

    inline unsigned ceil_pow2(unsigned n){
	assert(n != 0);
	unsigned out;
	asm("bsr %0, %1" : "=r"(out) : "r"((n<<1)-1));
	return 1<<out;
}

inline unsigned floor_pow2(unsigned n){
	assert(n != 0);
	unsigned out;
	asm("bsr %0, %1" : "=r"(out) : "r"(n));
	return 1<<out;
}

    Funktioniert auf x86 Prozessoren. Gibt Blödsinn bei n = 0 aus.

    0
  • U

    CStoll schrieb:

    Undertaker schrieb:

    CStoll schrieb:

    Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür 😉

    ich lass das lieber, würde mir gewaltig einen abbrechen dabei. ich bin mir aber sicher dass es leute gibt, die das locker hinkriegen. 🙂

    Und da erwartest du, daß ein 08/15-Programmierer den Sinn dieses Fragments auf einen Blick erfassen kann?

    zumindest eher, als dass er es mit mathematischen formalismen beschreiben kann. 🙂

    CStoll schrieb:

    ...es war eher dein Auftreten im Allgemeinen...

    was stört dich daran?

    0
  • ?

    Hallo

    Wenn's noch schneller sein muß und man schnelles RAM oder große Caches hat, belegt man beim Programmstart einfach
    ein Array vom Typ int mit den entsprechenden Funktionswerten

    a[i]=(int)exp(log(2)*ceil(log(n)/log(2)))

    Braucht man später den Funktionswert an der Stelle i,
    schlägt man einfach a[i] nach.

    Bei Zahlen bis 2^20-1 muß man dafür 4 MByte Speicher
    reservieren.

    Gruß

    0
  • C

    Undertaker schrieb:

    CStoll schrieb:

    Undertaker schrieb:

    CStoll schrieb:

    Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür 😉

    ich lass das lieber, würde mir gewaltig einen abbrechen dabei. ich bin mir aber sicher dass es leute gibt, die das locker hinkriegen. 🙂

    Und da erwartest du, daß ein 08/15-Programmierer den Sinn dieses Fragments auf einen Blick erfassen kann?

    zumindest eher, als dass er es mit mathematischen formalismen beschreiben kann. 🙂

    Also ich müsste da länger überlegen, um zu erkennen, WAS dieser Code bewirken soll (und warum da am Ende das richtige Ergebnis herauskommen sollte) - und ich halte mich für einen halbwegs erfahrenen C++ Programmierer.

    CStoll schrieb:

    ...es war eher dein Auftreten im Allgemeinen...

    was stört dich daran?

    Das lässt sich nur schwer in Worte fassen - du benimmst dich ganz einfach "typisch" (vielleicht ist es deine Sturheit - oder auch nur deine Ablehnung gegenüber Templates).

    0
  • ?

    Hat geklappt, der SpeicherManager ist in Größenordnungen von 3000x so schnell wie die Systemfunktion und hat nicht das Problem von externer Fragmentierung, kann aber auch nur Blöcke der Größe 2^n hohlen. Alles in allem ein Erfolg.
    Sicherlich wird sich der eine oder Andere Konsolenprogrammierer an den Kopp fassen, was ich im WorstCase für Speicher verplemper, aber ich hatte ein echtes Problem mit vielen kleinen Objekten, was ich aus der Welt schaffen musste.

    0
  • U

    CStoll schrieb:

    CStoll schrieb:

    ...es war eher dein Auftreten im Allgemeinen...

    was stört dich daran?

    Das lässt sich nur schwer in Worte fassen - du benimmst dich ganz einfach "typisch" (vielleicht ist es deine Sturheit - oder auch nur deine Ablehnung gegenüber Templates).

    sturheit? wann war ich 'stur'?
    was templates angeht: ich finde templates sind eine tolle erfindung. warum soll eine cpu immer wieder ackern, wenn das ergebnis schon vorher einmal berechnet werden kann?
    ja, die C++ template-syntax finde ich grauenhaft, aber das ist ein anderes thema.
    🙂

    0
Anmelden zum Antworten