Josephus-Problem

Benutzeravatar
el_primo
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 8. Nov 2005 00:42

Josephus-Problem

Beitrag 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
The idea of style and competing for the best style is key to all forms of rocking

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Josephus-Problem

Beitrag 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 ;)

Sascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 245
Registriert: 13. Apr 2004 19:23
Wohnort: Darmstadt
Kontaktdaten:

Re: Josephus-Problem

Beitrag 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.)

philippD.
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 1. Okt 2008 12:50

Re: Josephus-Problem

Beitrag 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

Benutzeravatar
el_primo
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 8. Nov 2005 00:42

Re: Josephus-Problem

Beitrag 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 :)
The idea of style and competing for the best style is key to all forms of rocking

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Josephus-Problem

Beitrag 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).

Benutzeravatar
el_primo
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 8. Nov 2005 00:42

Re: Josephus-Problem

Beitrag von el_primo »

Viel geholfen, danke, ivoch!!!
The idea of style and competing for the best style is key to all forms of rocking

philippD.
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 1. Okt 2008 12:50

Re: Josephus-Problem

Beitrag von philippD. »

hmpf... das nächste mal antwort ich ausführlicher... genaus so hab ichs auch :P

Antworten

Zurück zu „Archiv“