Darf man so Bits zählen?

Es ist weder "Good Style" noch OK.

a) Bei der Addition müsstest du shiften. Sonst rechnest du 1 + 1 + 1 + 0 
+ 0 + 1, was auch immer, aber du müsstest rechnen 1 + 2 + 4 + ...

Und auch durch das Schieben kriegst du die einzelnen Bits nicht. Du 
musst dort mit einer Maske arbeiten. Der &-Operator ist dein Freund.

Kleiner Programmierer schrieb:
> Hallo,
> ich hab dies programmiert, es scheint auf dem AVRstudio4 & ATmega128
> zu funktionieren.
>

1

> struct{

2

>   unsigned char b0:1;

3

>   unsigned char b1:1;

4

>   unsigned char b2:1;

5

>   unsigned char b3:1;

6

>   unsigned char b4:1;

7

>   unsigned char b5:1;

8

>   unsigned char b6:1;

9

>   unsigned char b7:1;

10

> }Z;

11

> 

12

> Z.b0 = Zahl >> 0;

13

> Z.b1 = Zahl >> 1;

14

> Z.b2 = Zahl >> 2;

15

> Z.b3 = Zahl >> 3;

16

> Z.b4 = Zahl >> 4;

17

> Z.b5 = Zahl >> 5;

18

> Z.b6 = Zahl >> 6;

19

> Z.b7 = Zahl >> 7;

20

> 

21

> Zahl = Z.b0 + Z.b1 + Z.b2 + Z.b3 + Z.b4 + Z.b5 + Z.b6 + Z.b7;

22

>

> Aber ist es so OK?

Wenn du die Anzahl der 1 Bits haben willst, dann ist das schon ok. Aber 
es ist maximal kompliziert.

> Is this good style?

Meiner Meinung nach nicht.

Einfachere, durchschaubarere Lösung

1

   Anzahl = ( Zahl & 0x01 ) ? 1 : 0     +

2

            ( Zahl & 0x02 ) ? 1 : 0     +

3

            ( Zahl & 0x04 ) ? 1 : 0     +

4

            ( Zahl & 0x08 ) ? 1 : 0     +

5

            ( Zahl & 0x10 ) ? 1 : 0     +

6

            ( Zahl & 0x20 ) ? 1 : 0     +

7

            ( Zahl & 0x40 ) ? 1 : 0     +

8

            ( Zahl & 0x80 ) ? 1 : 0;

Ein anderer Ansatz besteht darin, die 8 Bit einer Zahl, in 2 4 Bit Teile 
zu zerlegen und für jeden der 4 Bit Teile die Anzahl der 1 Bits getrennt 
festzustellen. Da es mit 4 Bit nur 16 mögliche Kombinationen gibt, kann 
man dafür eine fertige Tabelle benutzen

1

                           // 0, 1, 2, 3, 4, 5, 6, 7,

2

unsigned char NrBits[16] = {  0, 1, 1, 2, 1, 2, 2, 3,

3

                           // 8, 9, A, B, C, D, E, F

4

                              1, 2, 2, 3, 2, 3, 3, 4 };

5

6

unsigned char BitsPerNibble( unsigned char Nibble )

7

{

8

  return NrBits[ Nibble & 0x0F ];

9

}

10

11

unsigned char BitsPer Byte( unsigned char Byte )

12

{

13

  return BitsPerNibble( Byte >> 4 ) +

14

         BitsPerNibble( Byte );

15

}

Einfacher ist folgende Variante mit einer Schleife:

1

int nbits=0;

2

int i=0;

3

for(int i; i < 8; ++i)

4

 if (zahl & (1 << i))

5

  nbits++;

alternativ ginge auch so was:

1

int nbits=0;

2

int i=0;

3

for(int i; i < 8; ++i)

4

 nbits += (zahl >> i) & 1;

Helfer schrieb:
> Scheint mir zu kompliziert. Was meinst du zu folgendem Fragment?
>

1

> uint8_t bits; // Anzahl gesetzter Bits

2

>

Am besten noch bits zu 0 initializieren. Ist besser als meine Loesung 
:-)

Hier noch der Klassiker:

1

int count_bits(int word) {

2

  int n = 0;

3

4

  while(word) {

5

    n++;

6

    word &= word - 1;

7

  }

8

  return n;

9

}

Vorteil: Die Anzahl der Schleifendurchläufe ist gleich der Anzahl der
gesetzten Bits, so dass die Funktion in den meisten Fällen schneller zum
Ergebnis kommt, als wenn jedes Bit abgeklappert wird.

Das

1

    word &= word - 1;

ist eine interessante Operation.
Ich kann sie mathematisch nicht begründen, aber es scheint so, dass 
diese Operation immer das am weitesten rechts stehende 1-Bit löscht.


Beispiel: 4 Bit Zahlen

   0001 & 0000  = 0000
   0010 & 0001  = 0000
   0011 & 0010  = 0010
   0100 & 0011  = 0000
   0101 & 0100  = 0100
   0110 & 0101  = 0100
   0111 & 0110  = 0110
   1000 & 0111  = 0000
   1001 & 1000  = 1000
   1010 & 1001  = 1000
   1011 & 1010  = 1010
   1100 & 1011  = 1000
   1101 & 1100  = 1101
   1110 & 1101  = 1100
   1111 & 1110  = 1110

1

A       = ...xxxxx100000...

2

A-1     = ...xxxxx011111...

3

A&(A-1) = ...xxxxx000000...

Es wird also die am weitesten rechts stehende 1 genullt (falls eine 1 
vorhanden ist)

Yalu X. schrieb:
> Hier noch der Klassiker:
>[...]
> Vorteil: Die Anzahl der Schleifendurchläufe ist gleich der Anzahl der
> gesetzten Bits, so dass die Funktion in den meisten Fällen schneller zum
> Ergebnis kommt, als wenn jedes Bit abgeklappert wird.
Beachtlich, wie kommt man auf so etwas?

Johann L. schrieb:
>

1

> A       = ...xxxxx100000...

2

> A-1     = ...xxxxx011111...

3

> A&(A-1) = ...xxxxx000000...

4

>

>
> Es wird also die am weitesten rechts stehende 1 genullt (falls eine 1
> vorhanden ist)

Danke, dass du mir die Tomaten von den Augen genommen hast.
Jetzt seh ich klarer :-)

Luk4s K. schrieb:

> Beachtlich, wie kommt man auf so etwas?

Da kann man ne Wissenschaft draus machen ;-)

http://gurmeet.net/puzzles/fast-bit-counting-routines/

Wenn du noch einiges an Platz hast, könnte auch eine Lookup table gehen.
Ein Byte hat nur 256 Zustände.

Hier mal ein benchmark was dir helfen könnte.

(Worauf willst du optimieren? Platz oder Geschwindigkeit?)

Luk4s K. schrieb:
> Beachtlich, wie kommt man auf so etwas?

Jeder, der C aus dem K&R-Buch gelernt hat, sollte den Trick kennen ;-)

Wie in Johanns Link

  http://gurmeet.net/puzzles/fast-bit-counting-routines/

nachzulesen ist, wurde die Methode aber schon viel früher, nämlich 1960
von Peter Wegner veröffentlicht.