JASm Coding – Beispielprogramme 2 (Logik, ggT, Division und bitweises Schieben)

Bitweise Operationen

Shift Left, Shift Right

Diese bitweisen Operationen sind leicht abzubilden, da es sich bei einem Shift um eine Stelle effektiv um eine Multiplikation mit 2 (shift left) oder Division durch 2 (shift right) handelt. Shift left (die Multiplikation) lässt sich dabei seht leicht durch eine Addition umsetzen, wie das folgende Beispiel zeigt.

a:              12              # Eingangswert, der mit einem Shift left behandelt werden soll
tmp:            0               # Hilfsvariable
                SUB @tmp @a     # tmp = -a
                SUB @tmp @a     # tmp -= a = -2a
                SUB @a @a       # a = 0
                SUB @a @tmp     # a = -tmp = 2a

Ganz so einfach ist dies mit einem Shift Right nicht zu implementieren, da vor allem die Divison durch 2 viele Rechenschritte benötigt. Den Beispielcode erspare ich mir dementsprechend an dieser Stelle.

AND, OR und XOR

Etwas anspruchsvoller wird es bei der AND, OR oder XOR Operation zweier Werte. Hierzu sind die einzelnen Bits eines Zahlenwerts miteinander zu vergleichen. Eine Operation, die eine Schleife und das oben beschriebene Shiften nach rechts erfordert, wobei der sich jeweils ergebende Rest den Wert des zuvor an der rechtesten Stelle befindlichen Bits ergibt.

6 = 1102

Nach einem shift right (Division durch 2) ergibt sich

3 = 112 Rest 0

Ein weiterer shift right des ganzzahligen Resultats resultiert in

1 = 12 Rest 1

Somit sind in einer Schleife die beiden gegebenen Eingangswerte so lange mit einem shift right zu belegen, bis beide Werte jeweils null ergeben. Die nach rechts rausfallenden Bits werden dann mit den gewünschten Verknüpfungen versehen. Hierbei gilt mit a und b als Bit jeweils 1 oder 0:

  • a AND b = (a * b == 1), bzw. (a + b == 2)
  • a OR b = (a + b > 0)
  • a XOR b = (a + b == 1)

Der nachfolgende JASm Code zeigt, wie aus den Eingangsgrößen a und b sowohl die bitweise AND, OR und XOR Verknüpfungen gebildet werden. Mit den hier vorgegebenen Größen 12 und 6 sollte der Code 4, 14 und 10 ausgeben als Resultate für a AND b, a OR b und a XOR b.

                @Start 
                -3 

a:              12                            # Eingangswert a
b:              6                             # Eingangswert b

aANDb:          0                             # Ergebnis der AND Verknüpfung von a und b
aORb:           0                             # Ergebnis der OR Verknüpfung von a und b
aXORb:          0                             # Ergebnis der XOR Verknüpfung von a und b

tmp:            0                             # Pufferspeicher
min:            0                             # kleinerer Wert von a und b
max:            0                             # großer Wert von a und b
restMin:        0                             # Puffer für Divisionsrest
restMax:        0                             # Puffer für Divisionsrest
pOne:           1                             # Konstante +1
mTwo:           -2                            # Konstante -2
sum:            0                             #
bit:            -1                            # Zu addierender Wert, variabel

retShiftMin:    @shiftMinDone                 # Rücksprungadressen nach dem shift right
retShiftMax:    @shiftMaxDone 

                INCLUDE DIV

Start:

REM Ermittlung des größeren Werts als Treiber für die Schleife

                SUB @tmp @a                   # tmp = -a
                SUB @min @tmp                 # min = a
                SUB @min @b                   # min = a - b
                JA  @min @aIsLarger 
                SUB @min @min 
                SUB @min @tmp                 # min = a
                SUB @tmp @tmp 
                SUB @tmp @b 
                SUB @max @tmp                 # max = b
                JA  0 @loop 
aIsLarger:      SUB @max @tmp                 # max = a
                SUB @tmp @tmp 
                SUB @tmp @b 
                SUB @min @min 
                SUB @min @tmp                 # min = b

loop:

REM bitweises vergleichen, solange der größere Wert (max) ungleich null ist

                JA  @max @shiftAndCompare 
output:         SUB @tmp @tmp 
                SUB @tmp @aANDb 
                SUB -1 @tmp 
                SUB @tmp @tmp 
                SUB @tmp @aORb 
                SUB -1 @tmp 
                SUB @tmp @tmp 
                SUB @tmp @aXORb 
                SUB -1 @tmp 
                SUB 0 0                       # Programmausstieg

shiftAndCompare:

REM shift right (Division durch 2 mit Rest) des kleineren Werts (min)
REM danach steht in min der geshiftete Wert, in restMin das entfallene Bit

                JA  @min @shiftMin            # wenn min bereits null ist, kann man sich die Division ersparen
                SUB @restMin @restMin 
                JA  0 @shiftMax 
shiftMin:
                SUB @tmp @tmp 
                SUB @tmp @min 
                SUB @DIV_a @DIV_a 
                SUB @DIV_a @tmp 
                SUB @DIV_b @DIV_b 
                SUB @DIV_b @mTwo 
                SUB @tmp @tmp 
                SUB @tmp @retShiftMin 
                SUB @DIV_return @DIV_return 
                SUB @DIV_return @tmp 
                JA  0 @DIV 
shiftMinDone:   SUB @tmp @tmp 
                SUB @tmp @DIV_result 
                SUB @min @min 
                SUB @min @tmp 
                SUB @tmp @tmp 
                SUB @tmp @DIV_a 
                SUB @restMin @restMin 
                SUB @restMin @tmp 

REM shift right (Division durch 2 mit Rest) des größeren Werts (max)
REM danach steht in max der geshiftete Wert, in restMax das entfallene Bit

shiftMax:
                SUB @tmp @tmp 
                SUB @tmp @max 
                SUB @DIV_a @DIV_a 
                SUB @DIV_a @tmp 
                SUB @DIV_b @DIV_b 
                SUB @DIV_b @mTwo 
                SUB @tmp @tmp 
                SUB @tmp @retShiftMax 
                SUB @DIV_return @DIV_return 
                SUB @DIV_return @tmp 
                JA  0 @DIV 
shiftMaxDone:   SUB @tmp @tmp 
                SUB @tmp @DIV_result 
                SUB @max @max 
                SUB @max @tmp 
                SUB @tmp @tmp 
                SUB @tmp @DIV_a 
                SUB @restMax @restMax 
                SUB @restMax @tmp 

REM Summe der entfallenen Bits berechnen als Basis für alle weiteren Berechnungen
REM sum = 0 => 00, sum = 2 => 11, sum = 1 => 10|01

                SUB @tmp @tmp 
                SUB @tmp @restMin 
                SUB @tmp @restMax             # tmp = -(restMin + restMax)
                SUB @sum @sum 
                SUB @sum @tmp                 # sum = restMin + restMax

                JA  @sum @orTrue              # sum > 0 => OR ist schon mal wahr
                JA  0 @checksDone             # sum == 0 => jede Operation liefert 0
orTrue:         SUB @aORb @bit                # aORb = 1 . aORb
checkAND:       SUB @sum @pOne                # sum = restMin + restMax - 1
                JA  @sum @andTrue             # sum -1 > 0 (kann nur bei sum == 2 der Fall gewesen sein) => AND wahr, andernfalls XOR wahr
xorTrue:        SUB @aXORb @bit               # aXORb = 1 . aXORb
                JA  0 @checksDone 
andTrue:        SUB @aANDb @bit               # aANDb = 1 . aANDb

REM shift left für bit, dies ist jeweils eine Multiplikation mit  2,
REM bzw. eine Addition mit sich selbst und das Ergebnis der log. Operationen
REM an der ersten Stelle anfügen zu können

checksDone:     SUB @tmp @tmp 
                SUB @tmp @bit 
                SUB @bit @tmp                 # bit *= 2

                JA  0 @loop                   # Schleifenende

Und weiter?

JASm kann also auch komplexere Berechnungen vornehmen, wobei der Aufwand, bzw. der Codebedarf zunehmend steigt. Die Verwendung von Makros ist also durchaus angezeigt. Für die beispielhafte JASm Laufzeitumgebung wurden nun einige Makros hinterlegt:

  • EXIT als unparametrisiertes Programmende (SUB 0 0)
  • ADD als Additionsfunktion von @ADD_a und @ADD_b
  • DIV als Division von @DIV_a und @DIV_b mit Restermittlung
  • EUCLID als Funktion zur Ermittlung des größten gemeinsamen Teilers (ggT).

Die Makros folgen alle der bereits vorgestellten JASm Makro Spezifikation und liefern ihre Ergebnisse in _result zurück, fordern die Rücksprungadresse in _return an und setzen ggf. _error und individuelle Variablen.

In den kommenden Beträgen werden weitere Algorithmen vorgestellt, unter anderem Listenbearbeitungen.

Inhalt

Beitrag vorlesen lassen

Kommentar hinterlassen

Nutze dieses Kommentarfeld um deine Meinung oder Ergänzung zu diesem Beitrag kundzutun. Verhalte dich bitte respektvoll und höflich! Kommentare werden vor der Veröffentlichung in der Regel moderiert und bei Verstößen gegen geltendes Recht, die guten Sitten, fehlendem Bezug oder missbräuchlicher Verwendung nicht freigegeben oder gelöscht.
Über die Angabe deines Namens, deiner E-Mail Adresse und deiner Webseite freuen wir uns, doch diese Felder sind optional. Deine E-Mail Adresse wird dabei zu keinem Zeitpunkt veröffentlicht.

Um mit dem Betreiber dieser Seite nicht-öffentlich in Kontakt zu treten, nutze die Möglichkeiten im Impressum.