Anzahl verwendeter Bitstellen mit C-Preprocessor ermittelbar?

[Ralf (Gast)]

Hallo,

ich grüble gerade, ob es mittels Preprocessor möglich ist, aus einem 
(konstanten,) ganzzahligen Wert die Anzahl der Bits zu ermitteln, die 
nötig sind, um diesen Wert darzustellen.
Also 127 = 7 Bits, 128 = 8 Bits, 129 = 8 Bits, ...

Ich kann natürlich ein "riesiges" Makro schreiben, in welchem das ganze 
mit einem Haufen Größenvergleiche hardcoded ist. Also in etwa(!) so:

#define GetExp2(x) ( (x) >= (1 << 31) ? 31 : ((x) >= (1 << 30) ? 30 : ...)...

Aber ich bin nicht sicher, ob das nicht auch eleganter geht.

Hat jemand einen Tip?

Ralf

[(prx) A. K. (prx)]

Die Methode, mit der man das optimiert berechnen kann, lässt sich auch 
im Präprozessor nutzen:
https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

[Adam P. (adamap)]

A. K. schrieb:
> Die Methode, mit der man das optimiert berechnen kann, lässt sich
> auch
> im Präprozessor nutzen:
> 
https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

Ich sehe dort aber keine Preprozessor-Anweisungen sondern Lösungen 
mittels Funktionen...

Und was ist mit der 0...sind dafür etwa 0 Bits nötig um es darzustellen?

Sonst bitte ich um Entschuldigung, wenn ich dein Anliegen nicht richtig 
gedeutet habe.

[(prx) A. K. (prx)]

Adam P. schrieb:
> Ich sehe dort aber keine Preprozessor-Anweisungen sondern Lösungen
> mittels Funktionen...

Vergiss es. Ich hatte die Frage missverstanden.

[Andreas M. (amesser)]

Mit dem Pre-prozessor fällt mir nichts ein, mit C++ und rkcursiven 
Templates schon:

/* Recursives template */
template<unsigned long VALUE>
class GetBits { public: static constexpr uint8_t Bits = 1 + GetBits<VALUE/2>::Bits;};

/* Rekursionsende */
template<>
class GetBits<0> { public: static constexpr uint8_t Bits = 0;};


/* beispiel */
int bits = GetBits<12345>::Bits;

Wird komplett vom Compiler berechnet, am Ende steht da nur noch eine 
Zahl im Code. Wenn man nur Bytes will wirds einfacher.

[Wilhelm M. (wimalopaan)]

constexpr-Function:

    template<typename T>
    constexpr uint8_t minimumBitsForValue(const T& v) {
        for(uint8_t n = 1; n <= std::numeric_limits<uint8_t>::max(); ++n) {
            T max = T((1 << n) - 1);
            if (v <= max) {
                return n;
            }
        }
        return 0;
    }

[Luther B. (luther-blissett)]

Hatten wir schon mal (Anzahl Bits == log2())
Beitrag "log2() mit Preprocessor"

[Ralf (Gast)]

Hallo Prx,

danke für den Link. Ich glaube, das ist nicht ganz das richtige, dort 
wird gezählt wie viele Bits gesetzt sind. Ich möchte wissen, wieviele 
Bitstellen ich brauche, um eine Zahl darzustellen.

Ralf

[Ralf (Gast)]

Sack und Asche oO

Mein Browser hat mich verseckelt. Als ich die letzte Antwort schrieb, 
wurde nur die Antwort von prx angezeigt. Vielen Dank natürlich auch an 
alle anderen für die Antworten, ich schaue ob ich da was passendes 
finde.

Falls es interessiert, habe es gerade eben (weil ich die Antwort der 
anderen nicht angezeigt bekam schäm) folgendermaßen implementiert:

#define POW2(x) (1 << (x))
#define GET_MSB_POS(x)  (  \
        (x) >= POW2(31) ? 32 : ( \
        (x) >= POW2(30) ? 31 : ( \
        (x) >= POW2(29) ? 30 : ( \
        ...
        (x) >= POW2(3) ? 4 : ( \
        (x) >= POW2(2) ? 3 : ( \
        (x) >= POW2(1) ? 2 : 1 \
        )))))))))))))))))))))))))))))) \
      )

Ich vergleiche also, ob (X) gleich oder größer als 2^N ist, und gebe N+1 
zurück, wobei N von 1-31 geht. Ist (X) = 0, gebe ich eins zurück, weil 
m.E. eine Null auch ein Bit braucht :)
Soviel zur Theorie... Wenn ich das ganze nun teste, kommt aber murks 
raus:

#define TEST 512

uint32_t Result;
Result = GET_MSB_POS(TEST);  //Result = 32

Laut Debugger hab ich 32 drin stehen, also liefert gleich die erste 
Abfrage im Makro ((x) >= POW(31)) wahr zurück. Ich finde den Fehler 
nicht. Liegt's an den Klammern? Was übersehe ich?

GCC 5.4-2016-q2 für ARM Cortex-M3.

Wie gesagt schau ich mir jetzt die bereits eingegangenen Antworten an, 
aber es würde mich trotzdem interessieren, was ich da falsch gemacht 
habe - man will ja lernen :)

Ralf

[Yalu X. (yalu) (Moderator)]

1<<31 verlässt den Wertebereich von int.

[Ralf (Gast)]

Hallo Yalu,

>> 1<<31 verlässt den Wertebereich von int.
Hm... d.h. es liegt daran, dass der Preprocessor nicht erkennt, dass es 
mehr als ein int ergibt und dass aus "1 << 31" im Endeffekt 0 wird. Die 
512 (TEST) sind somit größer und deswegen ist die Bedingung wahr, 
korrekt?
Dann werde ich im Makro mal auf long casten und schauen, ob es dann 
korrekt ist.

Danke :)

Ralf

[Ralf (Gast)]

Sieht nicht so aus, als ob es das war. Aber danke trotzdem, dass alles 
erst mal ohne weiteres als 16-Bit Wert interpretiert wird, sollte man im 
Hinterkopf behalten.

Ralf

[Yalu X. (yalu) (Moderator)]

Ralf schrieb:
> Hm... d.h. es liegt daran, dass der Preprocessor nicht erkennt, dass es
> mehr als ein int ergibt und dass aus "1 << 31" im Endeffekt 0 wird.

Streng nach ISO ist es "undefined behavior", in der realen Welt aber
0x80000000 (auf einem 32-Bit-System), was in Zweierkomplementdarstellung
die negativste aller darstellbaren Zahlen ist.

> Die 512 (TEST) sind somit größer und deswegen ist die Bedingung wahr,
> korrekt?

Ja.

Ralf schrieb:
> Sieht nicht so aus, als ob es das war.

Es sollte reichen,

#define POW2(x) (1 << (x))

in

#define POW2(x) (1u << (x))

zu ändern, so dass POW2(x) immer positiv wird.

Übrigens kannst du die an Lisp erinnernde Zeile

        )))))))))))))))))))))))))))))) \

und die dazugehörigen öffnenden Klammern weglassen :)

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Ralf schrieb:
>

> #define GET_MSB_POS(x)  (  \
>         (x) >= POW2(31) ? 32 : ( \
>         (x) >= POW2(30) ? 31 : ( \
>         (x) >= POW2(29) ? 30 : ( \
>         ...
>         (x) >= POW2(3) ? 4 : ( \
>         (x) >= POW2(2) ? 3 : ( \
>         (x) >= POW2(1) ? 2 : 1 \
>         )))))))))))))))))))))))))))))) \
>       )
>

Wenn du es so machen willst, nimm wenigstens eine binäre Suche. D.h. 
teste zuerst auf den Mittelwert des (Rest)Intervalls.

Ansonsten, wie schon von diversen Schreibern vorgeschlagen, nimm eine 
Integer ilog2() Funktion deiner Wahl 
(https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 
ff) und:

msb_pos = ilog2(x);

Die ilog2() Funktion sollte abrunden und bei ilog2(0), entgegen der 
korrekten mathematischen Definition, statt einer −∞ Exception einen Wert 
wie 0 oder -1 zurück geben.

[(prx) A. K. (prx)]

Hannes J. schrieb:
> Wenn du es so machen willst, nimm wenigstens eine binäre Suche. D.h.
> teste zuerst auf den Mittelwert des (Rest)Intervalls.

Die Rechnung wird bereits vom Compiler durchgeführt, da es eine 
Konstante ist.

Bei einem möglichweise nicht konstanten Wert wäre beim erwähnten GCC/ARM 
der CLZ Befehl hilfreich: __builtin_clz(x). Bei einer Konstanten wird 
auch dies schon vom Compiler gerechnet.

[Rolf M. (rmagnus)]

Ralf schrieb:
> Hallo Yalu,
>
>>> 1<<31 verlässt den Wertebereich von int.
> Hm... d.h. es liegt daran, dass der Preprocessor nicht erkennt,

Der Preprozessor berechnet in deinem Code gar nix. Der macht hier nur 
Textersetztung. Die einzige Stelle, wo der Preprozessor wirklich selber 
rechnet, ist in einer #if-Anweisung.

> dass es mehr als ein int ergibt und dass aus "1 << 31" im Endeffekt 0
> wird.

Wie groß das Ergebnis ist, spielt keine Rolle für den Zieltyp, sondern 
auschließlich der Typ der Operanden. 1 ist vom Typ int, also ist 1 << X 
(für beliebiges X) ebenfalls vom Typ int.

> Dann werde ich im Makro mal auf long casten und schauen, ob es dann
> korrekt ist.

Dann achte aber darauf, dass es nur auf 64-Bit-Plattformen üblich ist, 
dass long größer als 32 Bit ist. Und casten musst du die 1 dafür auch 
nicht. Es reicht, 1L zu schreiben, bzw. besser gleich 1UL, denn dann ist 
es vorzeichenlos.

Ralf schrieb:
> Aber danke trotzdem, dass alles erst mal ohne weiteres als 16-Bit Wert
> interpretiert wird, sollte man im Hinterkopf behalten.

Der Typ ist int. Der muss nicht zwingend 16 Bit breit sein, sondern kann 
auch je nach Zielarchitektur größer sein. Da deine Zielarchitektur ein 
PC ist, werden es 32 Bit sein.

[Ralf (Gast)]

Guten Morgen,

jawoll, das casten in einen vorzeichenlosen Datentyp hat's wohl gelöst. 
Muss es noch austesten, aber im Listfile steht nun zumindest mal ne 10 
(2^10 = 512) drin :)
Vielen Dank an alle.

@Yalu:
>> Übrigens kannst du die an Lisp erinnernde Zeile
>>

       )))))))))))))))))))))))))))))) \

>> und die dazugehörigen öffnenden Klammern weglassen :)
Okay... das war der Tatsache geschuldet, dass man prinzipiell bei 
Makros, die etwas berechnen, auf die Klammerung achten soll. Und in 
einem Editor, der die zueinander gehörenden Klammern anzeigen kann, sind 
viele Klammern manchmal doch hilfreich :)

@Hannes:
Danke für den Link, sehr hilfreich. Der wird gleich mal abgespeichert. 
Momentan benötige ich es nur für Konstanten, d.h. es kann schon beim 
Übersetzen berechnet werden. Von daher reicht es als Makro. Aber die 
Implementierung als Funktion wird sicherlich auch mal gebraucht.

@prx:
>> Bei einem möglichweise nicht konstanten Wert wäre beim erwähnten GCC/ARM
>> der CLZ Befehl hilfreich: __builtin_clz(x). Bei einer Konstanten wird
>> auch dies schon vom Compiler gerechnet.
Interessant. Mit direkten ASM-Befehlen habe ich noch nie gearbeitet. 
Muss ich mal ausprobieren. Ich würd ja jetzt zu gern fragen, wie man 
dann Portabilität sicherstellt, aber ich glaube das wäre ein eigener 
Thread :)

Ralf

[Yalu X. (yalu) (Moderator)]

Ralf schrieb:
> @Yalu:
>>> Übrigens kannst du die an Lisp erinnernde Zeile
>>>       )))))))))))))))))))))))))))))) \>> und die dazugehörigen öffnenden
> Klammern weglassen :)
> Okay... das war der Tatsache geschuldet, dass man prinzipiell bei
> Makros, die etwas berechnen, auf die Klammerung achten soll.

Um bei einem in ein Makro verpackten arithmetischen Ausdruck mögliche
Überraschungseffekte zu minimieren, sollte man Klammern vor allem um die
einzelnen Argumente im Ausdruck sowie um den gesamten Ausdruck setzen.
Weitere Klammern kommen je nach Bedarf oder Geschmack hinzu.

In deinem Fall sind die vielen Klammern natürlich nicht schädlich, sie
sehen nur ein wenig skurril aus.

Hannes J. schrieb:
> Wenn du es so machen willst, nimm wenigstens eine binäre Suche. D.h.
> teste zuerst auf den Mittelwert des (Rest)Intervalls.

Luther hat ja weiter oben schon indirekt folgende, nach diesem Prinzip
arbeitende und deswegen recht kompakte Lösung verlinkt, die ebenfalls
eine Compilezeitkonstante liefert, d.h. für die Dimensionierung von
Arrays benutzt werden kann:

#define NBITS2(n) ((n&2)?1:0)
#define NBITS4(n) ((n&(0xC))?(2+NBITS2(n>>2)):(NBITS2(n)))
#define NBITS8(n) ((n&0xF0)?(4+NBITS4(n>>4)):(NBITS4(n)))
#define NBITS16(n) ((n&0xFF00)?(8+NBITS8(n>>8)):(NBITS8(n)))
#define NBITS32(n) ((n&0xFFFF0000)?(16+NBITS16(n>>16)):(NBITS16(n)))
#define NBITS(n) (n==0?0:NBITS32(n)+1)

Sie stammt aus

  https://stackoverflow.com/questions/6834868/macro-to-compute-number-of-bits-needed-to-store-a-number-n

Ich nehme aber an, Ralf hat sie bereits gelesen. Im ging es ja zuletzt
nur noch darum, den Fehler in seiner eigenen Variante zu finden.

[(prx) A. K. (prx)]

Ralf schrieb:
> Muss ich mal ausprobieren. Ich würd ja jetzt zu gern fragen, wie man
> dann Portabilität sicherstellt, aber ich glaube das wäre ein eigener
> Thread :)

Natürlich nicht portabel, aber beim GCC verbreiteter als man vermuten 
sollte. Denn sogar GCC/AVR implementiert __builtin_clz. Beim ARM ist das 
ein Befehl, beim AVR eine Runtime-Funktion.

[rbx (Gast)]

Ralf schrieb:
> Mit direkten ASM-Befehlen habe ich noch nie gearbeitet.

Das brauchst du nicht extra schreiben, dass kann man am Eingangsposting 
ablesen.