GCC Präprozessor soll Anzahl der Einsen in einem Byte ermitteln

[Phillip H. (philharmony)]

Servus,
ich habe ein Byte zur Zuweisung von Funktionen das ich vorab im Code 
setzen/ändern möchte.
Im Programm soll eine Schleife so oft laufen, wie Einsen in dem Byte 
stehen.
Wie kann ich per Makro o.ä. die Anzahl der gesetzten Bits in einem Byte 
rausfinden?

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

(((b)&0x80)!=0) + (((b)&0x40)!=0) + ...

[STK500-Besitzer (Gast)]

Wenn das nur zum Compilieren benutzt wird, kannst du lieber die Bits 
selber zählen. Das ist einfacher.

Wenn es im Programm auch variable eingesetzt werden soll, nimmst du eine 
Schleife von 1 bis 128 und multiplizierst den Schleifenwert immer mit 2.
Das ist dann eine Schleife, die 8 Mal durchlaufen wird.
In der Schleife vergleichst ("Logisches UND") du den Schleifenzähler mit 
deinem Byte und jedes Mal, wenn wenn der Vergleich positiv war, zählst 
du eine weitere Variable hoch.

[MaWin (Gast)]

Macros mögen keine Rekursion, also lohnt der K&R BitCOunt nicht, man 
kann es auf die übersichtliche Art machen:

#define bits7(x) (x&0x80?1:0)
#define bits6(x) (x&0x40?1:0)+bits7(x)
#define bits5(x) (x&0x20?1:0)+bits6(x)
#define bits4(x) (x&0x11?1:0)+bits5(x)
#define bits3(x) (x&8?1:0)+bits4(x)
#define bits2(x) (x&4?1:0)+bits3(x)
#define bits1(x) (x&2?1:0)+bits2(x)
#define bits(x) ((x&1?1:0)+bits1(x))

Anwendung:

n = bits(0x22)

[Phillip H. (philharmony)]

>Wenn das nur zum Compilieren benutzt wird, kannst du lieber die Bits
>selber zählen. Das ist einfacher.

Jo, das meine ich ja, und wie geht das?

[Uhu U. (uhu)]

Nimm das, was A.K. vorgeschlagen hat.

[Phillip H. (philharmony)]

Oh, den Beitrag hatte ich ganz übersehen.
Danke, werd ich mal so einbauen.
Grüße

[Sven P. (Gast)]

MaWin schrieb:
> Macros mögen keine Rekursion, also lohnt der K&R BitCOunt nicht, man
> kann es auf die übersichtliche Art machen:
>
> #define bits7(x) (x&0x80?1:0)
> #define bits6(x) (x&0x40?1:0)+bits7(x)
> #define bits5(x) (x&0x20?1:0)+bits6(x)
> #define bits4(x) (x&0x11?1:0)+bits5(x)
> #define bits3(x) (x&8?1:0)+bits4(x)
> #define bits2(x) (x&4?1:0)+bits3(x)
> #define bits1(x) (x&2?1:0)+bits2(x)
> #define bits(x) ((x&1?1:0)+bits1(x))
>
> Anwendung:
>
> n = bits(0x22)

Über diese Brücke würde ich nicht unbedingt gehen.

[MaWin (Gast)]

> Über diese Brücke würde ich nicht unbedingt gehen.

Mal abgesehen von 0x11,
Wir warten auf deinen besseren Vorschlag, aber da kommt sicher Nichts.
Den 4-zeiler hab ich wegen Unübersichtlichkeit absichtlich nicht 
gebracht.

[Phillip H. (philharmony)]

A.K. Vorschlag funktioniert doch wunderbar, ist nachvollziehbar und 
einfach zu definieren und liefert wie gewünscht die Anzahl der Einsen in 
einem Byte zurück. Was mehr? Es geht nur um eine 
Präprozessor-Geschichte, da ist eventuelles Optimieren eh nicht so 
wichtig...

[Karl H. (kbuchegg)]

Phillip Hommel schrieb:
> A.K. Vorschlag funktioniert doch wunderbar, ist nachvollziehbar und
> einfach zu definieren und liefert wie gewünscht die Anzahl der Einsen in
> einem Byte zurück. Was mehr? Es geht nur um eine
> Präprozessor-Geschichte, da ist eventuelles Optimieren eh nicht so
> wichtig...

Ich denke mit Optimieren hat das wenig zu tun.
Prärpozessor Makros sind generell gefährlich und man muss vorsichtig 
sein.

Wenn schon, würde ich noch eine inline Funktion drüberstülpen.

#define bits7(x) ( x&0x80?1:0 )
#define bits6(x) ( x&0x40?1:0 ) + bits7(x)
#define bits5(x) ( x&0x20?1:0 ) + bits6(x)
#define bits4(x) ( x&0x10?1:0 ) + bits5(x)
#define bits3(x) ( x&0x08?1:0 ) + bits4(x)
#define bits2(x) ( x&0x04?1:0 ) + bits3(x)
#define bits1(x) ( x&0x02?1:0 ) + bits2(x)
#define bits0(x) ( x&0x01?1:0 ) + bits1(x)

uint8_t bits( uint8_t arg )
{
  return bits0( arg );
}

damit mich Fälle wie

   i = bits( j++ );
   i = bits( 5 + 8 );

nicht in den Wahnsinn treiben.

[Johann L. (gjlayde)]

Phillip Hommel schrieb:
> Servus,
> ich habe ein Byte zur Zuweisung von Funktionen das ich vorab im Code
> setzen/ändern möchte.
> Im Programm soll eine Schleife so oft laufen, wie Einsen in dem Byte
> stehen.
> Wie kann ich per Makro o.ä. die Anzahl der gesetzten Bits in einem Byte
> rausfinden?

Bits zählt man am einfachsten so:

#include <stdint.h>

uint8_t bitcount (uint8_t x)
{
    uint8_t count = 0;

    while (x != 0)
    {
        count++;
        x &= x-1;
    }

    return count;
}

Analog wenn das in einer Schleife sein soll:

uint8_t bits;
uint8_t wert = ...;

for (bits = wert; bits; bits &= bits-1)
{
    // mach was 
}

Johann

[Phillip H. (philharmony)]

@ Johann,
ich möchte aber nicht zur Laufzeit sondern vorab die Bitzahl wissen da 
diese zur Laufzeit fix ist.
Spezialfälle kommen bei mir nicht vor da ich das ganze nur an drei oder 
vier stellen benutze und ich da nur ein fertiges Byte zw 0x00 und 0xff 
übergebe.
Da funktioniert das simple Makro doch hervorragend.

[Johann L. (gjlayde)]

Weitere Möglichkeutist bei Verwendung von gcc die Magie von 
__builtin_popcount (oder __builtin_popcount32?), für 32-Bit Variablen.

Oder weiterlesen in

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Johann

[Karl H. (kbuchegg)]

Es gäbe dann noch die Variante: Time For Space

Das Byte in 2 Nibbel zerlegen und damit in einer Tabelle die Anzahl der 
gesetzten Bits ablesen.

[Johann L. (gjlayde)]

Phillip Hommel schrieb:
> @ Johann,
> ich möchte aber nicht zur Laufzeit sondern vorab die Bitzahl wissen da
> diese zur Laufzeit fix ist.

Dann verwende __builtin_popcount. Wenn der Wert zur Compilezeit bekannt 
ist, wertet GCC das aus und ersetzt es durch die entsprechende 
Konstante.

Da Makro oben von A.K. müsste auch gehen; gcc sollte den entstehenden 
recht komplexen Ausdruck zu ner Konstanten falten (falls ihm nicht 
irgendwelche "Optimierungs-Kapriolen" zu Kopfe steigen).

Johann

[Sven P. (Gast)]

MaWin schrieb:
>> Über diese Brücke würde ich nicht unbedingt gehen.
>
> Mal abgesehen von 0x11,
> Wir warten auf deinen besseren Vorschlag, aber da kommt sicher Nichts.
> Den 4-zeiler hab ich wegen Unübersichtlichkeit absichtlich nicht
> gebracht.

Spar dir solches Gesülze und probier mal folgendes mit deiner Variante:

#define bits7(x) (x&0x80?1:0)
#define bits6(x) (x&0x40?1:0)+bits7(x)
#define bits5(x) (x&0x20?1:0)+bits6(x)
#define bits4(x) (x&0x11?1:0)+bits5(x)
#define bits3(x) (x&8?1:0)+bits4(x)
#define bits2(x) (x&4?1:0)+bits3(x)
#define bits1(x) (x&2?1:0)+bits2(x)
#define bits(x) ((x&1?1:0)+bits1(x))


int n = bits(1 + 0);

(Ja, da fehlen Klammern)

[MaWin (Gast)]

> probier mal folgendes mit deiner Variante

Brauch ich nicht, braucht Philipp nicht,
aber du kannst gerne Klammern spendieren.

Dein Beitrag war für'n Arsch.

[Sven P. (Gast)]

Dein Quelltext war nicht ausreichend getestet. Toll, ne?

Mir reichts, ist mir zu blöde.

[Vlad T. (vlad_tepesch)]

hört auf euch zu anzuflamen und bleibt sachlich


um das argument gehören immer klammern, ich würd also noch mehr setzen.
Selbst wenn es zum derzeitigen Zeitpunkt wirklich nur für einfache 
Konstanten genutzt wird.
Beim nächstem mal steckt man vielleicht was anderes rein und hat die 
Randbbedingungen schon wieder vergessen

#define bits7(x) ((x)&0x80?1:0)
#define bits6(x) ((x)&0x40?1:0)+bits7(x)
#define bits5(x) ((x)&0x20?1:0)+bits6(x)
#define bits4(x) ((x)&0x11?1:0)+bits5(x)
#define bits3(x) ((x)&8?1:0)+bits4(x)
#define bits2(x) ((x)&4?1:0)+bits3(x)
#define bits1(x) ((x)&2?1:0)+bits2(x)
#define bits(x) (((x)&1?1:0)+bits1(x))

obwohl ich das ganze in ein define packen würde, um den namespace nicht 
so vollzumüllen


Edit:
bits ist vielleicht auch nicht der geeigneteste Name dafür.

[Axel H. (axelh)]

Hallo Karl heinz,

> Wenn schon, würde ich noch eine inline Funktion drüberstülpen.

Den Tip werde ich mir mal merken. Das ist eigentlich eine recht elegante 
Lösung für gefährliche Macros, die ich bisher nicht kannte. Und eine 
gewisse Typensicherheit bekommt das ganze auch noch. DANKE!

Axel

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

Wobei man das dann auch nicht drüberstülpen muss, sondern gleich so ohne 
Verwendung eines Makros realisieren kann. Das hat neben einigen 
Vorteilen aber auch Nachteile.

Eine reine Konstantenrechnung im Makro wird immer vom Compiler fertig 
ausgewertet, eine Inline-Funktion abhängig von Optimierungsgrad, 
Compilerversion und Wasserstand. Und das Ergebnis einer 
Konstantenrechnung kann man in einem #if abfragen.

[Axel H. (axelh)]

Hallo A. K.,

das mir der Auswertung von Inline-Funktion durch den Compiler ist so 
eine Sache. Eigentlich sollte er das machen und eigentlich sollte der 
Optimierer das erkennen. Aber ich habe schon zu oft gesehen, dass 
Compiler das nicht machen bzw. schnell bei Verschachtelungen aufgeben. 
Und da hilft es dann auch nicht, dem Compiler dazu zu zwingen mit 
irgendwelchen Aufruf-Parametern oder Funktions-Attributen.
Ausserdem kommt auch noch hinzu, dass bei einem Debug-Build 
normalerweise nicht Optimiert wird, damit ich Dinge nachvollziehbar 
bleiben. Trotzdem sollten aber so "einfache" Sachen wie das Zählen von 
Bits oder das berechnen von Offsets vom Compiler erledigt werden - sonst 
passt der Code einfach nicht in den Chip. Dann sind Macro die bessere 
Wahl und ein inline-Wrapper macht das ganze noch etwas sicherer.

Aber über sowas kann man sich sowieso vortrefflich streiten. Und 
vielleicht wird das mit LLVM Compilern irgendwann mal besser .... ;)

Axel