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

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.

Undertaker

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?

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ß

CStoll

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

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.

Undertaker

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.

rapso

Undertaker schrieb:

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

... und ist ein raw-data-hazard.

Die assembler version ist eindeutig die beste. siehe auch: http://msdn2.microsoft.com/en-us/library/ms913691.aspx

hustbaer

kleine Bemerkung schrieb:

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ß

Ja, und macht sich damit wunderschön den 1st Level Cache kaputt

Undertaker

rapso schrieb:

Undertaker schrieb:

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

... und ist ein raw-data-hazard.

hey, die einzelnen schritte sollen gefälligst sequenziell ablaufen

rapso schrieb:

Die assembler version ist eindeutig die beste. siehe auch: http://msdn2.microsoft.com/en-us/library/ms913691.aspx

ja, asm ist immer das beste. wahrscheinlich gibt's prozessoren, die das mit 3 befehlen können, aber der OP muss diesen prozessor erstmal haben

groovemaster

Undertaker schrieb:

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

Die konstante Laufzeit hast du dir aber auch nur dadurch "erschummelt", dass du es auf 32 Bit begrenzt. Wenn man damit leben kann und das Argument keine compile time Konstante ist, würde ich diese Lösung auch vorziehen. Und da mittlerweile auch Assembler Vorschläge gemacht wurden, kannst du 'plattformunabhängig' noch als weiteren Punkt hinzufügen. Tja, C bzw. C++ fehlen halt bit scan intrinsics. Ein Template Ersatz ist dein Vorschlag trotzdem nicht.

Daniel E.

groovemaster schrieb:

Ein Template Ersatz ist deine Lösung trotzdem nicht.

Ein Template-Ersatz wird auch nicht benötigt. Wenn ich den Wert zur Compilezeit kenne, dann schreibe ich ihn direkt in den Quelltext und geheimse da nicht irgendwelches template<>::blabla-Gefrickel drumrum.

Undertaker

groovemaster schrieb:

Die konstante Laufzeit hast du dir aber auch nur dadurch "erschummelt", dass du es auf 32 Bit begrenzt.

ja, für z.b. 64 bit braucht man eine zeile mehr, für 128 bit eine weitere usw.
zum glück sind die datenwortbreiten von computern nicht so sehr variabel, als dass man sowas mit 'ner schleife machen müsste

Daniel E. schrieb:

Ein Template-Ersatz wird auch nicht benötigt. Wenn ich den Wert zur Compilezeit kenne, dann schreibe ich ihn direkt in den Quelltext und geheimse da nicht irgendwelches template<>::blabla-Gefrickel drumrum.

das lässt die template-varianten aber ganz alt aussehen

groovemaster

Daniel E. schrieb:

Ein Template-Ersatz wird auch nicht benötigt. Wenn ich den Wert zur Compilezeit kenne, dann schreibe ich ihn direkt in den Quelltext und geheimse da nicht irgendwelches template<>::blabla-Gefrickel drumrum.

Und was machste dann mit 'foo'. Das kann auch eine compile time Konstante sein. Klar, du kannst im entsprechenden Header nachschauen, um den Wert zu erfahren. Aber was ist, wenn den mal jemand ändert? Denkst du auch daran, die abhängigen Stellen anzupassen? Stichwort: Eliminierung von Redundanzen.

Daniel E.

groovemaster schrieb:

Daniel E. schrieb:

Ein Template-Ersatz wird auch nicht benötigt. Wenn ich den Wert zur Compilezeit kenne, dann schreibe ich ihn direkt in den Quelltext und geheimse da nicht irgendwelches template<>::blabla-Gefrickel drumrum.

Und was machste dann mit 'foo'. Das kann auch eine compile time Konstante sein. Klar, du kannst im entsprechenden Header nachschauen, um den Wert zu erfahren. Aber was ist, wenn den mal jemand ändert?

Dieses Problem in C bereits gelöst worden, #if&#error lassen grüßen. Zugegebenermaßen, besonders elegant war das noch nie, aber die Template-Lösung saugt auch ziemlich, die bringt uns wieder in die Zeiten zurück, wo man auf ein Compilat von mittelmäßig großen Programmen ein paar Stunden warten muß, von der augenkrebsverursachenden Syntax ganz abgesehen.

.filmor

Undertaker schrieb:

groovemaster schrieb:

Die konstante Laufzeit hast du dir aber auch nur dadurch "erschummelt", dass du es auf 32 Bit begrenzt.

ja, für z.b. 64 bit braucht man eine zeile mehr, für 128 bit eine weitere usw.
zum glück sind die datenwortbreiten von computern nicht so sehr variabel, als dass man sowas mit 'ner schleife machen müsste

Aber variabel genug dass man das nicht so im Code stehen haben will. Es gibt schon viel zu viele sorglose Leute, die Datentypgrößen ignorieren.

template <typename T, unsigned s, unsigned e>
struct npo2_
{
    static T& impl () (T& x)
    {
        x |= x >> e; 
        return npo2_<T, s - 1, e * 2>::impl (x);
    }
};

template <typename T, unsigned e>
struct npo2_<T, 0, e>
{
    static T& impl () (T& x) { return x |= x >> e; }
};

template <typename Int>
Int next_pow_of_2 (Int x)
{
    return npo2_<Int, sizeof(Int), 1>::impl (--x) + 1;
}

Das ergibt übrigens auf einem anständigen Compiler meines Erachtens exakt dasselbe wie deine Lösung (vorausgesetzt ich habe mich nicht vertan, hab wiederum keinen Compiler zur Hand ;))

Daniel E. schrieb:

die Template-Lösung saugt auch ziemlich, die bringt uns wieder in die Zeiten zurück, wo man auf ein Compilat von mittelmäßig großen Programmen ein paar Stunden warten muß

Aber sicherlich nicht bei einem solchen Template. Ekelhaft wirds nur bei wirklich vielen Templateinstanziierungen (>> 20).