Bitchange in einem Byte

[Unwissender69 (Gast)]

Bonjours,
Ich wollte mit einem kleinen Progrämmchen herausfinden wieviele Bits 
sich in einem Byte, im Vergleich zu anderen Byte geändert haben.
Ich benötige auch die Position der Bytes, bei dem sich nur ein Bit 
verändert hat.
Schön und gut, funktioniert auch soweit (siehe C-File im Anhang).
Wenn ich das so wie in der Datei auf meinen uC "draufknalle", benötigt 
er bei einem Sysclock von 30 MHz bereits 16 us dafür und das ist 
viiiiiiieeel zu lange.

Hat mir jemand einen Tipp wie man das ganze effizienter schreiben/machen 
könnte?

Wie gesagt, das File befindet sich im Anhang.


Salut Unwissender

[Peter II (Gast)]

um was für eine CPU geht es?

Bei einem Atmel ist das sehr ungünstig

if(weight[i] & ( 1 << k ) ) {

weil er immer nur 1 bit schieben kann.

[Unwissender69 (Gast)]

Peter II schrieb:
> um was für eine CPU geht es?

Sorry, das hatte ich vergessen. Um einen Arm Cortex M3.

[Frank K. (fchk)]

Tabellenorientiert gehts am schnellsten

static unsigned char bitsinbyte[256]={
  0,1,1,2,1,2,2,3,  // Anzahl 1-Bits im Byte
  1,2,2,3,1,3,2,4,
  .....
};

//...

//Compare value of the element in StartBytes[0][2][1] with all others of this part
weight[i]=(StartBytes[0][2][1]) ^ ( StartBytes[0][2][i]);
howmuch[i]=bitsinbyte[weight[i]];

Überlege Dir genau, ob DU weight[i] später noch brauchst. Wenn nicht, 
ersetze es durch weight.

Schau, ob Du nicht mit Pointern anstelle Arrayzugriffen arbeiten 
möchtest:

unsigned char* pweight=&weight[0];
unsigned char* phowmuch=&howmuch[0];

...

//Compare value of the element in StartBytes[0][2][1] with all others of this part
*pweight=(StartBytes[0][2][1]) ^ ( StartBytes[0][2][i]);
*phowmuch=bitsinbyte[*pweight];

...

pweight++;
phowmuch++;

z.B. Die Arrayzugriffe auf StartBytes[][][] sind in diesem Zuge auch 
noch optimierungsfähig.

fchk

[Unwissender69 (Gast)]

Frank K. schrieb:
> Tabellenorientiert gehts am schnellsten

Geht leider nicht. Benötige "StartBytes" im weiteren Programmablauf noch 
öfters.
Wenn möglich, dann möchte ich das schon so durchziehen.

Frank K. schrieb:
> Überlege Dir genau, ob DU weight[i] später noch brauchst. Wenn nicht,
> ersetze es durch weight.

Nein, wird nicht mehr benötigt. Hab es ersetzt.

Frank K. schrieb:
> Schau, ob Du nicht mit Pointern anstelle Arrayzugriffen arbeiten
> möchtest:

OK.. werde es mal schnell versuchen. Eventuell gehts damit schneller.

Aber ob ich durch diese Veränderungen die Ausführzeit halbieren oder 
sogar dritteln kann, werde ich gleich sehen! :)

Frank K. schrieb:
> Die Arrayzugriffe auf StartBytes[][][] sind in diesem Zuge auch
> noch optimierungsfähig.

Die Position (also z.B. StartBytes[0][1][2]) der Elemente bekomme ich 
von einer anderen Funktion übergeben. Die müssen vorher berechnet 
werden.

[Frank K. (fchk)]

Unwissender69 schrieb:
> Frank K. schrieb:
>> Tabellenorientiert gehts am schnellsten
>
> Geht leider nicht. Benötige "StartBytes" im weiteren Programmablauf noch
> öfters.
> Wenn möglich, dann möchte ich das schon so durchziehen.

Das meinte ich nicht. Ich meinte die Eliminierung der for-Schleife mit 
Bitschiebereien zum Abzählen der 1-Bits durch einen Tabellenzugriff.

[Sebastian (Gast)]

Das Zählen von geänderten Bits fällt in die Kategorie "Counting bits 
set".

Unter

  "Bit Twiddling Hacks"
  http://graphics.stanford.edu/~seander/bithacks.html

gibt es eine ganze Reihe von möglichen Ansätzen, einige davon abhängig 
von den Fähigkeiten der zur Verfügung stehenden CPU. Der naive Weg und 
die lookup table (LUT) wurden schon genannt.

"Brian Kernighan's way" ist ein portabler Ansatz, der ohne Tabelle 
auskommt und dessen Laufzeit von der Anzahl gesetzter Bits abhängt.

Viele Grüße,
Sebastian.

[Unwissender69 (Gast)]

Frank K. schrieb:
> Das meinte ich nicht. Ich meinte die Eliminierung der for-Schleife mit
> Bitschiebereien zum Abzählen der 1-Bits durch einen Tabellenzugriff.

Falsch verstanden. Sry!
Verstehe ich das so richtig, dass die Elemente der Tabelle angibt 
wieviele bits gesetzt sind?

Du möchtest also folgenden Code:

  
for(k = 0 ; k < BITS; k++ )
{
  if(*pweight & ( 1 << k ) ) 
    {

    //If one bit is set at this position, increment howmuch.
     phowmuch[i]++;
     }
}

mit der Tabelle ersetzten?

Klingt logisch.

Ich versuchs :)

[Unwissender69 (Gast)]

Sebastian schrieb:
> Unter
>
>   "Bit Twiddling Hacks"
>   http://graphics.stanford.edu/~seander/bithacks.html

Das ist ja wirklich eine mächtige Seite.
Vielen Dank, gleich mal zu den Favoriten hinzugefügt!

Da bei mir eh nur immer 3 Bits gesetzt werden (können), ist sicherlich
"Brian Kernighan's way" das Richtige.

Anbei der geänderte Code, diesmal mit *ptr und Brian Kernighan's way.
Nun hat die Nachwelt vielleicht auch etwas davon.


Vielen Dank an euch alle!


Salut