AVR-Tutorial: Arithmetik8

2008-11-23T14:58:36Z

89.49.34.151: /* Carry */

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 lediglich auf 8 Bit Arithmetik eingegangen, um zunächst mal die Grundlagen des Rechnens mit einem µC zu zeigen. Die Erweiterung von 8 Bit auf 16 Bit Arithmetik ist in einigen Fällen trivial (Addition + Subtraktion), kann sich aber bei Multiplikation und Division schon in einem beträchtlichem Codeumfang 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 doch 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 sog. '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 )

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

= 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.

= spezielle Statusflags =

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 zeigt an ob bei einer Berechnung ein Über- oder Unterlauf erfolgt ist.

Wie das?

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

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

Das Ergebnis der Addition umfasst 9 Bit. Da aber die Register nur 8 Bit fassen können, würde das bedeuten, dass das MSB (das 9. Bit) verlorengeht. In diesem Fall sagt man: Die Addition ist übergelaufen. Damit man darauf reagieren kann, wird dieses 9. Bit allerdings in das Carry Flag übertragen und es gibt auch spezielle Befehle, die dieses Carry Flag in ihren Berechnungen berücksichtigen können.

= 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==
<avrasm>
inc r16
</avrasm>

bzw.

<avrasm>
dec r16
</avrasm>

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 ==
<avrasm>
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.
</avrasm>

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 wiederrum in den Ausführungen mit und ohne Berücksichtigung des Carry Flags

==AVR Befehle==

<avrasm>
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.
</avrasm>

= 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 ===
<avrasm>
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.
</avrasm>

== 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.

<avrasm>
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
</avrasm>

= 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: 92 / 5 ( 92 ist der Dividend, 5 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.

<avrasm>
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
</avrasm>

= Arithmetik mit mehr als 8 Bit =

Eine Sammlung von Algorithmen zur Arithmetik mit mehr als 8 Bit findet sich [[AVR_Arithmetik | hier]]. Die Grundprinzipien sind im wesentlichen identisch zu den in diesem Teil detailliert ausgeführten Prinzipien.

{{Navigation_zurückhochvor|
zurücktext=Logik|
zurücklink=AVR-Tutorial: Logik|
hochtext=Inhaltsverzeichnis|
hochlink=AVR-Tutorial|
vortext=Stack|
vorlink=AVR-Tutorial: Stack}}

[[Category:AVR]][[Category:AVR-Tutorial]]

Mikrocontroller.net - Benutzerbeiträge [de]

AVR-Tutorial: Arithmetik8