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.
