Servus,
ich sitze gerade vor einem kleinen Problem und zwar soll ich im
Assemblercode von einem Bit String 0x00110000 die Nullen zählen.
Klar ist, ich muss hier eine Schleife anwenden und jede einzelne stelle
mit 0 vergleichen und nebenbei einen Counter laufen lassen.
Mein Problem ist, dass ich nicht weiß, wie ich mit 0x00110000 umgehen
soll, also wie ich auf die einzelnen Bits zugreifen kann.
Lerne seit 2 Wochen MIPS mit MARS und irgendwie ist es zum verzweifeln.
Habt ihr eine Idee?
Grüße Tom
Zitronen F. schrieb:> Die Zahl auf negativ testen und links schieben.>> Was bedeutet auf negativ testen ?
Danke für deine Antwort, aber wie hilft mir das Linksschieben denn
weiter?
Damit mache ich doch nur:
$s0=0000 0000 1001
sll $t0,$s0,2
$t0=0000 0010 0100
Damit habe ich doch mein Problem, wie ich auf die einzelnen Bits
zugreife, damit ich sie vergleichen kann, nicht gelöst?
qwertzuiopü+ schrieb:> Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag> auswerten.
Wäre eine Möglichkeit, aber dabei komme ich in ganz neue Gewässer und
hätte keine Ahnung wie ich den Übertrag dann abspeichere
A. K. schrieb:> qwertzuiopü+ schrieb:>> Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag>> auswerten.>> Und damit wärst du durchgefallen.
Magst du das weiter ausführen?
qwertzuiopü+ schrieb:>>> Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag>>> auswerten.>>>> Und damit wärst du durchgefallen.>> Magst du das weiter ausführen?
Wie kommt man in der MIPS ISA denn an das Carry-Flag ran?
A. K. schrieb:> qwertzuiopü+ schrieb:>>>> Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag>>>> auswerten.>>>>>> Und damit wärst du durchgefallen.>>>> Magst du das weiter ausführen?>> Wie kommt man in der MIPS ISA denn an das Carry-Flag ran?
Gute Frage. MIPS ist doch schon etwas her...
Man könnte natürlich mit 0b10000...00 vergleichen. Ist das Register
größer/gleich, steht vorne ne 1, sonst nicht. Danach schiebt man es eins
nach links weiter (Oder das Vergleichsregister eins nach rechts).
qwertzuiopü+ schrieb:> A. K. schrieb:>> qwertzuiopü+ schrieb:>>>>> Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag>>>>> auswerten.>>>>>>>> Und damit wärst du durchgefallen.>>>>>> Magst du das weiter ausführen?>>>> Wie kommt man in der MIPS ISA denn an das Carry-Flag ran?>> Gute Frage. MIPS ist doch schon etwas her...
Merkt man. Es gibt kein Carry Flag. ;-)
Tom.K schrieb:> Ich denke man müsste 0x00110000 erst einmal in Binärdarstellung bringen,> oder? Denke nicht, dass man mit 0x00110000 etwas anfangen kann.
Nicht du sollst die Bits zählen, sondern die Maschine. Und zwar so, dass
es egal ist, welche Werte man ihr vorsetzt.
A. K. schrieb im Beitrag #5676586:
> Tom.K schrieb:>> Ich denke man müsste 0x00110000 erst einmal in Binärdarstellung bringen,>> oder?>> Fang weiter vorne an. Bei den allerersten Grundlagen. Die fehlen> nämlich.
Könntest du dies etwas präzisieren?
Bitte jetzt nicht falsch verstehen, ist nicht böse gemeint, aber was
meinst du mit allerersten Grundlagen?
Du bist wahrscheinlich schon so erfahren mit Assemblern, dass bestimmt
Dinge meist, die ich selbst nach 10000 mal lesen des Skriptes nicht
herausbekommen würde.
Hatte vor 1 Jahren schon einmal eine Frage zu C gestellt und dort wurde
mir genau der selbe Tipp gegeben, schlussendlich hat sich herausgestellt
(1 Woche weinen später), dass der Experte einfach in anderen Dimensionen
gedacht hat und etwas als Grundlagen verstanden hat, was zu dem
Zeitpunkt keine Grundlage war.
A. K. schrieb:> Hab es auch umformuliert.
Habe ich gesehen.
Danke erst einmal für deine Hilfe.
A. K. schrieb:> Tom.K schrieb:> Nicht du sollst die Bits zählen, sondern die Maschine. Und zwar so, dass> es egal ist, welche Werte man ihr vorsetzt.
Richtig!
Nur wie soll man damit denn sagen ob eine 1 oder 0 vorliegt?
Es gibt zwar Algorithmen im Internet, aber diese sind so komplex, und
kopieren möchte ich ja auch nicht.
Der generelle Algorithmus um die Bits zu zählen wäre in etwa so:
- Zählvariable auf 0 setzen
- Vom Wert alle Bits bis auf das niederwertigste ausmaskieren (AND mit
1)
- Ergebnis zur Zählvariable addieren
- String nach rechts schieben (SRL -- Shift right logical)
Das ganze solange wiederholen bis der Wert fertig bearbeitet ist.
Ich habe zwar keine Ahnung von MIPS mit MARS, aber man könnte es
bestimmt über das Carry lösen:
1. Zählvariable auf 0 setzen
2. Dummyvariable auf 0 setzen
3. String in Carry Schieben
4. Dummyvariable zu Zählvariable mit Carry addieren
5. zurück zu 3. bis alle 8 bits durch sind.
Hi, ich habe diselbe Aufgabe nur muss ich Einsen zählen und komme auch
seit Tagen nicht weiter
# Sie dürfen die unten stehenden Werte verändern um Ihre Implementierung
zu testen.
.data
output_text_number_bits_set: .asciiz "Number of bits set: "
output_data_intact: .asciiz "The input data is intact!"
output_data_corrupt: .asciiz "The input data seems to be corrupt!"
bit_string: .word 0x00001111
parity_bit: .byte 1
########################################################################
################
#
# main
#
.text
.globl main
main:
# Register sichern
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $s0, 4($sp)
# Loading the parity bit and the bit string
lw $a0, bit_string
jal count_bits_set
#Saving the result for printing
move $s0, $v0
la $a0, output_text_number_bits_set
jal print_string
move $a0, $s0
jal print_int
jal print_new_line
# Checking if the data is intact
move $a0, $s0
lb $a1, parity_bit
jal check_odd_parity
beq $v0, $zero, data_corrupt
la $a0, output_data_intact
jal print_string
j end_main
data_corrupt:
la $a0, output_data_corrupt
jal print_string
end_main:
lw $ra, 0($sp)
lw $s0, 4($sp)
addi $sp, $sp, 8
li $v0, 10
syscall
#
# end main
#
########################################################################
################
#Anfang der Hilfsfunktionen
# $a0: int to print
print_int:
li $v0, 1
syscall
jr $ra
# $a0: char to print
print_char:
li $v0, 11
syscall
jr $ra
print_new_line:
addi $a0, $0, 0xA
li $v0, 11
syscall
jr $ra
# $a0: string address to print
print_string:
li $v0, 4
syscall
jr $ra
#Ende der Hilfsfunktionen
########################################################################
################
########################################################################
################
############################################
#
# YOUR SOLUTION HERE BELOW!
#
############################################
# $a0: bit string to check for parity as a word
# $v0: number of bits set
count_bits_set:
jr $ra
############################################
#
# YOUR SOLUTION HERE ABOVE!
#
############################################
########################################################################
################
Alternativ kannst Du auch eine Lookup-Tabelle machen (z.B. byte-weise)
und hast in den einzelnen Tabelleneinträgen die Anzahl stehen.
Viel schneller als einzelne Bits zu zählen und hat einen vertretbaren
Speicheraufwand.
Hat er schon mit logischen Operationen gearbeitet?
Was ist bei dieser CPU der technische Unterschied zwischen Shiften und
Rotieren?
Könnte man auch dividieren?
Probiert doch mal links schieben und Vorzeichen testen.
Was rotieren und schieben machen, sollte im ASM Manual ersichtlich sein.
Ich empfehle eh, das ASM Manual, resp das Instruction manual zu
studieren.
Oder so:
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
Das Verfahren ist zwar nicht in MIPS-Assembler geschrieben, aber kommt
mit Operationen aus, die leicht nach MIPS übersetzbar sein sollten.
Notfalls macht GCC eine Vorlage. Und es braucht keine Schleifen/Sprünge,
was der Geschwindigkeit zuträglich ist.
Ach ja, es zählt die Einsen, aber das sollte ja kein unüberwindbares
Hindernis sein.
da in der Zwischenzeit eine zweite Aufgabe dazu gekommen ist, die sehr
ähnlich der ersten ist, gehe ich davon aus, dass es sich um Fragen zum
gleichen Kurs/Buch/Übungsaufgabe handelt.
Ben B. schrieb:> Das wäre jetzt die Frage... ob der 0x10101010 oder "0x10101010" meint.> Und wenn zweites, ob die Null vor dem X auch mitgezählt werden soll.
diese Frage kann man zumindest im folgenden Code eindeutig beantworten
Nadine schrieb:
1
> bit_string: .word 0x00001111
2
> parity_bit: .byte 1
3
[snip]
4
>
5
> # Loading the parity bit and the bit string
6
> lw $a0, bit_string
7
> jal count_bits_set
[quote]
Load word
lw rt, address
0x23 rs rt offset
6 5 5 16
Load 32-bit word at address into register rt.
[/quote]
A. K. schrieb:> Oder das unterste Bit addieren und nach rechts schieben.
wieder basierend auf dem Code von Nadine würde ich (auch) eine
Kombination aus
- bnez/beqz/bgez
- addi
- li
und noch ein paar weiteren Befehlen einsetzen.
aja, der Unterschied zwischen 0 und 1 zählen ist - bei der Lösung dir
mir grad durch den Kopf geht - nur ein Befehl.
über Auswertung der Parität habe ich mir jetzt keine Gedanken gemacht,
hab so schon genug Kopfweh.
---
wow, dass ich mein (fast 20 jahre altes) mips-manual noch mal
brauche/öffne hätte ich mir bis inkl. letztes jahr nicht gedacht ;-)
Mir ist durch die zahlreichen Einträge leider immer noch nicht klar
geworden, was wie sich die gesetzten Bits zählen und zurückgeben lassen
anhand dem Beispiel welches von Nadine beigefügt wurde.
Bitte um eine triviale Lösung im Schritt für Schritt Verfahren damit ich
es verstehe. Was man tun muss um die 1en in einem String zu zählen und
wieder zurückgeben zu können.
Vielen Dank für die Hilfe im Voraus
Silas
Silas schrieb:> Mir ist durch die zahlreichen Einträge leider immer noch nicht> klar> geworden, was wie sich die gesetzten Bits zählen und zurückgeben lassen> anhand dem Beispiel welches von Nadine beigefügt wurde.> Bitte um eine triviale Lösung im Schritt für Schritt Verfahren damit ich> es verstehe. Was man tun muss um die 1en in einem String zu zählen und> wieder zurückgeben zu können.>> Vielen Dank für die Hilfe im Voraus> Silas
Sry aber wir machen hier nicht eure Hausaufgaben. Es gibt 100
Algorithmen dazu im Internet
Es wurden alle Stichworte genannt, die zur Erarbeitung einer eigenen
Lösung nützlich sind. Und nicht nützliche, aber das haben Foren so an
sich.
Wer bei Assembler nicht wirklich völlig blank ist, sollte es auf dieser
Grundlage dann auch selber schaffen. Darum geht es nämlich. Andernfalls
trägt auch eine fertige Lösung wenig zur Erkenntnis bei.
Manchmal funktioniert es auch besser, sich konkret von Auge zu Auge
helfen zu lassen. Dann kann der Helfer nämlich sanft in die richtige
Richtung stupsen und er kann erkennen, wieviel Basis überhaupt da ist,
auf der aufgebaut werden kann. Mein bisheriger Eindruck ist leider:
nichts. Das pflegt in Foren eher abzuschrecken.
Silas schrieb:> Mir ist durch die zahlreichen Einträge leider immer noch nicht klar> geworden, was wie sich die gesetzten Bits zählen und zurückgeben lassen> anhand dem Beispiel welches von Nadine beigefügt wurde.> Bitte um eine triviale Lösung im Schritt für Schritt Verfahren damit ich> es verstehe. Was man tun muss um die 1en in einem String zu zählen und> wieder zurückgeben zu können.>> Vielen Dank für die Hilfe im Voraus> Silas
Zuerst muß man sich mal klar werden, was man eigentlich aus
Ausgangs-"Material" hat.
- Ein String mit Nullen und Einsen?
Also die Textrepräsentation einer Binärezahhl?
Falls ja, die sollte nicht mit 0x beginnen,
denn das ist die C Knvention für hexadezimal.
- Ein Bit-String?
So bezeichnet man üblicherweise Binärdaten,
deren Länge nicht zu den üblichen Längen 8/16/32/64-Bit passt.
- Eine Hexadezimal-Konstante?
Da wäre zu beachten, daß 0x00110000 nicht etwa 8, sonder 32Bits hat
und als Bits betrachtet 00000000000100010000000000000000 beinhaltet.
Mit letzterem, einem Ganzzahlwert liesen sich von mir oben verlinkte
Allgorithmen anwenden, Bitstrings müßte man zudem noch passend zerlegen,
bei Strings wird drüberiterrieren und bei '1'sen* Zähler erhöhen das
Einfachste sein.
*Man beachte die Schreibweise '1'en und verstehe warum!
Man das kann doch nicht so schwer sein, sowas ist normalerweise eine
Programmierübung, aber nicht mehr als das.
Falls es gar nicht anders geht:
1
if ($in=0) {$out=1;}
2
if ($in=1) {$out=0;}
3
if ($in=2) {$out=1;}
4
if ($in=3) {$out=0;}
5
if ($in=4) {$out=2;}
6
if ($in=5) {$out=1;}
7
if ($in=6) {$out=1;}
8
if ($in=7) {$out=0;}
9
if ($in=8) {$out=3;}
So, keine Lust, das jetzt für 128 Bit Zahlen aufzuschreiben.
Aber da wird doch ein Muster ersichtlich, mich würde es nicht wundern,
wenn jemand das in einer einzelnen Formel berechnen kann.
Ansonsten könnte man das als Algoritmus lösen.
1. Wenn Zahl gerade dann Nullen plus 1 und Zahl durch 2 teilen
2. Wenn Zahl ungerade dann Zahl minus 1 und durch 2 teilen
3. Wenn Zahl gleich 0 dann Ende
4. zurück zu 1
Das ganze hier mal in PHP, Umsetzung in andere
Programmiersprachen nicht mein Problem.
1
function nullbits($zahl) {
2
if ($zahl==0) {return 1;}
3
$nullen=0;
4
while ($zahl>0) {
5
if (($zahl%2)==0) {$nullen++;} else {$zahl--;}
6
$zahl=$zahl/2;
7
}
8
return $nullen;
9
}
Mist, damit ist mein Vorschlag oben leider hinfällig.
"Cray supercomputers early on featured a population count machine
instruction, rumoured to have been specifically requested by the U.S.
government National Security Agency for cryptanalysis applications."
Wenn man google bemüht findet man gleich was nettes dazu:
https://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT
Einige Beispiele im C-Buch von Kernighan und Ritchie legen (auch) recht
unverblümt Krypto-Alltag nahe ;)
Kurze Recherche legt zumindest x86 und ARM nahe. Ich kenne das auch aus
der Kryptographie, aber ich dachte ich hätte es auch schonmal aus der
Graphen-Richtung oder so gehört.
