Division 16-Bit durch 16-Bit

[johny7]

Moin allerseits,

es ist an vielen Stellen im Internet beschrieben, wie eine Division durch Subtraktion durchgeführt wird. Meist nur als Assembler-Code-Beispiel. Geteilt werden 16Bit durch 8 Bit oder 32 durch 32 Bit-Zahlen.
Ich muss nun einmal 16 durch 16-Bit teilen. Kann mir jemand das Grundprinzip erklären? Wenn ein ASM-Code gleich dabei ist, umso besser.

Grüße, JN

[Encoder]

Was solls denn werden? Vielleicht kann man dir dann ein bisschen besser drauf helfen.
Hast du das Prinzip an sich verstanden?

[johny7]

Moin allerseits,

Was solls denn werden? Vielleicht kann man dir dann ein bisschen besser drauf helfen.

Ich muss den Widerstandswert per UART an den PC senden und nicht die Spannung und Stromstärke, die dann im Computer berechnet werden müsste, wie bisher.

Hast du das Prinzip an sich verstanden?

Ja, ich habe es vorher schon einmal durchprobiert.

Ich habe allerdings mittlerweile eine Implementierung des Herstellers gefunden, die für mich genau passt. Ich habe nur nicht bei der Registerwahl berücksichtigt, dass ich in den Bereich des Stacks gegangen bin.
Nun, bin eben ziemlich am Anfang bei Assembler.

Grüße, JN

[Tom]

Hello,

Ich muss nun einmal 16 durch 16-Bit teilen. Kann mir jemand das Grundprinzip erklären? Wenn ein ASM-Code gleich dabei ist, umso besser.

Ich verstehe jetzt nicht, wo da das Problem ist.

Du legst in einem Register den Startwert (Dividend) ab. [2]
Im anderen Register legst Du den Divisor ab. [2]
Ein drittes Register benutzt Du zum zählen. [2]

Nun baust Du eine Schleife auf, in der vom Dividenden der Divisor so fot abgezogen wird, bis der Dividend kleiner ist (oder Null [1]), als der Divisor. Ist dieser Punkit erreicht, hast Du im Zählerregister den Quotienten und im Dividenden-Register den Rest stehen.

Interessant an der Sache ist,
[1} Grenzen betrachten:

Wenn Du dich der Grenze des Definitionsbereiches näherst, musst Du diese sauber erkennen. Es ist also wichtig, ob Du negative Zahlen zulässt, oder nicht. Durch den Überschlag [3] kann es sonst zu falschen Ergebnissen führen.

[2] Welches Register wofür verwenden:
Das hängt vom Prozessor und teilweise auch ungeschriebenen Konventionen ab.
I.d.R. wird z.B. das C*-Register zum Zählen verwendet. Das hängt meistens davon ab, welche Assemblerbefehle bestimmte Register voraussetzen.

[3] Das Überschreiten einer Grenze, also ein Überchlag, wird i.d.R. in einem speziellen Register oder einem Flag angezeigt (z.B. Carry-Flag). Oft muss man die Flags erst in ein Register laden, um sie abfragen zu können, manchmal gibt es aber auch spezielle Assembler-Befehle, um einzelne Flags gezielt abzufragen.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Der Martin]

Hi,

es ist an vielen Stellen im Internet beschrieben, wie eine Division durch Subtraktion durchgeführt wird.

ja, es geht aber auch eleganter (performanter), so dass man eine Division "nur" auf m Subtraktionen und 2m Bit-Shifts abbildet (m=Wortbreite des Zählers in Bit), anstatt bis zu 2^n Subtraktionen.

Ich muss nun einmal 16 durch 16-Bit teilen. Kann mir jemand das Grundprinzip erklären?

Wo liegt das Problem, eines der vielen 32/16-Beispiele zu nehmen und einfach das höherwertige Wort des Dividenden implizit als 0 zu betrachten?

Ansonsten versuche, den Algorithmus für die ausführliche schriftliche Division, die wohl so ziemlich jeder von uns in der Schule gelernt hat, auf die Binär-Notation anzupassen. Es wird dadurch sogar einfacher!

Bezeichnungen:
   Z - Zähler (m Bit)
   N - Nenner (n Bit)
   Q - Quotient (m Bit)
   H - Hilfsregister (m Bit)

Pseudocode:

H = 0
  Wiederhole m-mal
     Rotiere Z um 1bit nach links (MSB ins Carry)
     Rotiere H um 1bit nach links (Carry ins LSB)
     Wenn H>N
        Subtrahiere N von H
        Setze Carry
     Sonst
        Lösche Carry
     Rotiere Q um 1bit nach links (Carry ins LSB)
  Schleife Ende
  Q enthält nun den Quotienten
  H enthält nun den Divisionsrest

Dieser Ansatz arbeitet vorzeichenlos (unsigned) und hat die Eigenschaft, bei Division durch 0 ein definiertes Ergebnis zu liefern - nämlich ein Ergebnis, in dem alle Bits gesetzt sind, z.B. 0xFFFF. Will man das als echte Fehlerbedingung ausschließen, muss man den Nenner vorher auf 0 prüfen.

Viel Spaß,
 Martin

[Der Martin]

Korrektur:

Pseudocode:

H = 0
  Wiederhole m-mal
     Rotiere Z um 1bit nach links (MSB ins Carry)
     Rotiere H um 1bit nach links (Carry ins LSB)
     Wenn H>N

Hier muss es H>=N heißen!

Dieser Ansatz arbeitet vorzeichenlos (unsigned) und hat die Eigenschaft, bei Division durch 0 ein definiertes Ergebnis zu liefern - nämlich ein Ergebnis, in dem alle Bits gesetzt sind, z.B. 0xFFFF.

... und gleichzeitig ist der Divisionsrest H gleich dem Zähler Z.

Ciao,
 Martin