Home ==> AVR-DE ==> Binärzahlen
Binär

Einführung in Binärzahlen und Binärmathematik


Überblick

  1. Einfache Dezimal-, Binär- und Hexadezimalzahlen
  2. Größere Zahlen
  3. Gepackte Zahlen
  4. Vorzeichenbehaftete Ganzzahlen
  5. Addieren
  6. Subtrahieren
  7. Multiplizieren/Dividieren
  8. Binäres UND, ODER und EXOR

1 Einfache Dezimal-, Binär- und Hexadezimalzahlen

Einfache Zahlen in der Dezimalwelt reichen von 0 bis 9. Für größere Zahlen wird nach links hin angebaut (warum nach links statt nach rechts bleibt ein Geheimnis). Die nächstlinke Ziffer zählt genau zehn Mal mehr als die Ziffer dahinter. Werden weitere Ziffern nach links hin dazugebaut, sind dies Hunderter, Tausender und Zehntausender. Mit der Methode Linksanbau lassen sich so beliebig groäße Zahlen basteln.

In der Binärwelt gehen schon bei 1 die Ziffern aus und es muss schon nach 1 nach links angebaut werden. Die Stellen sind nach links hin dann Zweier, Vierer, Achter, 16-er, etc.. Also immer zwei Mal mehr (statt 10 Mal mehr wie in der Dezimalwelt).

Binär 10101010 So kommt man von einem Binärwert von 1010.1010 zum entsprechenden Dezimalwert: ist eine Binärziffer 0, wird die entsprechende Dezimalwertigkeit der Stelle nicht addiert. Ist sie 1, wird die entsprechende Wertigkeit addiert.

Die 1010.1010 ist eine besondere Zahl, weil sie beim seriellen Senden, also Bit für Bit nacheinander, das größte Geklapper auf der Signalleitung macht.

Binär 01010101 Gleich großes Geklapper macht nur die dezimale 85. Die einzelnen Bits der 85 sind die gleichen wie bei der 170, nur sind alle invertiert (umgedreht, aus Null mach Eins und umgekehrt). Und noch etwas kann man an der 85 erkennen: sie entsteht durch einmaliges Rechts-Schieben aus der 170, wenn man von links eine Null hineinschiebt und die rechts herausfallende Null ignoriert. Ganz ähnlich wie in der Dezimalwert: einmal Rechtsschieben von 170 ergibt 17, also dem Teilen durch 10. Beim Binären macht das Rechtsschieben nur die Hälfte.

Ganz ähnlich auch das Linksschieben. In der Dezimalwelt wird beim Linksschieben von 170 schon 1700, beim binären Linksschieben wird aus 1010.1010 nur 1.0101.0100, also zwei mal mehr. Damit haben wir auch schon das binäre Malnehmen und Teilen gelernt, aber nur das mit ganzen Zweierpotenzen.


Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftet Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR

2 Größere Zahlen

Die AVR haben als kleinste Speichereinheit das Bit, in das nur eine Eins oder eine Null hineinpassen. Damit ässt sich kaum grössere Rechnerei veranstalten, schon beim Addieren von zwei Einsen passt das Ergebnis nicht mehr in das eine Bit.

Die nächstgrößere Einheit ist das Byte. Davon haben die AVRs reichlich, nämlich z.B. 32 8-Bit-Register (PICs haben davon beispielsweise nur ein Einziges). Darin passen immerhin ganze 256 einzelne Bits, jeweils in Achter-Päckchen verpackt. Da das Byte die wichtigste Grundeinheit in den 8-Bit-AVRs ist, haben wir weiter oben zwei 8-Bit-Zahlen gewählt.

Weil das Schreiben schon von nur 8 Bits mühsam ist, gibt es für das Schreiben von Binärzahlen eine großartige Vereinfachung, die Hexadezimalzahlen. Dazu werden jeweils vier Binärstellen zusammengefasst und mit einer Ziffer dargestellt. Weil vier Bits maximal 1111 groß werden können, werden ab 1010 die Ziffern A bis F verwendet. Die obigen beiden Zahlen heißen daher 0xAA bzw. 0x55. Die 0x vor der Zahl sagt, dass jetzt eine Zahl in Hexadezimalformat folgt. In acht Bit passt maximal 0xFF oder 0b11111111 oder dezimal 128+64+32+16+8+4+1=255 hinein.

Sind größere Zahlen zu handhaben, müssen mehr als 8 Bit her. Da wir dafür im AVR reichlich haben, packen wir die größere Zahl halt in zwei (16 Bit), drei (24 Bit), vier (32 Bit) oder fünf Register (40 Bit). Das ginge dann bis eine Billiarde und dürfte für fast alle Zwecke ausreichend sein. In welche von den 32 Registern wir die fünf Bytes packen und in welcher Reihenfolge, ist beim Assembler-Programmieren meistens ganz egal (die Hochsprachler werden da ziemlich rigid von ihren Compilern bevormundet). Um die Übersicht zu behalten, kann man z.B. für eine 32-Bit-Zahl schreiben:

.equ Zahl = 4294000000 ; Ca. vier Milliarden
	ldi R16,Byte1(Zahl) ; die untersten 8 Bit
	ldi R17,Byte2(Zahl) ; Bits 9 bis 16
	ldi R18,Byte3(Zahl) ; Bits 17 bis 24
	ldi R19,Byte4(Zahl) ; Bits 25 bis 32

Die Zahlen liegen jetzt schön in einer Reihe, vom niedrigstwertigen bis zum höchstwertigen, wir könnten sie aber auch beliebig mischen. Ist nur für das menschliche Gedächtnis eine Erleichterung, dem Herrn Professor ist das alles wurscht-egal. Er macht, was ihm gesagt wird damit.

Damit lassen sich alle Rechenaufgaben bewältigen.

Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftet Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR

3 Gepackte Zahlen

Binär- oder Hexadezimalzahlen haben eine optimale Packungsdichte, kein Speicherbit ist überflüssig. Sie sind am Engsten gepackt und rechnen auch am schnellsten. In dieser optimalen Welt hat man aber auch weniger gute Konstruktionen erdacht. Wer also gerne Rechenzeit und Speicher verschwenden will, wählt eine der folgenden Möglichkeiten.

Die naheliegendste Möglichkeit ist das Speichern einer dezimalen ASCII-Ziffer in einem Byte. Das kommt dann vor, wenn Binärzahlen in darstellbare Zeichen auf einer LCD umzuwandeln sind. Die Dezimalziffern 0 bis 9 sind in ASCII als Zeichen mit den Nummern 48 bis 57 vertreten, in Hex 0x30 bis 0x39. Jede Ziffer braucht ein Byte, die vier Milliarden von oben würden also zehn Byte benötigen (in Binärform nur vier).

Ganz ähnlich sind die Verhältnisse, wenn statt des ASCII-Codes nur die Dezimalziffer zwischen 0 und 9 in einem Byte gespeichert wird. Das Konstrukt heißt Binary Coded Digit (BCD). Vier Bits in jedem Register sind dann überschüssig und immer Null.

Das macht man sich bei gepackten BCD zu nutze, bei dem eine Dezimalziffer in den unteren vier Bits eines Registers, die zweite in den oberen vier Bits untergebracht wird.

Packed BCD Das reduziert den Speicherbedarf für die obige Zahl von zehn auf immerhin nur fünf, ist also nur geringfügig speichergefrässiger als binär.

Die Anwendungen für BCD und gepackte BCD sind rar, Vorteile haben sie keine und das Rechnen damit ist auch nicht einfacher als das binäre Rechnen. Außer dass man wissen sollte, dass es das gibt und dass das geht, ist damit kein schönerer Blumentopf zu gewinnen.


Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftet Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR

4 Vorzeichenbehaftete Ganzzahlen

Manchmal hat man es mit positiven UND negativen Ganzzahlen zu tun. Für die Fälle, in denen man das nicht vermeiden kann, gibt es das Speichern und Rechnen mit negativen Zahlen. Den Bytes sieht man nicht an, ob sie vorzeichenbehaftet sind oder nicht, das muss sich der Programmierer schon selbst merken.

Bei negativen binären Zahlen dient das oberste Bit der Zahl (bei mehrbytigen Zahlen nur das Alleroberste) als Vorzeichenbit. Ist es Null, dann ist die Zahl in den unetern 6 Bits positiv. Ist es Eins, dann ist die Zahl negativ und ist von Null abgezogen. -1 wird auf diese Weise zu 0xFF, -2 zu 0xFE, etc.. Der Wertebereich, der in ein Byte passt, reicht von 0 bis 127 für positive Zahlen und von -1 bis -128 für negative. Die etwas andere Speicherung negativer Zahlen vereinfacht das Addieren positiver und negativer Zahen, wie weiter unten zu sehen ist.

Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftet Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR

5 Addieren

Addieren vin Binärzahlen

Das binäre Addieren geht ganz einfach. Links das dezimale Addieren, rechts das binäre.
DEZIMAL    158 BINÄR      10101010
          + 48           +  110110
         -----          ----------
Übertrag   110 Übertrag   01111100
Resultat = 206 Resultat = 11100000
         =====          ==========
Wird beim dezimalen Addieren die zehn erreicht, erfolgt ein Übertrag in die nächsthöhere Stelle. 8 plus 8 ergibt 16, also wird eine 1 in die nächste Stelle addiert. 5 plus 4 plus 1 (Übertrag) ergibt 10, also wieder ein Übertrag.

Beim binären Addieren gibt es den Übertrag schon dann, wenn 1 und 1 zu addieren sind (das gibt dann 10). Ist noch ein Übertragsbit von der nächst-niedrigen Stelle zu addieren, dann kommt 11 heraus und die vordere 1 wird in die nächste Stelle übertragen.

5.1 Addieren von Bytes

Da der AVR ein 8-Bit-Controller ist, brauchen wir uns um diese einzelnen Addierereien und Überträge nicht weiter kümmern, das macht die eingebaute CPU für uns. Mit den Instruktionen

	LDI R16,0b10101010 ; die erste Zahl in das Register R16
	LDI R17,0b110110 ; die zweite Zahl in das Register R17
	ADD R16,R17 ; addiere die zweite zur ersten und schreibe Ergebnis in R16

0b steht für eine Binärzahl. Mit ADD haben wir die beiden Zahlen schon vollständig addiert, die CPU hat sich auch um eventuelle Überträge gekümmert, und in R16 steht unser Resultat. Wenn jetzt aber das Ergebnis größer als 255 geworden wäre, also beim Addieren des achten Bits ein Übertrag erfolgte (nicht in unserem Fall), dann muss diese wichtige Information irgendwo anders hin. Dafür hat die CPU das Flaggenregister ("Status register" oder "SREG"). Und darin speziell das Bit "Carry" oder kurz "C". Wo das genau im SREG liegt, braucht uns nicht weiter interessieren, das weiß die CPU schon selbst ganz genau.

Mit dem C kann man nach der ADD-Instruktion was anfangen, also zum Beispiel eine Warnung in Form einer roten LED ausgeben. Das täte man dann in Assembler so programmieren.

	LDI R16,0b10101010 ; die erste Zahl in das Register R16
	LDI R17,0b110110 ; die zweite Zahl in das Register R17
	ADD R16,R17 ; addiere die zweite zur ersten und schreibe Ergebnis in R16
	BRCS RoteLedAn ; Wenn carry-Flagge C gesetzt S springe (branch)
	SBI LedPort,RoteLed ; Setze das Bit der roten LED im LED-Port hoch
	RJMP SprungDanach ; Springe über die nächste Instruktion
RoteLedAn:
	CBI LedPort,RoteLed ; Setze das Bit der roten LED im LED-Port niedrig
SprungDanach:
	; Hierher kommt man wieder in beiden Fällen und es kann weitergehen

Hier dient die Übertragsflagge als Schalter zum Springen und als Verzweiger zum Ansteuern zweier unterschiedlicher Programmteile. Noch viel öfter wird die Carry-Flagge aber gebraucht, wenn man 2, 3 oder 4 Byte lange Binärzahlen addieren will, weil ja bei jedem Addieren eines niederen Bytes so ein Übertrag auftreten kann und der dann noch zu dem höheren Byte dazu gezählt werden muss.

5.2 Addieren von beliebig großen Zahlen

Aber keine Angst dass jetzt eine Carry-Springorgie kommt, das kommt so häufig vor, dass es die CPU schon von sich aus kann.

Nehmen wir an, wir hätten eine zwei Byte lange Zahl in den beiden Registern R16 und R17 (geschrieben als R17:R16, R17 enthält die oberen 8 Bits der 16-Bit-Zahl) und wollten eine weitere zwei Byte große Zahl in R19:R18 dazu addieren. Die untersten 8 Bit gehen wieder mit "ADD R16,R18" addieren. Zu den oberen 8 Bits muss jetzt aber noch das Carry dazu addiert werden, das entweder 0 oder 1 sein kann. Dafür kennt die CPU die Instruktion "ADC R17,R19". ADC addiert die beiden Register und das Carry-Bit in einem Rutsch. Nix mit Springen und Verzweigen, geht alles viel eleganter. Das funktioniert mit beliebig langen Zahlen, hier mal das Addieren einer Vier-Byte-Zahl in R19:R18:R17:R16 mit einer Zwei-Byte-Zahl in R21:R20:

	ADD R16,R20 ; Unterste Bytes addieren, Ergebnis in R16
	ADC R17,R21 ; Nächsthöres Byte addieren, Ergebnis in R17
	LDI R20,0 ; Eine Null in R20 schreiben
	ADC R18,R20 ; Addiere Null und Carry, Ergebnis in R18
	ADC R19,R20 ; Addiere Null und Carry, Ergebnis in R19

Das war schon die langwierige Prozedur des Addierens einer 32-Bit-Zahl mit einer 16-Bit-Zahl: gerade mal fünf lumpige Instruktionen lang. Jedenfalls kein vernünftiger Grund, auf eine 16- oder 32-Bit-Controllerfamilie umzusteigen, um mal lange Zahlen zu verarbeiten. Geht alles auch schon so.

5.3 Addieren von gepackten BCD-Zahlen

Jetzt machen wir das mit zwei gepackten BCD-Zahlen. Als Beispiel wählen wir die gepackten Zahlen 89 in R16 und 32 in R17. Das sieht dann so aus:
DEZIMAL:       89  BINÄR: 1000.1001
              +32         0011.0010
Übertrag      110       0.0000.0000
Resultat     =121         1011.1011
Das ist jetzt alles sehr enttäuschend, denn dabei ist jetzt gar kein Übertrag aufgetreten, wie er sollte. Dafür steht im unteren und im oberen Nibble eine für BCD illegale Zahl, nämlich 1011. Illegal deshalb, weil es mehr ist als 9. Dem kann man abhelfen, indem wir zum unteren und oberen Nibble jeweils sechs dazu zählen, also z.B. so:

	LDI R18,0x66 ; Gepacktes BCD mit 66
	ADD R16,R18 ; zum Ergebnis addieren

In der Binärformulierung von oben wird nun daraus:
BINÄR:     1011.1011
          +0110.0110
       = 1.0010.0001
PACKED = 1    2    1
Famos, Überlauf und die beiden gepackten BCD-Ziffern stimmen jetzt alle. Aber nur, weil wir das Beispiel so gewählt haben. Wenn nämlich beim Addieren von 6 zur unteren Ziffer kein Übertrag in die obere Ziffer erfolgt wäre, müssten wir die sechs nämlich wieder abziehen. Das signalisiert uns eine weitere Flagge im SREG, das Halbübertragsbit H. Ist es Null, wäre 6 wieder abzuziehen, damit die untere Ziffer stimmt.

Selbiges auch beim oberen Nibble: tritt beim Addieren von 0x66 kein Carry auf, wären 6 auch vom oberen Nibble wieder abzuziehen, damit die obere Ziffer wieder stimmt. Je nachdem müssen wir also nach dem Addieren von 0x66 Das gibt einen schönen Verhau an Entscheidungen. Übrigens kann schon bei der ersten Addition der beiden Zahlen das Carry gesetzt sein, wenn z.B. das gepackte 99 mit dem gepackten 99 addiert würde. Auch darauf wäre noch zu reagieren.

Nach all dem dürfte klar sein, dass die gepackte BCD-Mathematik keineswegs einfacher ist als das simple Addieren von Binärzahlen. Nur pure Informatiker haben an so was ihre Freude, der Rest der Menschheit dürfte nicht so arg begeistert sein. Wir vergessen also das H-Bit im SREG wieder und wenden uns Wichtigerem zu. Es muss aber unbedingt auch völlig unnützes Zeugs im Design einer CPU geben, damit dem Spieltrieb keine Grenzen gesetzt werden und weil das alle anderen CPUs auch so machen, so was wie Herdentrieb.

5.4 Addieren von vorzeichenbehafteten Zahlen

Nehmen wir mal an, unsere Register R16 und R17 wären vorzeichenbehaftete Ganzzahlen. Also z.B. +94 und, der Einfachheit halber, -1. Beim Addieren müsste dann 93 herauskommen. Mal schauen, ob das so stimmt.
DEZIMAL   +94  BINÄR  0101.1110  HEX   5E
        +  -1         1111.1111        FF
Resultat  +93       1.0101.1101       15D
Perfekt, stimmt fast alles. Das oberste Bit des Ergebnisses ist Null, die Zahl ist also positiv. Und korrekterweise 93. Nur das Übertragsbit ist verkehrt, weil eigentlich kein Übertrag erfolgt.

Nun addieren wir +94 und -94, was bekanntlich 0 ergeben müsste. -94 ist (256 - 94) = 162, also mit gesetztem Vorzeichenbit (>=128).
DEZIMAL   +94  BINÄR  0101.1110  HEX   5E
        + -94         1010.0010        A2
Resultat    0       1.0000.0000       100
Stimmt wieder auffällig genau, wenn nicht das überflüssige Carry wäre.

Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftete Ganzzahlen Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR

6 Subtrahieren

Beim Subtrahieren geht das alles wie beim Addieren, nur mit der Instruktion SUB (Subtrahieren zweier Register, Ergebnis in das erste Register).

Bei Zahlen mit mehr Bytes wird wieder SUB mit SBC kombiniert (SUB zusätzlich noch mit Subtrahieren des Carry-Bits). Auch hier signalisiert ein gesetztes Carry-Bit, dass beim Subtrahieren ein Überlauf (oder besser: Unterlauf?) erfolgt ist, der dann beim nächsthöheren Subtrahieren mit abgezogen werden muss.

7 Multiplizieren/Dividieren

7.1 Multiplizieren

Zum Multiplizieren nimmt man entweder den eingebauten 8-Bit-Multiplizierer (in den neueren ATmega verbaut) und werkelt damit ganz schön schnell oder man baut sich seine Multiplikationsroutine selber per Software (geht immer und ist gar nicht so kompliziert).

Hier nebeneinander die dezimale und die binäre Variante. Die unterscheiden sich gar nicht so arg voneinander, außer dass die Binärzahl viel länger ist und die Multiplikationsroutine mehr Schritte hat, aber dafür aber viel einfacher gestrickt ist.
DEZIMAL   9.748 * 143    BINÄR     10.0110.0001.0100 * 1000.1111
--------------------     ---------------------------------------
         29.244                    10.0110.0001.0100
       +389.920                  +100.1100.0010.1000
       +974.800                 +1001.1000.0101.0000
--------------------          +1.0011.0000.1010.0000
      =1.393.964             +00.0000.0000.0000.0000
====================        +000.0000.0000.0000.0000
                           +0000.0000.0000.0000.0000
                         +1.0011.0000.1010.0000.0000
                         ---------------------------------------
                         =1.0101.0100.0101.0010.1100
                         =======================================
Beim dezimalen Multiplizieren muss man die zu multiplizierende Zahl, mit der letzten Stelle beginnend, mit der Ziffer multiplizieren und zum Ergebnis addieren. Vor der Multiplikation mit jeder weiteren Ziffer wird die Zahl erst mal mit Zehn malgenommen. Zählt man alles zusammen, kommt das Ergebnis heraus.

Beim binären Malnehmen geht alles viel einfacher: Aus dem Malnehmen mit Zehn wird das Malnehmen mit 2 (wir ahnen schon: es ist Linksschieben angesagt). Und für jede Ziffer gibt es nur zwei Alternativen: ist sie Null wird nix dazugezählt, ist sie Eins, wird das Linksgeschobene dazu gezählt.

Das ist nun so einfach zu programmieren, dass man sich fast schämt, das hinzuschreiben:

	; Zahlen in R1:R0 und R3
	ldi R16,0x26 ; 0x2614 in R1:R0
	mov R1,R16
	ldi R16,0x14
	mov R0,R16
	clr R2 ; R2 wird zum Linksschieben gebraucht
	ldi R16,0x8F ; 0x8F in R3
	mov R3,R16
	; Ergebnis in R6:R5:R4 leeren
	clr R6
	clr R5
	clr R4
MultLoop:
	lsr R3 ; ein Bit herausschieben
	brcc MultOhne ; wenn Null, nicht addieren
	add R4,R0 ; Zahl addieren
	adc R5,R1 ; Zahl mit Uebertrag addieren
	adc R6,R2 ; Zahl mit Uebertrag addieren
MultOhne:
	lsl R0 ; Zahl links schieben, Null in niedrigstes Bit
	rol R1 ; Links schieben, Carry in niedrigstes Bit
	rol R2 ; Links schieben, Carry in niedrigstes Bit
	tst R3 ; schon fertig?
	brne MultLoop ; Nein, noch mal dasselbe
	; Ergebnis in R6:R5:R4 fertig

Multiplikation Das war es schon, ganze 19 Instruktionen für die Multiplikation einer 16-Bit-Zahl mit einer 8-Bit-Zahl. Und, wie das Studio nach der Simulation sagt, ganze 90 µs bei 1 MHz Takt. Dafür nun unbedingt auf einen ATmega wechseln, um den Hardware Multiplizierer anwerfen zu können, ist nun ziemlich unter unserer Würde.

Im Studio ist auch zu sehen, dass das Ergebnis in R6:R5:R4 mit dem oben erzielten (0x15452C) auffallend übereinstimmt.

Es sollte auch ein Leichtes sein, nun 8-Bit mal 8-Bit oder 24-Bit mal 24-Bit zu programmieren, wenn man das Prinzip erst mal kapiert hat. War doch gar nicht so schwer, oder? Und schon gar kein Grund, Assembler für hochkomplex zu erklären und stattdessen den C-Compiler anzuwerfen, nur um so einen einfachen Kram nicht lernen zu müssen.

7.2 Division

Jetzt wird es aber riesenkompliziert, weil Division ist höllisch schwer. Wieder an den beiden Zahlenarten aus dem Multiplikationsbeispiel, nur jetzt rückwärts.
DEZIMAL 1.393.964 : 143     BINÄR 0001.0101.0100.0101.0010.1100 : 1000.1111
        139 : 143 = 0        <==  0010.1010.1000.1010.0101.1000 Links geschoben
        1393: 143 = 9        Vgl  1000.1111 = 0 (kleiner!)
-143*9=-1.287.000            <==  0101.0101.0001.0100.1011.0000 Links geschoben
         =106.964            Vgl  1000.1111 = 0 (kleiner!)
	  1069 : 143 = 7     <==  1010.1010.0010.1001.0110.0000 Links geschoben
-143*7=  -100.100            Min -1000.1111 = 1 (abziehen!)
            6.864            Erg =0001.1011.0010.1001.0110.0000 abgezogen 
            686 : 143 = 4    <==  0011.0110.0101.0010.1100.0000 Links geschoben
-4*143=     5.720            Vgl  1000.1111 = 0 (kleiner!) 
            1.144 : 143 = 8  <==  0110.1100.1010.0101.1000.0000 Links geschoben
-8*143=    -1.144            Vgl  1000.1111 = 0 (kleiner!) 
                0            <==  1101.1001.0100.1011.0000.0000 Links geschoben
---------------------------  Min -1000.1111 = 1 (abziehen!) 
          = 9.748            Erg =0100.1010.0100.1011.0000.0000 abgezogen
                             <==  1001.0100.1001.0110.0000.0000 Links geschoben
                             Min -1000.1111 = 1 (abziehen!) 
                             Erg =0000.0101.1001.0110.0000.0000 abgezogen
                             <==  0000.1011.0010.1100.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  0001.0110.0101.1000.0000.0000 Links geschoben 
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  0010.1100.1011.0000.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  0101.1001.0110.0000.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  1011.0010.1100.0000.0000.0000 Links geschoben
                             Min -1000.1111 = 1 (abziehen!) 
                             Erg =0010.0011.1100.0000.0000.0000 abgezogen
                             <==  0100.0111.1000.0000.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  1000.1111.0000.0000.0000.0000 Links geschoben
                             Min -1000.1111 = 1 (abziehen!)
                             Erg =0000.0000.0000.0000.0000.0000 abgezogen
                             <==  0000.0000.0000.0000.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                             <==  0000.0000.0000.0000.0000.0000 Links geschoben
                             Vgl  1000.1111 = 0 (kleiner!)
                                 ----------------------------------------------
                                 =0010.0110.0001.0100
                                 ====================
Wie auch hier zu sehen, ist die Anzahl der Schritte bei der binären Version deutlich größer, dafür sind diese aber viel einfacher. Es gibt nur das Linksschieben (<==), das Vergleichen (Vgl) und, falls die oberen beiden Byte größer oder gleich dem Divisor sind, noch das Abziehen (Min). Das Vergleichsergebnis (0 wenn kleiner, 1 wenn größer oder gleich) wird noch, von rechts aus nach links, in das Ergebnis eingeschoben. Nachdem wir das 16 Mal so veranstaltet haben, ist unser Ergebnis fertig zum Abholen.

Um das in Programmcode zu übersetzen, hier noch mal die einzelnen Operationen. So geht das Linksschieben mit 32 Bits:

Linksschieben

Das geht mit LSL (Logical Shift Left) für das unterste Byte und mit ROL (ROtate Left) für die höheren Bytes, um die Überträge aus dem niedrigeren Byte, die in der Carry-Flagge herumliegen, in das neue Bit 0 hinein zu rollen. Der Vergleich geht so:

Vergleich

Es müssen nur die obersten zwei Bytes verglichen werden. Eigentlich würde es auch reichen, nur die acht Bits des niedrigen Registers beim Vergleich heranzuziehen. Es kann aber Fälle geben, bei denen eine Eins in das Register R3 hineingelangt (wenn der Divisor nahe 255 liegt). Also sicherheitshalber mit zwei Bytes. Das unterste Byte wird mit CP (ComPare) verglichen, das oberste Byte mit CPC (ComPare with Carry, um Überläufe aus dem unteren Byte-Vergleich auch noch zu berücksichtigen). Ist nach dem Vergleich die Carry-Flagge gesetzt, dann war der Divident kleiner als der Divisor. In das Ergebnis gelangt dann eine binäre Null. Ergab der Vergleich größer oder gleich, kommt eine Eins ins Ergebnis. In diesem Fall ist noch der Divisor zu subtrahieren:

Abziehen

Wieder werden nur die obersten zwei Byte subtrahiert, und wieder mit Carry beim obersten Byte. Zur Anwendung kommen daher die Instruktionen ADD (ADD) und ADC (ADd with Carry). Das Hineinschieben des Ergebnisbits in das Ergebnis geht von rechts nach links:

Linksrotieren

Hier kommt durchgängig die Instruktion ROL zum Einsatz, da ja das Carry das Ergebnisbit enthält und dieses in das unterste Byte des Ergebnisses eingeschoben werden muss.

Das ist schon die ganze Kunst des Dividierens. Ordentlich geplant lautet dann unser Flussdigramm folgendermaßen:

Flussdiagramm Division Alles beginnt damit, dass der Divisor und der Divident auf die gewünschten Werte zu setzen sind. Außerdem müssen die Ergebnisregister von enthaltenem Schrott entleert und der Zähler auf 16 gesetzt werden.

Die Divisionsschleife beginnt mit dem Linksschieben des Divisors. Dem folgt der Vergleich mit dem Dividenten. Ergibt der ein nicht gesetztes Carry-Bit, folgt noch das Abziehen. Beide Fälle enden mit dem Ergebnis in der Carry-Flagge.

Diese wird in das Ergebnis hineingerollt. Ein Bit ist damit fertig bearbeitet.

Um festzustellen, ob alle Bits behandelt sind, wird nun der Bitzähler um eins verringert und, falls noch Bits zu behandeln sind, einfach an den Anfang der Division verzweigt. Wenn nicht, ist alles fertig.

Interessant ist noch, wenn wir einfach die Anzahl an Divisionsschritten von 16 auf 24 setzen. Dann sind die untersten acht Bit des Ergebnisses eine binäre Fließkommazahl (Float) statt einer Ganzzahl (Integer). Aber das ist höhere Binärmathetik.

Auch noch ein interessanter Fall tritt ein, wenn wir statt einer Drei-Byte-Zahl eine Vier-Byte-Zahl (32 Bit) hineintun oder das dritte Byte größer ist als der Divisor. In diesen Fällen gelangen lauter Einsen in das Ergebnis. Kluge Programmierer fangen solche Fälle vorher ab.

Damit kann es jetzt an das Codieren gehen. Wichtig ist es dabei, den Überblick über die vielen Register zu behalten. Daher immer kommentieren, was wo gespeichert wird und was damit gemacht wird.

	; In R3:R2:R1:R0 kommt die zu dividierende Zahl
.equ Zahl1 = 1393964
	ldi R16,Byte1(Zahl1)
	mov R0,R16
	ldi R16,Byte2(Zahl1)
	mov R1,R16
	ldi R16,Byte3(Zahl1)
	mov R2,R16
	ldi R16,Byte4(Zahl1)
	mov R3,R16
	; R4 Divident
	; In R5:R4 kommt der Divident
.equ Zahl2 = 143
	ldi R16,Zahl2
	mov R4,R16
	clr R5
	; Anzahl Bits der Division in R16
	ldi R16,16
	; Ergebnis ist in R8:R7:R6, entleeren
	clr R8
	clr R7
	clr R6
DivLoop: ; Die Divisionsschleife
	lsl R0 ; Zu dividierende Zahl links schieben
	rol R1
	rol R2
	rol R3
	cp R2,R4 ; Vergleiche LSB
	cpc R3,R5 ; Vergleiche MSB, mit Carry
	brcs DivNull ; Ergebnis 0
	sub R2,R4 ; Abziehen des LSB
	sbc R3,R5 ; Abziehen des MSB, mit Carry
	sec ; Ergebnis ist 1, in Carry
	rjmp DivShift
DivNull:
	clc ; Ergebnis ist 0, in Carry
DivShift:
	rol R6 ; Carry in Ergebnis rollen
	rol R7
	rol R8
	dec R16 ; Noch Bits zu dividieren?
	brne DivLoop ; 16 mal wiederholen

Division Studio Das Studio meldet nach der Simulation eine Ausfürungsdauer von 268 µs bei 1 MHz Takt. Das ist zwar etwas länger als die Multiplikation, aber auch nicht gerade die Welt. Und das Ergebnis in R8:R7:R6 stimmt auch auffällig genau.

8 UND, ODER und EXOR

Die Binärmathematik kennt noch drei wichtige Operationen, die aber in der Dezimalwelt gar keine Rolle spielen und für die es auch keine dezimale Entsprechung gibt.

8.1 Binäres UND

Haben wir eine Binärzahl und möchten gerne die obersten vier Bits loswerden, dann kennt die CPU dafür die folgende Instruktion:

	ANDI R16,0x0F ; Binäres UND mit den untersten vier Bit

Was auch immer in den obersten vier Bits von Register R16 gestanden haben mag, hinterher sind sie alle Null. Denn nur die vier untersten Bits überleben: waren sie 0, dann bleiben sie Null, waren sie 1, dann bleiben sie eins.

Wofür das gut sein soll? Nun, wenn wir ein Byte mit 8 Bits auf dem Port A, B, C, oder D ausgegeben hatten und wir möchten nun die obersten vier Bits im Port alle auf Null setzen, könnten wir zwar vier Mal hintereinander CBI ausgeben. Aber mit ANDI geht das in einem Rutsch und gleichzeitig. Z.B. so:

	IN R16,Portausgang ; Lese den aktuellen Zustand am Portausgang
	ANDI R16,0x0F ; Loesche alle obersten Bits
	OUT Portausgang,R16 ; Und schreibe Nullen in die obersten Bits

Statt 0x0F können wir natürlich auch alle anderen Bitmuster UNDen und ausgeben.

Mit dem UNDen kann man aus gepackten BCD-Zahlen auch das unerwünschte Nibble ausblenden. Das wird auch gerne mit der Instruktion SWAP kombiniert, die das untere und obere Nibble vertauscht.

8.2 Binäres ODER

Das umgekehrte, nämlich das Setzen von Bits, geht mit ODER. Sollen jetzt die oberen vier Bits im Port auf Eins gesetzt werden, geht das so:

	IN R16,Portausgang ; Lese den aktuellen Zustand am Portausgang
	ORI R16,0xF0 ; Setze alle obersten Bits
	OUT Portausgang,R16 ; Und schreibe Einsen in die obersten Bits

Was auch immer in den obersten vier Bits stand, nach ORI R16,0xF0 sind alle vier Oberen zu Eins geworden.

Durch Kombination von UND und ODER lässt sich für einen Teil eines Bytes jedes gewünschte Bitmuster setzen.

8.3 Binäres EXOR

Die Instruktion EXOR heißt in AVR-Assembler EOR. Sie geht aber nicht mit einem konstanten Bitmuster sondern nur mit zwei Registern, also z.B. EOR R16,R17. Beim EOR werden alle Bits im ersten Register umgedreht, die im zweiten Register Eins sind. Mit

	IN R16,Portausgang ; Lese Bitmuster im Port
	LDI R17,0x55 ; Lade Umkehrmaske, 0101.0101
	EOR R16,R17 ; alle Bits umkehren, die in der Maske R17 Eins sind
	OUT Portausgang,R16 ; Und an Portausgang schreiben

Damit lässt sich beispielsweise die Polarität an den gewünschten Bitpositionen eines Ports gezielt umdrehen, während die mit Null maskierten in Ruhe gelassen werden.

9 Schlussfolgerungen

  1. Das alles ist so hochkomplex und kompliziert, dass man damit besser keine Lernunwilligen quälen sollte.
  2. Wer Addition, Subtraktion, Multiplikation und Division schon in der Schule nicht verstanden hat, sollte sich doch mal die binäre Variante ansehen. Die ist nämlich viel einfacher zu verstehen und auszuführen. Wer das mal verstanden hat, der versteht danach auch die dezimale Variante.
  3. Wer sich von seinem Compiler gequält fühlt, weil der sich weigert, 48-Bit-Zahlen zu akzeptieren, sollte dringend zu Assembler wechseln. Hier kann er die neue Freiheit voll und ganz ausleben, kann sogar 56- und 64-Bit-Zahlen handlen und ist seine ganzen verdammten Compiler-Ketten mit ein paar lumpigen Zeilen Quellcode los.


Einfache Zahlen Größere Zahlen Gepackte Zahlen Vorzeichenbehaftet Addieren Subtrahieren Multipliz./Divid. UND/ODER/EXOR


©2017 by http://www.avr-asm-tutorial.net