C++ Community

Hoolui

Hallo,

mein Anliegen ist recht kurz:

Ich benötige eine (schnelle) Formel, wie man von einem Wert n auf die nächst größere 2er Potenz kommt.

Beispiel:

Wert ist 500.
Nächst größere 2er Potenz ist 512.
Wert ist 513.
Nächst größere 2er Potenz ist 1024 usw.

Ich hoffe, dass irgendwer mir dabei behilflich sein kann.

MfG

ich

borg

$2^{\lceil\log_2(x)\rceil}$

walljumper

ich würds so machen

int i=0;
double zahl=500;
while(zahl >= 1.0)
{
zahl/=2;
i++;
}

in i steht dann der exponent

Undertaker

für 32 bittige int's -->

unsigned next_pow_of_2 (unsigned x)
{
    x--;
    x = x | x >> 1;
    x = x | x >> 2;
    x = x | x >> 4;
    x = x | x >> 8;
    x = x | x >> 16;
    return x+1;
}

hustbaer

Und compile-time gehts so :

#include <conio.h>

template <unsigned long n> struct pow2 {
	static unsigned long const value = pow2<n-1>::value * 2; };

template <> struct pow2<0> {
	static unsigned long const value = 1; };

template <bool stop, unsigned long x, unsigned long n> struct next_pow2_impl {
	static bool const stop_next = (x <= pow2<n + 1>::value);
	static unsigned long const value = next_pow2_impl<stop_next, x, n + 1>::value;
	static unsigned long const exponent = next_pow2_impl<stop_next, x, n + 1>::exponent; };

template <unsigned long x, unsigned long n> struct next_pow2_impl<true, x, n> {
	static unsigned long const value = pow2<n>::value;
	static unsigned long const exponent = n; };

template <unsigned long x> struct next_pow2 {
	static unsigned long const value = next_pow2_impl<(x <= 1), x, 0>::value;
	static unsigned long const exponent = next_pow2_impl<(x <= 1), x, 0>::exponent; };

int main() 
{ 
	#define DO_TEST(n) printf("%d, %d, %d\n", n, next_pow2<n>::value, next_pow2<n>::exponent)
	DO_TEST(0);
	DO_TEST(1);
	DO_TEST(2);
	DO_TEST(23);
	DO_TEST(128);
	DO_TEST(129);
	DO_TEST(10101);
	DO_TEST(16777000);
	#undef DO_TEST

	return 0;
}

BTW: an die Template Spezialisten: kann man das eigentlich auch eleganter lösen? Ohne Verwendung von Boost MPL oder ähnlichem natürlich...

.filmor

Also das eigentliche Anwendertemplate könntest du schon noch deutlich einfacher machen:

template <unsigned long x> struct next_pow2 : public next_pow2_impl<(x <= 1), x, 0> {};

Außerdem reicht dir ja an sich die Zweierpotenz, der Exponent ist ja egal und du kannst die Implementierung (da sie recht kurz ist) direkt ins Template packen:

template <unsigned N> struct next_pow2
{
private:
    template <unsigned Value> struct impl
    {
        static const unsigned value = (Value >= N) ? Value : impl<Value * 2>::value;
    };

public:
    static const unsigned value = impl<1>::value;
};

Alle Angaben ohne Gewähr, ich hab auch gerade keinen Compiler zur Hand.

camper

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

rapso

http://www.forum-3dcenter.org/vbulletin/showthread.php?t=372382

Wesley67

Optimiert:

int result = 0;
int zahl = 98454365;   // oder was auch immer

for (;result != (zahl |= zahl >> 1); result = zahl);
result++;

Krux

int nzp(int i){  //Nächste zweierpotent
    for(int j = 1; j <= i; j*=2);
    return j;
}

optimierungen wie das ersetzen durch bitschift erledigt der Kompiler.
die Zeit geht in O(log n)

Blue-Tiger

http://graphics.stanford.edu/~seander/bithacks.html

Sven25 @logged off

Vielleicht stehe ich ja gerade auf dem Schlauch, aber was ist falsch an borgs Lösung? Ich würde auch den Zweierlogarithmus nehmen, aufrunden, und wieder 2 hoch vorheriges Ergebnis rechnen. Sollte doch wesentlich schneller sein als alle Schleifen, oder?

Blue-Tiger

Sven25 @logged off schrieb:

Vielleicht stehe ich ja gerade auf dem Schlauch, aber was ist falsch an borgs Lösung? Ich würde auch den Zweierlogarithmus nehmen, aufrunden, und wieder 2 hoch vorheriges Ergebnis rechnen. Sollte doch wesentlich schneller sein als alle Schleifen, oder?

Wer sagt dir denn, das log() intern ohne Schleife auskommt? Die schnellste Loesung ist sicher die template-Loesungen von hustbaer, die aber nur funktioniert wenn das Argument bereits zur Compilezeit feststeht.
Wenn das nicht geht, ist die von Undertaker die schnellste, da sie ohne Schleife, ohne Runden, etc. auskommt. Andere sehr schnelle Loesungen gaebs noch auf der Seite, deren Link ich vorhin gepostet hab, nur leider ist die grad offline. Aber die "naive"-Methode ueber den 2er Logarithmus wahrscheinlich die langsamste.

EDIT: hier nochmal ein Link der auch funktioniert: http://www.cs.utk.edu/~vose/c-stuff/bithacks.html#RoundUpPowerOf2

CStoll

Ja, der Logarithmus-Ansatz hat (vermutlich) konstante Laufzeit - aber er verwendet Gleitkomma-Arithmetik und die ist meist um einiges langsamer als Ganzzahl-Arithmetik.

(womit wir beim Grundproblem der Komplexitätstheorie sind: O(1) ist "besser" als O(log n), zumindest für große Werte von n. Bei relativ kleinen Werten mußt du dir die Laufzeit genauer ansehen, um zu entscheiden - und da ist 10s (liegt in O(1)) natürlich schlechter als 1ms*log₂n (O(log n) (zumindest für n<10³⁰⁰⁰))

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

kleine Bemerkung

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.

kleine Bemerkung

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.

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