Wie ermittelt man von einer Zahl x, welchen Wert y bei der Gleichung 2 hoch y = x hat?



  • Ich habe eine Zahl, die eine Potenz von 2 ist. Gibt es jetzt eine Möglichkeit, zur Compile-Zeit (also ohne Funktionsaufrufe) herauszufinden, die wievielte Potenz von 2 diese Zahl ist?

    Also wenn ich ein Makro erstelle:

    #define ZWEIERPOTENZ(wert) ...
    

    dann soll folgendes Ergebnis kommen:

    int a = ZWEIERPOTENZ(2);
    // a ist jetzt 1.
    int b = ZWEIERPOTENZ(4);
    // b ist jetzt 2.
    int c = ZWEIERPOTENZ(8);
    // c ist jetzt 3.
    int d = ZWEIERPOTENZ(16);
    // d ist jetzt 4.
    

    Ist sowas zur Compile-Zeit möglich (natürlich unter der Voraussetzung, dass ich dem Makro einen konstanten Wert übergebe) oder braucht es dafür Funktionen?



  • Gibt es jetzt eine Möglichkeit, zur Compile-Zeit (also ohne Funktionsaufrufe) herauszufinden, die wievielte Potenz von 2 diese Zahl ist?

    Ja, wenn die Parameter bereits beim Kompilieren gegeben sind. Dann kannst du auch Funktionen nutzen. Gute Compiler sollten durch Optimierung das Ergebnis bereits beim Übersetzen berechnen, wodurch der Aufruf der Funktion wieder entfällt.



  • Das ist aber nicht garatiert, dass der Compiler das optimiert.



  • Wenn du es garantiert wegoptimiert haben möchtest (was eigentlich völliger quatsch ist, wenn der Compiler es zur compilezeit sehen kann), dann würde ich sowas benutzen.
    Pre C++14:

    #include <iostream>
    template<unsigned N> struct is_power2
    {
        const static int value = N == 0 ? 0 : ((N & (N - 1)) != 0 ? 0 : 1);
    };
    
    template<unsigned N> struct power2
    {
        const static int value = is_power2<N>::value == 0 ? -1 :  1 + power2<N / 2>::value;
    };
    template<> struct power2<0>
    {
        const static int value = -1;
    };
    
    int main()
    {
        std::cout<<power2<8>::value<<'\n';
        std::cout<<power2<9>::value<<'\n';
    }
    

    Mit C++14:

    #include <iostream>
    
    constexpr auto power2(unsigned N)
    {
        auto sum = 0;
        if( N == 0 || (N&(N-1)) != 0)
        	sum = -1;
        else
    	    while (N >>= 1)
            	++sum;
        return sum;
    }
    
    int main()
    {
        std::cout<<power2(8)<<'\n';
        std::cout<<power2(9)<<'\n';
    }
    

    Macros machen keinen Sinn, wenn du eine Auswertung zur Compilezeit erzwingen möchtest. Das ist am Ende nichts anderes für den Compiler als eine Funktion, die er sehen kann. Kann das Macro wegoptimiert werden, dann wird auch deine (inline) Funktion wegoptimiert. Im Gegensatz zu den anderen 2 Methoden (template magie und constexpr-Funktion) ist das Auswerten zur Compilezeit dann aber nicht garantiert, aber extrem wahrscheinlich.



  • Das
    https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
    sollte sich als Makro formulieren lassen. Vermutlich wäre die "IF YOUR CPU BRANCHES SLOWLY" Variante am einfachsten zu adaptieren.
    Wenn man denn wirklich ein Makro braucht.



  • asdfasd schrieb:

    Macros machen keinen Sinn, wenn du eine Auswertung zur Compilezeit erzwingen möchtest. Das ist am Ende nichts anderes für den Compiler als eine Funktion, die er sehen kann. Kann das Macro wegoptimiert werden, dann wird auch deine (inline) Funktion wegoptimiert.

    Makros die "einen Wert haben" können keine Schleifen enthalten (ja, ich weiss, GCC compound statements - aber das ist ne nonstandard Extension). Inline Funktionen schon. Und auf das Wegoptimieren von Schleifen würde ich mich nie verlassen -- nicht wenn es wichtig ist. Kann nach hinten losgehen.
    Davon abgesehen kann man Inline Funktionen - ohne constexpr - nicht an Stellen verwenden wo konstante Werte benötigt werden. Wenn man das braucht, und constexpr nicht verwenden kann, scheiden Inline Funktionen also schonmal ganz aus.

    Und was die implizierte Behauptung angeht dass man sich bei Makros nicht darauf verlassen kann dass diese zur Compilezeit ausgewertet werden...
    Also man kann schreiben

    int a[3];
    int a[1 + 2];
    int a[2 * 2 - 1];
    int a[(2 * 2 * 2) == 8 ? 3 : 4];
    //...
    

    Bisher sind mir da auch kein Limit bezüglich der "maximalen Komplexität" dieser Ausdrücke aufgefallen.
    Da ein "Makro mit Wert" zu genau sowas expandiert, kann man sich also mMn. sehr wohl darauf verlassen dass es compiletime ausgewertet wird. Und dass ein Compiler so doof sein sollte das nur dort zu machen wo er muss, an anderen Stellen aber Code generiert der es unnötigerweise ausrechnet - das kann ich mir irgendwie nicht vorstellen.

    Wobei die Template-Variante mMn. viel eleganter ist. Und wer sich an der Syntax stört kann ja den "Aufruf" des Tempaltes immer noch in einem Makro verstecken.



  • Du hast natürlich recht. Ich habe immer an Lösungen über Schleifen/Rekursion gedacht. Wenn man es mit dem Holzhammer macht, kann man sich natürlich so ein Macro bauen:

    #define power2(N) ((N) == (1<<0)  ? 0  : \
                       (N) == (1<<1)  ? 1  : \
                       (N) == (1<<2)  ? 2  : \
                          ....               \
                       (N) == (1<<31) ? 31 : \ [je nach dateityp]
                       -1)
    


  • asdfasd schrieb:

    Du hast natürlich recht. Ich habe immer an Lösungen über Schleifen/Rekursion gedacht. Wenn man es mit dem Holzhammer macht, kann man sich natürlich so ein Macro bauen:

    #define power2(N) ((N) == (1<<0)  ? 0  : \
                       (N) == (1<<1)  ? 1  : \
                       (N) == (1<<2)  ? 2  : \
                          ....               \
                       (N) == (1<<31) ? 31 : \ [je nach dateityp]
                       -1)
    

    Oder mit dem power-holzhammer
    [code="cpp"]
    //nicht auf vorzeichen und so kram geachtet, nur demo
    #define power2_2(n) (n)==1?0:(n)==2?1:-1)
    #define power2_4(n) ((n)<(1>>2):power2_2(n):power2_2((n)>>2)
    #define power2_8(n) ((n)<(1>>4):power2_4(n):power2_4((n)>>4)
    #define power2_16(n) ((n)<(1>>8):power2_8(n):power2_8((n)>>8)
    #define power2_32(n) ((n)<(1>>16):power2_16(n):power2_16((n)>>16)
    [/quote]



  • Um sowas zur Laufzeit zu machen, gibts auf x86 uebrigens dies hier: http://www.fermimn.gov.it/linux/quarta/x86/bsr.htm


Log in to reply