Dzielenie i modulo liczb całkowitych bez znaku z 6 rejestrami
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
Odejmowanie nasycające i jzero
umoż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.)
jodd
pozwala 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*divisor
z 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)