DIV 연산 코드가없는 어셈블리에서 임의의 수 (16 비트)를 3으로 나누는 방법이 더 빠릅니다.

Question

부호없는 정수를 3으로 나눕니다. 8086 어셈블리 또는 이와 유사한 방법으로 DIV 연산 코드를 사용하고 싶지는 않습니다.

Answer 1

필수 대답은 "일정 원하는 당신의 역수를 곱"하는 것입니다, 곱셈을 수행하기 위해 쉬프트 앤 가드를 사용하고, 바이너리 포인트의 위치를 ​​올바르게 잡기위한 몇 가지 가능한 포스트 시프트를 사용한다.

트릭은 예상되는 가장 큰 입력 배당금의 크기를 처리하기 위해 상호의 정밀도가 무엇인지 알아내는 것입니다. 가장 큰 입력 피연산자가 전체 레지스터라는 것을 분명히 결정할 수 있지만, 더 많이 알면 더 적은 비트로 역수를 사용할 수있어 더 빠른 shift-add 스타일을 얻을 수 있습니다.

Cuoq의 대답은 좋은 참고 자료입니다.

Answer 2

"해커의 기쁨"의 10 장 "정수로 정수 나누기"를 읽어보십시오. Bonus content은 해당 장에서 사용할 수 있지만 장 자체에서는 사용할 수 없습니다.

또는 주어진 상수를 찾기 위해 첫 번째 단계에서 알려진 알고리즘을 적용 할 라이브러리 인 libdivide을 사용하면 지정된 분모로 나누는 것이 더 빠릅니다.

libdivide 페이지에서 지적했듯이 컴파일러는 컴파일 타임 상수를 곱셈과 쉬프트로 변환하는 방법을 알고 있으므로 가장 간단한 방법은 컴파일러를 사용하는 것입니다. 나는 당신을 위해 그것을 할 것이지만 나는 16 비트 컴파일러를 가지고 있지 않다. 32 비트 컴파일러를 수행 할 경우, 결과는 다음과 같다 : C 함수에 대한

movw $-21845, %ax 
    mulw 8(%ebp) 
    andl $65534, %edx 
    movl %edx, %eax 
    shrl %eax 

:

int f(unsigned short d) 
{ 
    return d/3; 
}