AVR-Tutorial: Arithmetik8

Wechseln zu: Navigation, Suche

Eine der Hauptaufgaben eines Mikrokontrollers bzw. eines Computers allgemein, ist es, irgendwelche Berechnungen anzustellen. Der Löwenanteil an den meisten Berechnungen entfällt dabei auf einfache Additionen bzw. Subtraktionen. Multiplikationen bzw. Divisionen kommen schon seltener vor, bzw. können oft durch entsprechende Additionen bzw. Subtraktionen ersetzt werden. Weitergehende mathematische Konstrukte werden zwar auch ab und an benötigt, können aber in der Assemblerprogrammierung durch geschickte Umformungen oft vermieden werden.

Hardwareunterstützung

Praktisch alle Mikroprozessoren unterstützen Addition und Subtraktion direkt in Hardware, das heißt: Sie haben eigene Befehle dafür. Einige bringen auch Unterstützung für eine Hardwaremultiplikation mit (so zum Beispiel der ATmega8), während Division in Hardware schon seltener zu finden ist.

8 Bit versus 16 Bit

In diesem Abschnitt des Tutorials wird gezielt auf 8 Bit Arithmetik eingegangen, um zunächst die Grundlagen des Rechnens mit einem µC zu zeigen. Die Erweiterung von 8 Bit auf 16 Bit Arithmetik ist in einigen Fällen wie Addition und Subtraktion trivial, kann sich aber bei Multiplikation und Division in einem beträchtlichen Codezuwachs niederschlagen.

Der im Tutorial verwendete ATmega8 besitzt eine sog. 8-Bit Architektur. Das heißt, dass seine Rechenregister (mit Ausnahmen) nur 8 Bit breit sind und sich daher eine 8-Bit Arithmetik als die natürliche Form der Rechnerei auf diesem Prozessor anbietet. Berechnungen, die mehr als 8 Bit erfordern, müssen dann durch Kombinationen von Rechenvorgängen realisiert werden. Eine Analogie wäre z. B. das Rechnen, wie wir alle es in der Grundschule gelernt haben. Auch wenn wir in der Grundschule (in den Anfängen) nur die Additionen mit Zahlen kleiner als 10 auswendig gelernt haben, so können wir dennoch durch die Kombination von mehreren derartigen Additionen beliebig große Zahlen addieren. Das gleiche gilt für Multiplikationen. In der Grundschule musste wohl jeder von uns das 'Kleine Einmaleins' auswendig lernen, um Multiplikationen im Zahlenraum bis 100 quasi 'in Hardware' zu berechnen. Und doch können wir durch Kombinationen solcher Einfachmultiplikationen und zusätzlichen Additionen in beliebig große Zahlenräume vorstoßen.

Die Einschränkung auf 8 Bit ist also keineswegs eine Einschränkung in dem Sinne, dass es eine prinzipielle Obergrenze für Berechnungen gäbe. Sie bedeutet lediglich eine obere Grenze dafür, bis zu welchen Zahlen in einem Rutsch gerechnet werden kann. Alles, was darüber hinausgeht, muss dann mittels Kombinationen von Berechnungen gemacht werden.

8-Bit Arithmetik ohne Berücksichtigung eines Vorzeichens

Die Bits des Registers besitzen dabei eine Wertigkeit, die sich aus der Stelle des Bits im Byte ergibt. Dies ist völlig analog zu dem uns vertrauten Dezimalsystem. Auch dort besitzt eine Ziffer in einer Zahl eine bestimmte Wertigkeit, je nach dem, an welcher Position diese Ziffer in der Zahl auftaucht. So hat z. B. die Ziffer 1 in der Zahl 12 die Wertigkeit 'Zehn', während sie in der Zahl 134 die Wertigkeit 'Hundert' besitzt. Und so wie im Dezimalsystem die Wertigkeit einer Stelle immer das Zehnfache der Wertigkeit der Stelle unmittelbar rechts von ihr ist, so ist im Binärsystem die Wertigkeit einer Stelle immer das 2-fache der Stelle rechts von ihr.

Die Zahl 4632 im Dezimalsystem kann also so aufgefasst werden:

  4632  =     4 * 1000          ( 1000 = 10 hoch 3 )
           +  6 * 100           (  100 = 10 hoch 2 )
           +  3 * 10            (   10 = 10 hoch 1 )
           +  2 * 1             (    1 = 10 hoch 0 )

Die Umwandlung von Binär in das Dezimalystem

Völlig analog ergibt sich daher folgendes für z. B. die 8 Bit Binärzahl 0b10011011 (um Binärzahlen von Dezimalzahlen zu unterscheiden, wird ein 0b vorangestellt):

 0b10011011     =    1 * 128    ( 128 = 2 hoch 7 )
                  +  0 * 64     (  64 = 2 hoch 6 )
                  +  0 * 32     (  32 = 2 hoch 5 )
                  +  1 * 16     (  16 = 2 hoch 4 )
                  +  1 * 8      (   8 = 2 hoch 3 )
                  +  0 * 4      (   4 = 2 hoch 2 )
                  +  1 * 2      (   2 = 2 hoch 1 )
                  +  1 * 1      (   1 = 2 hoch 0 )

Ausgerechnet (um die entsprechende Dezimalzahl zu erhalten) ergibt das 128 + 16 + 8 + 2 + 1 = 155. Die Binärzahl 0b10011011 entspricht also der Dezimalzahl 155. Es ist wichtig, sich klar zu machen, dass es zwischen Binär- und Dezimalzahlen keinen grundsätzlichen Unterschied gibt. Beides sind nur verschiedene Schreibweisen für das Gleiche: Eine Zahl. Während wir Menschen an das Dezimalsystem gewöhnt sind, ist das Binärsystem für einen Computer geeigneter, da es nur aus den 2 Ziffern 0 und 1 besteht, welche sich leicht in einem Computer darstellen lassen (Spannung, keine Spannung).

Welches ist nun die größte Zahl, die mit 8 Bit dargestellt werden kann? Dabei handelt es sich offensichtlich um die Zahl 0b11111111. In Dezimalschreibweise wäre das die Zahl

   0b11111111   =   1  *  128
                  + 1  *  64
                  + 1  *  32
                  + 1  *  16
                  + 1  *  8
                  + 1  *  4
                  + 1  *  2
                  + 1  *  1

oder ausgerechnet: 255

Wird also mit 8 Bit Arithmetik betrieben, wobei alle 8 Bit als signifikante Ziffern benutzt werden (also kein Vorzeichenbit, dazu später mehr), so kann damit im Zahlenraum 0 bis 255 gerechnet werden.


   Binär          Dezimal               Binär         Dezimal
  0b00000000        0                 0b10000000       128
  0b00000001        1                 0b10000001       129
  0b00000010        2                 0b10000010       130
  0b00000011        3                 0b10000011       131
  0b00000100        4                 0b10000100       132
  0b00000101        5                 0b10000101       133
    ...                                      ...
  0b01111100      124                 0b11111100       252
  0b01111101      125                 0b11111101       253
  0b01111110      126                 0b11111110       254
  0b01111111      127                 0b11111111       255

Die Umwandlung von Dezimal in das Binärsystem

Aus dem vorhergehenden ergibt sich völlig zwanglos die Vorschrift, wie Binärzahlen ins Dezimalsystem umgewandelt werden können (nicht vergessen: Die Zahl selber wird ja gar nicht verändert. Binär- und Dezimalsystem sind ja nur verschiedene Schreibweisen): Durch Anwendung der Vorschrift, wie denn eigentlich ein Stellenwertsystem aufgebaut ist. Aber wie macht man den umgekehrten Schritt, die Wandlung vom Dezimal ins Binärsystem. Der Weg führt über die Umkehrung des vorhergehenden Prinzips. Fortgesetzte Division durch 2

Es sei die Zahl 92 ins Binärsystem zu wandeln.

    92 / 2   =   46   Rest 0
    46 / 2   =   23   Rest 0
    23 / 2   =   11   Rest 1
    11 / 2   =    5   Rest 1
     5 / 2   =    2   Rest 1
     2 / 2   =    1   Rest 0
     1 / 2   =    0   Rest 1

Die Division wird solange durchgeführt, bis sich ein Divisionergebnis von 0 ergibt. Die Reste, von unten nach oben gelesen, ergeben dann die Binärzahl. Die zu 92 gehörende Binärzahl lautet also 1011100. Es wird noch eine führende 0 ergänzt um sie auf die standardmässigen 8-Bit zu bringen: 0b01011100.

8-Bit Arithmetik mit Berücksichtigung eines Vorzeichens

Soll mit Vorzeichen (also positiven und negativen Zahlen) gerechnet werden, so erhebt sich die Frage: Wie werden eigentlich positive bzw. negative Zahlen dargestellt? Alles was wir haben sind ja 8 Bit in einem Byte.

Problem der Kodierung des Vorzeichens

Die Lösung des Problems besteht darin, dass ein Bit zur Anzeige des Vorzeichens benutzt wird. Im Regelfall wird dazu das am weitesten links stehende Bit benutzt. Von den verschiedenen Möglichkeiten, die sich hiermit bieten, wird in der Praxis fast ausschließlich mit dem sog. 2-er Komplement gearbeitet, da es Vorteile bei der Addition bzw. Subtraktion von Zahlen bringt. In diesem Fall muß nämlich das Vorzeichen einer Zahl überhaupt nicht berücksichtigt werden. Durch die Art und Weise der Bildung von negativen Zahlen kommt am Ende das Ergebnis mit dem korrekten Vorzeichen heraus.

2-er Komplement

Das 2-er Komplement verwendet das höchstwertige Bit eines Byte, das sog. MSB (= Most Significant Bit) zur Anzeige des Vorzeichens. Ist dieses Bit 0, so ist die Zahl positiv. Ist es 1, so handelt es sich um eine negative Zahl. Die 8-Bit Kombination 0b10010011 stellt also eine negative Zahl dar, wenn und nur wenn diese Bitkombination überhaupt als vorzeichenbehaftete Zahl aufgefasst werden soll. Anhand der Bitkombination alleine ist es also nicht möglich, eine definitive Aussage zu treffen, ob es sich um eine vorzeichenbehaftete Zahl handelt oder nicht. Erst wenn durch den Zusammenhang klar ist, dass man es mit vorzeichenbehafteten Zahlen zu tun hat, bekommt das MSB die Sonderbedeutung des Vorzeichens.

Um bei einer Zahl das Vorzeichen zu wechseln, geht man wie folgt vor:

  • Zunächst wird das 1-er Komplement gebildet, indem alle Bits umgedreht werden. Aus 0 wird 1 und aus 1 wird 0
  • Danach wird aus diesem Zwischenergebnis das 2-er Komplement gebildet, indem noch 1 addiert wird.

Diese Vorschrift kann immer dann benutzt werden, wenn das Vorzeichen einer Zahl gewechselt werden soll. Er macht aus positiven Zahlen negative und aus negativen Zahlen positive.

Beispiel: Es soll die Binärdarstellung für -92 gebildet werden. Dazu benötigt man zunächst die Binärdarstellung für +92, welche 0b01011100 lautet. Diese wird jetzt nach der Vorschrift für 2-er Komplemente negiert und damit negativ gemacht.

  0b01011100            Ausgangszahl
  0b10100011            1-er Komplement, alle Bits umdrehen
  0b10100100            noch 1 addieren

Die Binärdarstellung für -92 lautet also 0b10100100. Das gesetzte MSB weist diese Binärzahl auch tatsächlich als negative Zahl aus.

Beispiel: Gegeben sei die Binärzahl 0b00111000, welche als vorzeichenbehaftete Zahl anzusehen ist. Welcher Dezimalzahl entspricht diese Binärzahl?

Da das MSB nicht gesetzt ist, handelt es sich um eine positive Zahl und die Umrechnung kann wie im Fall der vorzeichenlosen 8-Bit Zahlen erfolgen. Das Ergebnis lautet also +56 ( = 0 * 128 + 0 * 64 + 1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 0 * 1 )

Beispiel: Gegeben sei die Binärzahl 0b10011001, welche als vorzeichenbehaftete Zahl anzusehen ist. Welcher Dezimalzahl entspricht diese Binärzahl?

Da das MSB gesetzt ist, handelt es sich um eine negative Zahl. Daher wird diese Zahl zunächst negiert um dadurch eine positive Zahl zu erhalten.

   0b10011001       Originalzahl
   0b01100110       1-er Komplement, alle Bits umdrehen
   0b01100111       2-er Komplement, noch 1 addiert

Die zu 0b10011001 gehörende positive Binärzahl lautet also 0b01100111. Da es sich um eine positive Zahl handelt, kann sie wiederum ganz normal, wie vorzeichenlose Zahlen, in eine Dezimalzahl umgerechnet werden. Das Ergebnis lautet 103 ( = 0 * 128 + 1 * 64 + 1 * 32 + 0 * 16 + 0 * 8 + 1 * 4 + 1 * 2 + 1 * 1). Da aber von einer negativen Zahl ausgegangen wurde, ist 0b10011001 die binäre Darstellung der Dezimalzahl -103.

Beispiel: Gegeben sei dieselbe Binärzahl 0b10011001. Aber diesmal sei sie als vorzeichenlose Zahl aufzufassen. Welcher Dezimalzahl entspricht diese Binärzahl?

Da die Binärzahl als vorzeichenlose Zahl aufzufassen ist, hat das MSB keine spezielle Bedeutung. Die Umrechnung erfolgt also ganz normal: 0b10011001 = 1 * 128 + 0 * 64 + 0 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1 = 153.

Beispiel: Wie lautet die Binärzahl zu -74?

Da es sich hier offensichtlich im eine vorzeichenbehaftete Zahl handelt, müssen die Regeln des 2-er Komplemnts angewendet werden. Zunächst ist also die Binärrepräsentierung von +74 zu bestimmen, welche dann durch Anwendung des 2-er Komplements negiert wird.

 74 / 2 = 37  Rest 0
 37 / 2 = 18  Rest 1
 18 / 2 =  9  Rest 0
  9 / 2 =  4  Rest 1
  4 / 2 =  2  Rest 0
  2 / 2 =  1  Rest 0
  1 / 2 =  0  Rest 1

Die Binärdarstellung für +74 lautet daher 0b01001010

   0b01001010     +74
   0b10110101     1-er Komplement, alle Bits umdrehen
   0b10110110     noch 1 addieren

Die Binärdarstellung für -74 lautet daher 0b10110110

Arithmetikflags

Im Statusregister des Prozessors gibt es eine Reihe von Flags, die durch Rechenergebnisse beeinflusst werden, bzw. in Berechnungen einfließen können.

Carry

Das Carry-Flag C zeigt an, ob bei einer Berechnung mit vorzeichenlosen Zahlen ein Über- oder Unterlauf erfolgt ist, d.h. das Ergebnis der Berechnung liegt außerhalb des darstellbaren Bereiches 0...255.

Wie das?

Angenommen es müssen zwei 8-Bit-Zahlen addiert werden.

   10100011
 + 11110011
  ---------
  110010110

Das Ergebnis der Addition umfasst neun Bit und liegt außerhalb des in einem Register darstellbaren Zahlenbereiches 0...255; die Addition ist übergelaufen.

Werden dieselben Zahlen subtrahiert,

   10100011
 - 11110011
  ---------
   10110000

verbleibt an der höchstwertigsten Stelle ein "geborgtes" Bit, welches durch das Carry angezeigt wird.

Signed- und Overflowflag

Wird mit vorzeichenbehafteten Zahlen gerechnet, so wird das Verlassen des 8-Bit-Zahlenbereiches -128...+127 durch die Flags S und V angezeigt. Der Prozessor selbst unterscheidet nicht zwischen vorzeichenlosen und -behafteten Zahlen. Der Programmierer legt durch Wahl der ausgewerteten Flags (C bei vorzeichenlosen bzw. S/V bei vorzeichenbehafteten) die Interpretation der Zahlen fest.

Weitere Flags

Das Zero-Flag Z wird gesetzt, wenn das 8-Bit-Ergebnis der Berechnung null ist. Dies kann bei der Addition auch durch Überlauf geschehen, was durch ein zusätzliches Carryflag angezeigt wird.

Das Negative-Flag N wird gesetzt, wenn im Ergebnis das höchstwertige Bit gesetzt ist. Bei vorzeichenbehafteter Arithmetik ist dies als negative Zahl zu interpretieren, sofern nicht durch das V-Flag ein Verlassen des Zahlbereichs angezeigt wird.

Das Half-Carry-Flag H zeigt, analog zum Carry-Flag, einen Übertrag zwischen Bit 3 und 4 an. Dies kann in speziellen Anwendungen (z. B. zwei simultane Vier-Bit-Berechnungen mit einem Befehl) nützlich sein.

Übersicht über die arithmetischen Flags

Ergebnis des Befehls ADD Rd, Rr

         Rr|    0 |    1 |   64 |  127 |  128 |  129 |  192 |  255
  Rd       |(  +0)|(  +1)|( +64)|(+127)|(-128)|(-127)|( -64)|(  -1)
 ----------+------+------+------+------+------+------+------+------
   0 (  +0)|    Z |      |      |      |S N   |S N   |S N   |S N
   1 (  +1)|      |      |      | VN   |S N   |S N   |S N   |   CZ
  64 ( +64)|      |      | VN   | VN   |S N   |S N   |   CZ |   C
 127 (+127)|      | VN   | VN   | VN   |S N   |   CZ |   C  |   C
 128 (-128)|S N   |S N   |S N   |S N   |SV CZ |SV C  |SV C  |SV C
 129 (-127)|S N   |S N   |S N   |   CZ |SV C  |SV C  |SV C  |S NC
 192 ( -64)|S N   |S N   |   CZ |   C  |SV C  |SV C  |S NC  |S NC
 255 (  -1)|S N   |   CZ |   C  |   C  |SV C  |S NC  |S NC  |S NC

Man erkennt: C=1 genau dann wenn die Addition Rd + Rr mit vorzeichenlosen Zahlen überläuft. V=1 genau dann wenn die Addition mit vorzeichenbehafteten Zahlen überläuft.


Ergebnis des Befehls SUB Rd, Rr bzw. CP Rd, Rr

         Rr|    0 |   63 |   64 |  127 |  128 |  191 |  192 |  255
  Rd       |(  +0)|( +63)|( +64)|(+127)|(-128)|( -65)|( -64)|(  -1)
 ----------+------+------+------+------+------+------+------+------
   0 (  +0)|    Z |S NC  |S NC  |S NC  | VNC  |   C  |   C  |   C
  63 ( +63)|      |    Z |S NC  |S NC  | VNC  | VNC  |   C  |   C
  64 ( +64)|      |      |    Z |S NC  | VNC  | VNC  | VNC  |   C
 127 (+127)|      |      |      |    Z | VNC  | VNC  | VNC  | VNC
 128 (-128)|S N   |SV    |SV    |SV    |    Z |S NC  |S NC  |S NC
 191 ( -65)|S N   |S N   |SV    |SV    |      |    Z |S NC  |S NC
 192 ( -64)|S N   |S N   |S N   |SV    |      |      |    Z |S NC
 255 (  -1)|S N   |S N   |S N   |S N   |      |      |      |    Z

Man erkennt: C=1 genau dann wenn die Subtraktion Rd - Rr mit vorzeichenlosen Zahlen unterläuft; äquivalent dazu ist Rd < Rr (vorzeichenlos). S=1 genau dann wenn die Subtraktion mit vorzeichenbehafteten Zahlen unterläuft bzw. Rd > Rr (vorzeichenbehaftet).

Inkrementieren / Dekrementieren

Erstaunlich viele Operationen in einem Computer-Programm entfallen auf die Operationen 'Zu einer Zahl 1 addieren' bzw. 'Von einer Zahl 1 subtrahieren'. Dementsprechend enthalten die meisten Mikroprozessoren die Operationen Inkrementieren (um 1 erhöhen) bzw. Dekrementieren (um 1 verringern) als eigenständigen Assemblerbefehl. So auch der ATmega8.

AVR-Befehle

 
        inc  r16

bzw.

 
        dec  r16

Die Operation ist einfach zu verstehen. Das jeweils angegebene Register (hier wieder am Register r16 gezeigt) wird um 1 erhöht bzw. um 1 verringert. Dabei wird die Zahl im Register als vorzeichenlose Zahl angesehen. Enthält das Register bereits die größtmögliche Zahl (0b11111111 oder dezimal 255), so erzeugt ein weiteres Inkrementieren die kleinstmögliche Zahl (0b00000000 oder dezimal 0) bzw. umgekehrt dekrementiert 0 zu 255.

Addition

Auf einem Mega8 gibt es nur eine Möglichkeit, um eine Addition durchzuführen: Die beiden zu addierenden Zahlen müssen in zwei Registern stehen.

AVR-Befehle

 
     add  r16, r17      ; Addition der Register r16 und r17. Das Ergebnis wird
                        ; im Register r16 abgelegt
     adc  r16, r17      ; Addition der Register r16 und r17, wobei das Carry-Bit
                        ; noch zusätzlich mit addiert wird.

Bei der Addition zweier Register wird ein möglicher Überlauf in allen Fällen im Carry Bit abgelegt. Daraus erklärt sich dann auch das Vorhandensein eines Additionsbefehls, der das Carry-Bit noch zusätzlich mitaddiert: Man benötigt ihn zum Aufbau einer Addition die mehr als 8 Bit umfasst. Die niederwertigsten Bytes werden mit einem add addiert und alle weiteren höherwertigen Bytes werden, vom Niederwertigsten zum Höchstwertigsten, mittels adc addiert. Dadurch werden eventuelle Überträge automatisch berücksichtigt.

Subtraktion

Subtraktionen können auf einem AVR in zwei unterschiedlichen Arten ausgeführt werden. Entweder es werden zwei Register voneinander subtrahiert oder es wird von einem Register eine konstante Zahl abgezogen. Beide Varianten gibt es wiederum in den Ausführungen mit und ohne Berücksichtigung des Carry Flags

AVR-Befehle

 
     sub  r16, r17      ; Subtraktion des Registers r17 von r16. Das Ergebnis wird
                        ; im Register r16 abgelegt
     sbc  r16, r17      ; Subtraktion des Registers r17 von r16, wobei das Carry-Bit
                        ; noch zusätzlich mit subtrahiert wird. Das Ergebnis wird
                        ; im Register r16 abgelegt
     subi r16, zahl     ; Die Zahl (als Konstante) wird vom Register r16 subtrahiert.
                        ; Das Ergebnis wird im Register r16 abgelegt
     sbci r16, zahl     ; Subtraktion einer konstanten Zahl vom Register r16, wobei
                        ; zusätzlich noch das Carry-Bit mit subtrahiert wird.
                        ; Das Ergebnis wird im Register r16 abgelegt.

Multiplikation

Multiplikation kann auf einem AVR je nach konkretem Typ auf zwei unterschiedliche Arten ausgeführt werden. Während die größeren ATMega Prozessoren über einen Hardwaremultiplizierer verfügen, ist dieser bei den kleineren Tiny Prozessoren nicht vorhanden. Hier muß die Multiplikation quasi zu Fuß durch entsprechende Addition von Teilresultaten erfolgen.

Hardwaremultiplikation

Vorzeichenbehaftete und vorzeichenlose Zahlen werden unterschiedlich multipliziert. Denn im Falle eines Vorzeichens darf ein gesetztes 7. Bit natürlich nicht in die eigentliche Berechnung mit einbezogen werden. Statt dessen steuert dieses Bit (eigentlich die beiden MSB der beiden beteiligten Zahlen) das Vorzeichen des Ergebnisses. Die Hardwaremultiplikation ist auch dahingehend eingeschränkt, dass das Ergebnis einer Multiplikation immer in den Registerpärchen r0 und r1 zu finden ist. Dabei steht das LowByte (also die unteren 8 Bit) des Ergebnisses in r0 und das HighByte in r1.

AVR-Befehl

 
    mul   r16, r17      ; multipliziert r16 mit r17. Beide Registerinhalte werden
                        ; als vorzeichenlose Zahlen aufgefasst.
                        ; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
                        ; zu finden.

    muls  r16, r17      ; multipliziert r16 mit r17. Beide Registerinhalte werden
                        ; als vorzeichenbehaftete Zahlen aufgefasst.
                        ; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
                        ; zu finden und stellt ebenfalls eine vorzeichenbehaftete
                        ; Zahl dar.

    mulsu r16, r17      ; multipliziert r16 mit r17, wobei r16 als vorzeichenbehaftete
                        ; Zahl aufgefasst wird und r17 als vorzeichenlose Zahl.
                        ; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
                        ; zu finden und stellt eine vorzeichenbehaftete Zahl dar.

Multiplikation in Software

Multiplikation in Software ist nicht weiter schwierig. Man erinnere sich daran, wie Multiplikationen in der Grundschule gelehrt wurden: Zunächst stand da das kleine Einmal-Eins, welches auswendig gelernt wurde. Mit diesen Kenntnissen konnten dann auch größere Multiplikationen angegangen werden, indem der Multiplikand mit jeweils einer Stelle des Multiplikators multipliziert wurde und die Zwischenergebnisse, geeignet verschoben, addiert wurden. Die Verschiebung um eine Stelle entspricht dabei einer Multiplikation mit 10.

Beispiel: Zu multiplizieren sei 3456 * 7812

      3456     * 7812
      ---------------
     24192     <-+|||
 +    27648    <--+||
 +      3456   <---+|
 +       6912  <----+
     --------
     26998272

Im Binärsystem funktioniert Multiplikation völlig analog. Nur ist hier das kleine Einmaleins sehr viel einfacher! Es gibt nur 4 Multiplikationen (anstatt 100 im Dezimalsystem):

   0 * 0   = 0
   0 * 1   = 0
   1 * 0   = 0
   1 * 1   = 1

Es gibt lediglich einen kleinen Unterschied gegenüber dem Dezimalsystem: Anstatt zunächst alle Zwischenergebnisse aufzulisten und erst danach die Summe zu bestimmen, werden wir ein neues Zwischenergebnis gleich in die Summe einrechnen. Dies deshalb, da Additionen von mehreren Zahlen im Binärsystem im Kopf sehr leicht zu Flüchtigkeitsfehlern führen (durch die vielen 0-en und 1-en). Weiters wird eine einfache Tatsache benutzt: 1 mal eine Zahl ergibt wieder die Zahl, während 0 mal eine Zahl immer 0 ergibt. Dadurch braucht man im Grunde bei einer Multiplikation überhaupt nicht zu multiplizieren, sondern eigentlich nur die Entscheidung treffen: Muss die Zahl geeignet verschoben addiert werden oder nicht?

   0b00100011         * 0b10001001
   --------------------------------
     00100011          <--+|||||||
+     00000000         <---+||||||
     ---------              ||||||
     001000110              ||||||
+      00000000        <----+|||||
     ----------              |||||
     0010001100              |||||
+       00000000       <-----+||||
     -----------              ||||
     00100011000              ||||
+        00100011      <------+|||
     ------------              |||
     001001010011              |||
+         00000000     <-------+||
     -------------              ||
     0010010100110              ||
+          00000000    <--------+|
     --------------              |
     00100101001100              |
+           00100011   <---------+
     ---------------
     001001010111011

Man sieht auch, wie bei der Multiplikation zweier 8 Bit Zahlen sehr schnell ein 16 Bit Ergebnis entsteht. Dies ist auch der Grund, warum die Hardwaremultiplikation immer 2 Register zur Aufnahme des Ergebnisses benötigt.

Ein Assembler Code, der diese Strategie im Wesentlichen verwirklicht, sieht z. B. so aus. Dieser Code wurde nicht auf optimale Laufzeit getrimmt, sondern es soll im Wesentlichen eine 1:1 Umsetzung des oben gezeigten Schemas sein. Einige der verwendeten Befehle wurden im Rahmen dieses Tutorials an dieser Stelle noch nicht besprochen. Speziell die Schiebe- (lsl) und Rotier- (rol) Befehle sollten in der AVR Befehlsübersicht genau studiert werden, um ihr Zusammenspiel mit dem Carry Flag zu verstehen. Nur soviel als Hinweis: Das Carry Flag dient in der lsl / rol Sequenz als eine Art Zwischenspeicher, um das höherwertigste Bit aus dem Register r0 beim Verschieben in das Register r1 verschieben zu können. Der lsl verschiebt alle Bits des Registers um 1 Stelle nach links, wobei das vorhergehende MSB ins Carry Bit wandert und rechts ein 0-Bit nachrückt. Der rol verschiebt ebenfalls alle Stellen eines Registers um 1 Stelle nach links. Diesmal wird aber rechts nicht mit einem 0-Bit aufgefüllt, sondern an dieser Stelle wird der momentane Inhalt des Carry Bits eingesetzt.

 
    ldi  r16, 0b00100011  ; Multiplikator
    ldi  r17, 0b10001001  ; Multiplikand
                          ; Berechne r16 * r17

    ldi  r18, 8          ; 8 mal verschieben und gegebenenfalls addieren
    clr  r19             ; 0 wird für die 16 Bit Addition benötigt
    clr  r0              ; Ergebnis Low Byte auf 0 setzen
    clr  r1              ; Ergebnis High Byte auf 0 setzen

mult:
    lsl  r0              ; r1:r0 einmal nach links verschieben
    rol  r1
    lsl  r17             ; Das MSB von r17 ins Carry schieben
    brcc noadd           ; Ist dieses MSB (jetzt im Carry) eine 1?
    add  r0,r16          ; Wenn ja, dann r16 zum Ergebnis addieren
    adc  r1,r19

noadd:
    dec  r18             ; Wurden alle 8 Bit von r17 abgearbeitet?
    brne mult            ; Wenn nicht, dann ein erneuter Verschiebe/Addier Zyklus

                         ; r0 enthält an dieser Stelle den Wert 0b10111011
                         ; r1 enthält 0b00010010
                         ; Gemeinsam bilden r1 und r0 also die Zahl
                         ; 0b0001001010111011

Division

Anders als bei der Multiplikation, gibt es auch auf einem ATMega-Prozessor keine hardwaremässige Divisionseinheit. Divisionen müssen also in jedem Fall mit einer speziellen Routine, die im wesentlichen auf Subtraktionen beruht, erledigt werden.

Division in Software

Um die Vorgangsweise bei der binären Division zu verstehen, wollen wir wieder zunächst anhand der gewohnten dezimalen Division untersuchen wie sowas abläuft.

Angenommen es soll dividiert werden: 938 / 4 ( 938 ist der Dividend, 4 ist der Divisor)

Wie haben Sie es in der Grundschule gelernt? Wahrscheinlich so wie der Autor auch:

   938 : 4 = 234
  ---
  -8
  ----
   1
   13
  -12
   ---
    1
    18
   -16
    --
     2 Rest

Der Vorgang war: Man nimmt die erste Stelle des Dividenden (9) und ruft seine gespeicherte Einmaleins Tabelle ab, um festzustellen, wie oft der Divisor in dieser Stelle enthalten ist. In diesem konkreten Fall ist die erste Stelle 9 und der Divisor 4. 4 ist in 9 zweimal enthalten. Also ist 2 die erste Ziffer des Ergebnisses. 2 mal 4 ergibt aber 8 und diese 8 werden von den 9 abgezogen, übrig bleibt 1. Aus dem Dividenden wird die nächste Ziffer (3) heruntergezogen und man erhält mit der 1 aus dem vorhergehenden Schritt 13. Wieder dasselbe Spiel: Wie oft ist 4 in 13 enthalten? 3 mal (3 ist die nächste Ziffer des Ergebnisses) und 3 * 4 ergibt 12. Diese 12 von den 13 abgezogen macht 1. Zu dieser 1 gesellt sich wieder die nächste Ziffer des Dividenden, 8, um so 18 zu bilden. Wie oft ist 4 in 18 enthalten? 4 mal (4 ist die nächste Ziffer des Ergebnisses), denn 4 mal 4 macht 16, und das von den 18 abgezogen ergibt 2. Da es keine nächste Ziffer im Dividenden mehr gibt, lautet also das Resultat: 938 : 4 ergibt 234 und es bleiben 2 Rest.

Die binäre Division funktioniert dazu völlig analog. Es gibt nur einen kleinen Unterschied, der einem sogar das Leben leichter macht. Es geht um den Schritt: Wie oft ist x in y enthalten? Dieser Schritt ist in der binären Division besonders einfach, da das Ergebnis dieser Fragestellung nur 0 oder 1 sein kann. Das bedeutet aber auch: Entweder ist der Divisior in der zu untersuchenden Zahl enthalten, oder er ist es nicht. Das kann aber ganz leicht entschieden werden: Ist die Zahl größer oder gleich dem Divisior, dann ist der Divisor enthalten und zum Ergebnis kann eine 1 hinzugefügt werden. Ist die Zahl kleiner als der Divisior, dann ist der Divisior nicht enthalten und die nächste Ziffer des Ergebnisses ist eine 0.

Beispiel: Es soll die Division 0b01101100 : 0b00001001 ausgeführt werden.

Es wird wieder mit der ersten Stelle begonnen und die oben ausgeführte Vorschrift angewandt.

  0b01101101 : 0b00001001 = 0b00001100
                              ^^^^^^^^
                              ||||||||
    0                ---------+|||||||   1001 ist in 0 0-mal enthalten
   -0                          |||||||
   --                          |||||||
    0                          |||||||
    01               ----------+||||||   1001 ist in 1 0-mal enthalten
   - 0                          ||||||
    --                          ||||||
    01                          ||||||
    011              -----------+|||||   1001 ist in 11 0-mal enthalten
   -  0                          |||||
    ---                          |||||
    011                          |||||
    0110             ------------+||||   1001 ist in 110 0-mal enthalten
   -   0                          ||||
    ----                          ||||
    0110                          ||||
    01101            -------------+|||   1001 ist in 1101 1-mal enthalten
   - 1001                          |||
    -----                          |||
     0100                          |||
     01001           --------------+||   1001 ist in 1001 1-mal enthalten
    - 1001                          ||
     -----                          ||
     00000                          ||
     000000          ---------------+|   1001 ist in 0 0-mal enthalten
   -      0                          |
     ------                          |
     0000001         ----------------+   1001 ist in 1 0-mal enthalten
    -      0
     -------
           1 Rest

Die Division liefert also das Ergebnis 0b00001100, wobei ein Rest von 1 bleibt. Der Dividend 0b01101101 entspricht der Dezimalzahl 109, der Divisor 0b00001001 der Dezimalzahl 9. Und wie man sich mit einem Taschenrechner leicht überzeugen kann, ergibt die Division von 109 durch 9 einen Wert von 12, wobei 1 Rest bleibt. Die Binärzahl für 12 lautet 0b00001100, das Ergebnis stimmt also.

 
    ldi  r16, 109   ; Dividend
    ldi  r17,   9   ; Divisor

                    ; Division r16 : r17

    ldi  r18,   8   ; 8 Bit Division
    clr  r19        ; Register für die Zwischenergebnisse / Rest
    clr  r20        ; Ergebnis

divloop:
    lsl  r16        ; Zwischenergebnis mal 2 nehmen und das
    rol  r19        ; nächste Bit des Dividenden anhängen

    lsl  r20        ; das Ergebnis auf jeden Fall mal 2 nehmen,
                    ; das hängt effektiv eine 0 an das Ergebnis an.
                    ; Sollte das nächste Ergebnis-Bit 1 sein, dann wird
                    ; diese 0 in Folge durch eine 1 ausgetauscht

    cp   r19, r17   ; ist der Divisor größer?
    brlo div_zero   ; wenn nein, dann bleibt die 0
    sbr  r20, 1     ; wenn ja, dann jetzt die 0 durch eine 1 austauschen ...
    sub  r19, r17   ; ... und den Divisor abziehen

div_zero:
    dec  r18        ; das Ganze 8 mal wiederholen
    brne divloop

                    ; in r20 steht das Ergebnis der Division
                    ; in r19 steht der bei der Division entstehende Rest

Arithmetik mit mehr als 8 Bit

Es gibt eine Sammlung von Algorithmen zur AVR-Arithmetik mit mehr als 8 Bit, deren Grundprinzipien im wesentlichen identisch zu den in diesem Teil ausgeführten Prinzipien sind.