Division 16-Bit durch 16-Bit

[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