Bit Array in C

Peter Zz schrieb:

> Gibt es ein Workaround, oder muß ich es mit Hardcore-Bitnapperei machen?


Na ja. So schwer ist es dann auch wieder nicht, die Bits in 8 Bit 
Häppchen anzuordnen und aus der gewünschten Bitnummer die Adresse eines 
8 Bit Happens und die Nummer dieses Bits in diesem Happen zu errechnen.

In einer Strasse stehen 10 Häuser (durchnummeriert).
In derselben Strasse wohnen 40 Menschen (ebenfalls durchnummeriert), 
wobei jeweils 4 Menschen in einem Haus wohnen.

In welchem Haus (Nummer?) wohnt daher Bewohner 25 und wenn dort alle 
aufgefädelt auf der Couch sitzen ... die wievielte Person auf der Couch 
ist das dann?
Und der drückst du dann ein Bier in die Hand oder befragst sie, ob sie 
schon ein Bier hatte.

Karl Heinz Buchegger schrieb:
> In welchem Haus (Nummer?) wohnt daher Bewohner 25 und wenn dort alle
> aufgefädelt auf der Couch sitzen ... die wievielte Person auf der Couch
> ist das dann?

Mann Karl, ich glaube du sitzt auch schon etwas länger. Auf der Couch.

Peter Zz schrieb:
> Sauger schrieb:
>> #define SETBIT(ByteArr,Bit) ((ByteArr)[Bit/8] |=  (1<<(Bit%8)))
>
> Thx.
>
> Würden Compiler das in jedem Fall immer effizient umsetzen,

Solange du die Bitnummer als unsigned definierst, machen das Compiler 
seit ungefähr 35 Jahren standardmässig und ohne große Probleme :-)

Wenn du dir Sorgen um die Effizient machst, dann solltest du dir lieber 
Sorgen um den variablen Shift machen. Denn wenn die CPU den nicht 
unterstützt (und die AVR tun das nicht), dann wird das eine teure 
Operation. Da ist eine Array mit Bitmasken, welches von der Bitnummer 
indiziert wird, schon besser.

Wie alle Daten, die nicht besonders (auf nicht Standard-konforme Weise) 
markiert sind, liegt auch dieser String im RAM.

wird der code nich  schneller wenn man die Makros folgender massen 
verbessert:

Da zb beim MSP430 empfohle wird / und % zu umgehn.

1

#define SETBIT(ByteArr,Bit) ((ByteArr)[Bit>>3] |=  (1<<(Bit&0x07)))

2

#define CLRBIT(ByteArr,Bit) ((ByteArr)[Bit>>3] &= ~(1<<(Bit&0x07)))

3

#define TSTBIT(ByteAry,Bit) ((ByteAry)[Bit>>3] &   (1<<(Bit&0x07)))

Anton G. schrieb:
> wird der code nich  schneller wenn man die Makros folgender massen
> verbessert:

Nochmal.
Compilerbauer sind keine Trottel! Die kennen diese Spielchen alle. Und 
noch ein paar mehr, von denen DU noch nie gehört hast.

Dreh die Optimierung deines Compilers auf und wenn es möglich ist, eine 
Division durch etwas Besseres zu ersetzen, dann macht das der Compiler. 
So etwas ist eine (triviale) Standardoptimierung seit über 45 Jahren. 
Wenn er es nicht tut, dann wirf das Klumpert von Compiler auf den Müll 
und nimm einen besseren Compiler.

Viel wichtiger ist, dass du die richtigen Datentypen nimmst! Division 
durch Schieben zu ersetzen, geht nur bei unsigned Typen. Bei signed 
Datentypen unterscheidet sich das Ergebnis von Dividieren und Schieben 
bei negativen Zahlen. Daher darf der Compiler hier keine Ersetzung 
vornehmen. Wenn du aber sowieso nur positive Zahlen hast, dann hätte man 
von vorne herein bereits einen unsigned Datentyp verwenden sollen und 
dann kann der Compiler das dann im Falle von 2-er Potenzen auch wieder 
durch Schieben ersetzen.


Du schreibst die Anweisungen so, wie sie im Zusammenhang am logischten 
sind. Wenn die Aufgabenstellung dergestalt ist, dass eine Division 
gefordert ist, dann schreib auch Division. Wenn die Aufgabenstellung 
sich im Rahmen von Bitpfriemelei abspielt, dann nimm Schieben. Hier 
haben wir es mit einer Auftailung in Gruppen zu tun, wofür Division die 
logische sinnvolle Operation ist. Den Rest überlass dem Compiler. Das 
ist nichts worüber man sich als Anwendungsprogrammierer den Kopf 
zerbrechen muss.

Peter Zz schrieb:
> Manche µP's und µC's haben dafür im Instruction Set zwei
> unterschiedliche Schiebeoperationen:
> ASR = Arithmetic Shift Right und
> LSR = Logical    Shift Right

Das alleine reicht aber nicht. Etwas mehr Aufwand bleibt trotzdem.

1

#include <stdint.h>

2

3

int8_t div(int8_t x)

4

{

5

  return x/4;

6

}

7

8

uint8_t udiv(uint8_t x)

9

{

10

  return x/4;

11

}

Mit gcc Optimierung -Os übersetzt gibt es das:

1

00000000 <div>:

2

   0:  87 fd         sbrc  r24, 7

3

   2:  8d 5f         subi  r24, 0xFD  ; 253

4

   4:  85 95         asr  r24

5

   6:  85 95         asr  r24

6

   8:  08 95         ret

7

8

0000000a <udiv>:

9

   a:  86 95         lsr  r24

10

   c:  86 95         lsr  r24

11

   e:  08 95         ret

Peter Zz schrieb:
> Will nicht klugscheissern, aber es geht auch bei signed, hab es eben
> ausprobiert.
>
> Beim Aritmetischen Schieben nach rechts wird Bit7 durch eine Kopie des
> Vorzeichen-Bits = Bit7 ersetzt.

Das rundet aber in die falsche Richtung.

1

MOV r0, #-1

2

ASR r0, r0, #1 ; -1/2 sollte 0 ergeben

3

BNE Error      ; Hoppla!

--
Marcus

Marcus Harnisch schrieb:
> Peter Zz schrieb:
>>
>> Beim Aritmetischen Schieben nach rechts wird Bit7 durch eine Kopie des
>> Vorzeichen-Bits = Bit7 ersetzt.
>
> Das rundet aber in die falsche Richtung.

Nein tut es nicht. Denn ein arithmetischer Shift ist eben keine 
Ganzzahl-Division. Steht ober schon geschrieben das.

Johann L. schrieb:
> Denn ein arithmetischer Shift ist eben keine Ganzzahl-Division.

Genau das war doch die Aussage meines Posts. "Rundet falsch" aus der 
Sichtweise einer Division.

> Steht ober schon geschrieben das.

Richtig, aber Peter Zz bestand darauf, dass das auch bei signed 
funktionieren würde.

--
Marcus