Test auf 2er Potenz-funktion?

P3nnyw1s3

hi leute,

ich habe ein problem.
ich habe eine funktion geschrieben der ein integer wert übergeben wird.
die funktion soll nun einen array anlegen dessen anzahl der elemente gleich dem logarithmus zur basis 2 des integer werts ist.
also zb wenn ich 9 übergebe,hat der array 3 elemente ,da der logarithmus= ca 3,irgendwas.(das ergebnis ist ein double und ich runde mit floor() )
wenn ich nun 8 übergebe hat der array leider nur 2 elemente da der wert des logarithmus wohl so circa 3 - 10^-15 ist^^
wie könnte eine funktion lauten die mir exakt sagt ob eine ganze zahl eine 2er potenz ist.
soll ich immer wieder durch 2 teilen bis irgendwann 1 rauskommt?
ich hoffe man versteht was ich meine^^
liebe grüße

Bashar

P3nnyw1s3 schrieb:

soll ich immer wieder durch 2 teilen bis irgendwann 1 rauskommt?

Ja.

P3nnyw1s3

hm was sollt ich am liebsten als abschätzung nehmen wie oft ich das machen muss,oder soll ich ne while schleife schreiben?

The-Kenny

Auf die schnelle bei Google gefunden:

http://www.cprogramming.com/snippets/show.php?tip=10&count=30&page=0

(Keine Garantie :D)

P3nnyw1s3

hm return !((x-1) & (x));

versteh ich nicht^^
also wenn eine zahl eine 2er potenz ist dann ist ja der binärcode der zahl eine 1 mit einer entsprechenenden anzahl an 0en dahinter.
das steht doch da auch irgendwie oder?^^

Swordfish

!( ( 100 - 001 ) & 100 )
!(         011   & 100 )
!                  000
=                 true

!( ( 101 - 001 ) & 101 )
!(         100   & 101 )
!                  100
=                 false

greetz, Swordfish

P3nnyw1s3

ah danke,der rückgabetyp ist ja int,wie geht das dann?

Nanyuki

Der Logarithmus von 8 zur Basis 2 ist genau 3. Kann aber durchaus sein, dass du da durch Ungenauigkeiten so etwas wie 2.9999999999 geliefert bekommst. Du kannst also entweder normal runden (+0.5 vor floor()) oder nur einen sehr kleinen Wert addieren (z.B. +0.00001).
Die folgende Funktion wurde hier auch vor nicht allzu langer Zeit gepostet. Sie dürfte auch recht schnell sein (falls es darauf ankommt).

int log2 (int v)
{
    static const int MultiplyDeBruijnBitPosition[32] =
    {
          0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    v |= v >> 1; // first round down to power of 2
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v = (v >> 1) + 1;

    return MultiplyDeBruijnBitPosition[(v * 0x077CB531UL) >> 27];
}

P3nnyw1s3 schrieb:

ah danke,der rückgabetyp ist ja int,wie geht das dann?

Was für ein Rückgabetyp?
Der Ausdruck !((x-1) & (x)) gibt dir ein bool-Wert, der angibt, ob x eine Potenz von 2 ist.

Swordfish

http://www.cprogramming.com/snippets/show.php?tip=10&count=30&page=0 schrieb:

int powerOfTwo( unsigned int x )
{
    return !((x-1) & x);
}

Implizite Umwandlung nach bool durch den ! -Operator und dann nach int . Alles was nicht 0 ist, ist true

greetz, Swordfish

PS: Sauber wäre natürlich, einen bool zurückzugeben...

Hier eine Template-Funktion zum Berechnen des 2-Logarithmuses einer Ganzzahl:

template<typename T> T lg(T x)
{
	T n = 0;
	for( ; x > 1; x >>= 1)
		++n;
	return n;
}

Dann brauchst du nicht mit Gleitkommazahlen rechnen...