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

hustbaer

camper schrieb:

.filmor: da fehlt eine Abbruchbedingung, Templates werden auch (noch) instantiiert, wenn sie wegen des ?: Operators eigentlich nicht gebraucht werden.
template <unsigned N> struct next_pow2 { static const unsigned value = 2 * next_pow2< ( N + 1 ) / 2 >::value; };
template <> struct next_pow2<1> { static const unsigned value = 1; };
template <> struct next_pow2<0> { static const unsigned value = 1; };

Hehe, ok, das IST eleganter
(und erzeugt vermutlich auch viel weniger instanzierte Templates, was auch gut ist)
Und geht vermutlich auch nocht mit dem ollen VC6 der ja keine partielle Spezialisierungs-Ding kann - müsste man nur den "static const" genen ein enum tauschen...

@Blue-Tiger: dein Link ist 403...

----

BTW: logarithmus und Gleitkomme und co: das ist Pfui! weil man gefälligst nicht mit Gleitkomme rechnet wenn man genaue Ergebnisse braucht

Hallo

wieso ist eine halbseitige Template-Sequenz elegant, wenn es auch eine
4-buchstabige Formel tut?

Eleganz ist Einfachheit im Verein mit Allgemeingültigkeit.

Gruß

CStoll

kleine Bemerkung schrieb:

wieso ist eine halbseitige Template-Sequenz elegant, wenn es auch eine
4-buchstabige Formel tut?

Erstens ist die letzte Template-Version nur drei Zeilen lang und zweitens ist die Formel zwar wunderbar geeignet, die Lösung mathematisch zu erfassen - die Frage ist jedoch, wie diese Formel technisch umgesetzt werden sollte.

Hallo

so vielleicht?:

exp(log(2)*ceil(log(n)/log(2)))

nicht schnell, aber elegant.

Gruß

CStoll

kleine Bemerkung schrieb:

Hallo

so vielleicht?:
exp(log(2)*ceil(log(n)/log(2)))
nicht schnell, aber elegant.

Und auch nicht sonderlich genau (selbst wenn das mathematisch exakt den Vorgaben entspricht, scheitert es in der Praxis an der begrenzten Genauigkeit der Gleitkomma-Arithmetik).

Undertaker

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

Michael E.

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

Undertaker

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?

Michael E.

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.

Undertaker

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

CStoll

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)

Undertaker

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

CStoll

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.

Undertaker

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

CStoll

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

Undertaker

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.

CStoll

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

Undertaker

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?

CStoll

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)

Ben04

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.