6 개의 레지스터가있는 부호없는 정수에 대한 나누기 및 모듈로
Dec 02 2020
두 개의 부호없는 정수 N1과 N2 ([둘 다> = 0] 양수 또는 0)을 나누기 위해 최대 6 개의 레지스터 (a, b, c, d, e, f)를 사용하여 로그 시간 알고리즘 (가상 머신 용)을 찾아야합니다. 분할기가 0이면 결과는 0이고 모듈로 연산입니다.
- div-> N1 / N2
- 모드-> N1 % N2
다음과 같은 명령으로
- 재설정 a-> a = 0
- ab 추가-> a = a + b
- SUB ab-> a = max (0, ab)
- SHR a-> a = 바닥 (a / 2)
- SHL a-> a = 바닥 (a * 2)
- INC a-> a + = 1
- DEC a-> a = max (0, a-1)
- JUMP j-> j 번째 줄로 점프
- JZERO xj-> x가 0이면 k + j로 점프
- JODD xj-> x가 k + j로 점프하는 것보다 홀수이면
나를 도울 수있는 알고리즘이 있습니까?
reg의 값이 ODD인지 ZERO인지 만 확인할 수 있습니다.
도움을 주셔서 감사합니다.
답변
1 PeterCordes Dec 02 2020 at 18:34
채도 빼기 및 jzero작거나 같음 (또는보다 큼) 비교를 허용하므로 비트 시프트 및 더하기 만 사용하여 곱하고 나눌 수 있는 방법에 대한 njuffa의 답변의 C 버전을 구현할 수 있습니다. 몫과 나머지를 생성합니다. 비 포화 추가가 있으므로 래핑 추가를 구현할 수 있습니다 (그런 다음 Nathan이 C에서하는 것처럼 래핑을 확인하여 수동 수행 감지를 수행합니다.)
joddif (x&1)표준 곱하기 알고리즘을 구현할 수있는 , 같은 낮은 비트를 테스트 할 수 있습니다 . 따라서 몫만 제공하는 나눗셈 알고리즘이 remainder = dividend - quotient*divisor있다면 로그-시간 곱셈으로 할 수 있습니다.
다른 이진 분할 Q & A :
- 비트 이동과 더하기 만 사용하여 곱하고 나누는 방법은 무엇입니까? -동일한 Q & A에 대한 또 다른 답변입니다. 이번에는 교과서 긴 나눗셈을 진행하기 전에 가장 중요한 제수 비트를 배당금과 "정렬"하는 이동을 사용합니다. 그러나 확장 너비 정수없이 안전하다는 것은 분명하지 않습니다.
- 비트 시프트 더하기 및 빼기 만 사용하는 로그 시간 정수 나눗셈
- 정수 나누기를 대체하기 위해 비트 이동을 어떻게 사용할 수 있습니까?
- 비트 시프트를 사용하여 10으로 나누시겠습니까? 모든 단계에서 곱하기를 수행합니다. 이는 빠른 곱셈이 있거나 몇 비트가 설정된 알려진 상수에 대해서만 좋습니다. 또 다른 장점은 오른쪽 시프트가 필요하지 않지만 오른쪽 시프트가 있다는 것입니다. (일부 장난감 ISA와 달리)