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
Beitrag #5676508 wurde vom Autor gelöscht.
Die Zahl auf negativ testen und links schieben. Was bedeutet auf negativ testen ?
:
Bearbeitet durch User
Hätte jetzt spontan gesagt: Nach links schieben und das Carry-Flag auswerten.
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. Und damit wärst du durchgefallen.
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?
:
Bearbeitet durch User
Ich denke man müsste 0x00110000 erst einmal in Binärdarstellung bringen, oder? Denke nicht, dass man mit 0x00110000 etwas anfangen kann.
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. ;-)
Beitrag #5676586 wurde vom Autor gelöscht.
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.
:
Bearbeitet durch User
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?
Beitrag #5676702 wurde vom Autor gelöscht.
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.
:
Bearbeitet durch User
Das würde ich so interpretieren, daß hier ein String vorliegt. Tom.K schrieb: > von einem Bit String 0x00110000
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.
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.
:
Bearbeitet durch User
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.
Das Problem ist unter dem Namen "popcount" bekannt. Dazu gibt's auch viel im Internet. Einige Architekturen haben sogar einige Instruktionen dafür.
Ich kenne nur Popcorn. Hast Du auch eine Ahnung wofür man das braucht wenn manche Systeme sogar Instruktionen für haben?
"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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.