Seite 1 von 1

Josephus-Problem

Verfasst: 9. Nov 2009 14:05
von el_primo
Hallo,

Mit einer Bit-Maske bestimme ich, ob ein Soldat noch lebt und an welcher Position er sich befindet. Kann mir jemand sagen, wie man weißt, welche Position ein Bit im Register hat? Zum Beispiel ist 001000 eine dezimale 8 und das Bit 1 steht an der 3. Position, da 2^3. Das würde mit Logarithmus auf den ersten Blick gehen. Oder gibt es ein besseres Vorgehen? Wie implementiert man dann Algorithmus in MIPS?

Danke im Voraus,
Alex

Re: Josephus-Problem

Verfasst: 9. Nov 2009 14:57
von ivoch
Verstehe ich dich richtig, dass du auf einzelne Bits zugreifen willst? Dies könntest du so machen:

Code: Alles auswählen

#du willst auf das 3. Bit im Register $t0 zugreifen, in dem z.B. 11000 geladen ist
srl $t0, $t0, 3    #jetzt ist das "dritte Bit" auf Index 0, also sieht die Zahl im $t0 so aus: 11
andi $t0, $t0, 1   #hier machst du nichts anderes als $t0 AND 1 = $t0 setzen
Alternativ könntest du erst nach links shiften, bis das gesuchte Bit ganz links liegt, dann wieder nach rechts, damit es ganz nach rechts geht. Warum beide Verfahren wie erwartet funktionieren, kannst du dir dann selbst überlegen ;)

Re: Josephus-Problem

Verfasst: 9. Nov 2009 15:10
von Sascha
el_primo hat geschrieben:Kann mir jemand sagen, wie man weißt, welche Position ein Bit im Register hat?
Einige Prozessoren, wie bspw. die x86-Familie, haben für diesen Zweck tatsächlich eigene Opcodes. MIPS hat meines Wissens leider nichts in der Richtung, und man muss in einer Schleife die Bits der Reihe nach abfragen. (Etwa so wie ivoch es im letzten Posting erklärt hat.)

Re: Josephus-Problem

Verfasst: 9. Nov 2009 15:52
von philippD.
wenn du nur die position rauskriegen willst wäre es wohl das beste solange shiften bis es raus fällt -> register wird 0
und nebenher nen zähler laufen zu lassen

Re: Josephus-Problem

Verfasst: 9. Nov 2009 21:27
von el_primo
Mein Problem nochmal: ich habe eine binäre Zahl, die immer durch 2 teilbar ist, also immer als 2^n repräsentiert wird. Zum Beispiel 001000 (eine 8 ) oder 000100 (eine 4). Den eigentlichen dezimalen Wert dieser Zahl kenne ich aber nicht, weil es in meinem Algorithmus keinen Zähler dazu geben kann. Jetz will ich wissen, nachdem ich durch alle Soldaten in Bit-Darstellung iteriert habe, an welcher Position meine 1 steht, damit ich bestimmen kann, welchen Soldaten der Reihe nach ich habe.
Ich hoffe, das sieht als Erklärung besser aus :)

Re: Josephus-Problem

Verfasst: 9. Nov 2009 21:43
von ivoch
Wenn es wirklich nur eine Eins im ganzen Register ist, dann könntest du dir eine Schleife basteln und in jedem Durchlauf diesen Register um 1 nach Rechts shiften und gleichzeitig einen Zähler um Eins erhöhen - dieser Zähler wird dir am Ende die Position der Eins zeigen. Abbrechen musst du wenn deine Zahl im Register gleich 1 wird (oder 0, je nachdem wie du zählst).

Wenn hinter dieser Eins noch weitere Einser sein könnten (also an höheren Positionen), dann müsstest du deine Schleife so ändern, dass du bei jedem Schritt auch versuchst, die Zahl durch zwei zu teilen und dann schaust, ob es im "hi"-Register eine 0 oder eine 1 steht (letztere würde bedeuten, dass deine andere 1 gerade auf Index 0 war und in diesem Fall müsstest du die Schleife abbrechen).

Re: Josephus-Problem

Verfasst: 9. Nov 2009 22:02
von el_primo
Viel geholfen, danke, ivoch!!!

Re: Josephus-Problem

Verfasst: 10. Nov 2009 10:48
von philippD.
hmpf... das nächste mal antwort ich ausführlicher... genaus so hab ichs auch :P