Dzielenie i modulo liczb całkowitych bez znaku z 6 rejestrami

Dec 02 2020

Muszę znaleźć algorytm czasu logowania (dla maszyny wirtualnej) przy użyciu maksymalnie 6 rejestrów (a, b, c, d, e, f) do podzielenia dwóch liczb całkowitych bez znaku N1 i N2 ([obie są> = 0] dodatnie lub 0) gdzie jeśli dzielnik jest równy 0, to wynik wynosi 0 i operacja modulo.

  • div -> N1 / N2
  • mod -> N1% N2

z poleceniami takimi jak

  • RESETUJ a -> a = 0
  • DODAJ ab -> a = a + b
  • SUB ab -> a = max (0, ab)
  • SHR a -> a = podłoga (a / 2)
  • SHL a -> a = podłoga (a * 2)
  • INC a -> a + = 1
  • DEC a -> a = max (0, a-1)
  • JUMP j -> skok do j-tej linii
  • JZERO xj -> jeśli x wynosi 0, to przeskocz do k + j
  • JODD xj -> jeśli x jest nieparzyste, to skocz do k + j

Czy są jakieś algorytmy, które mogą mi pomóc?

Mogę tylko sprawdzić, czy wartość w reg jest ODD czy ZERO.

Dziękuje Ci za pomoc.

Odpowiedzi

1 PeterCordes Dec 02 2020 at 18:34

Odejmowanie nasycające i jzeroumożliwia porównywanie dla mniejszych lub równych (lub większych niż), dzięki czemu można zaimplementować odpowiedź njuffa w wersji C na temat Jak mogę mnożyć i dzielić, używając tylko przesuwania bitów i dodawania? co daje iloraz i resztę. Ponieważ masz nienasycające dodawanie, możesz zaimplementować dodatek zawijający (a następnie wykonać ręczne wykrywanie wykonania, sprawdzając zawijanie, tak jak robi to Nathan w C.)

joddpozwala przetestować niski bit, na przykład if (x&1), który pozwoliłby Ci również zaimplementować standardowy algorytm mnożenia. Więc gdybyś miał algorytm dzielenia, który dałby ci tylko iloraz, mógłbyś to zrobić remainder = dividend - quotient*divisorz mnożeniem czasu logarytmicznego.


Inne pytania i odpowiedzi dotyczące dzielenia binarnego:

  • Jak mogę mnożyć i dzielić używając tylko przesunięcia bitowego i dodawania? - kolejna odpowiedź na te same pytania i odpowiedzi, tym razem wykorzystując przesunięcia, aby „wyrównać” najbardziej znaczący fragment dzielnika z dywidendą przed przystąpieniem do dzielenia długiego z podręczników. Ale nie jest jasne, czy jest to bezpieczne bez liczb całkowitych o rozszerzonej szerokości.
  • Logarytmiczne dzielenie liczb całkowitych w czasie przy użyciu tylko dodawania i odejmowania z przesunięciem bitowym
  • Jak mogę użyć przesuwania bitów, aby zastąpić dzielenie liczb całkowitych?
  • Podzielić przez 10 za pomocą przesunięć bitowych? mnoży się na każdym kroku, co jest dobre tylko wtedy, gdy masz szybkie mnożenie lub dla znanych stałych z kilkoma ustawionymi bitami, więc zajmuje to tylko kilka przesunięć / dodań. Kolejną zaletą jest to, że nie wymaga zmiany w prawo, ale masz właściwą zmianę. (W przeciwieństwie do niektórych zabawkowych ISA)