[c] 비트 이동 및 더하기 만 사용하여 곱하고 나누는 방법은 무엇입니까?

교대와 더하기를 사용하는 정수를 나누는 절차는 초등학교에서 가르치는 것처럼 십진수 장 나눗셈에서 간단하게 파생 될 수 있습니다. 숫자가 0과 1 중 하나이므로 각 몫 숫자의 선택이 단순화됩니다. 현재 나머지가 제수보다 크거나 같으면 부분 몫의 최하위 비트는 1입니다.

십진수 긴 나눗셈과 마찬가지로 피제수는 최상위에서 최하위까지 한 번에 한 숫자로 간주됩니다. 이진 나눗셈의 왼쪽 이동으로 쉽게 수행 할 수 있습니다. 또한 현재 몫 비트를 한 위치만큼 왼쪽으로 이동 한 다음 새 몫 비트를 추가하여 몫 비트를 수집합니다.

고전적인 배열에서 이러한 두 개의 왼쪽 시프트는 하나의 레지스터 쌍의 왼쪽 시프트로 결합됩니다. 위쪽 절반에는 현재 나머지가 있고 아래쪽 절반에는 배당금이 있습니다. 배당 비트가 왼쪽 시프트에 의해 나머지 레지스터로 전송되므로 사용되지 않은 하위 절반의 최하위 비트가 몫 비트를 누적하는 데 사용됩니다.

아래는 x86 어셈블리 언어와이 알고리즘의 C 구현입니다. 시프트 및 더하기 나누기의이 특정 변형은 현재 나머지에서 제수를 빼는 것이 나머지가 제수보다 크거나 같지 않으면 수행되지 않기 때문에 때때로 “실패하지 않는”변형이라고도합니다. C에서는 레지스터 쌍 왼쪽 시프트의 어셈블리 버전에서 사용하는 캐리 플래그 개념이 없습니다. 대신, 모듈로 2 ⁿ 덧셈의 ​​결과가 수행이있는 경우에만 덧셈 보다 더 작을 수 있다는 관찰을 기반으로 에뮬레이션 됩니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define USE_ASM 0

#if USE_ASM
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot;
    __asm {
        mov  eax, [dividend];// quot = dividend
        mov  ecx, [divisor]; // divisor
        mov  edx, 32;        // bits_left
        mov  ebx, 0;         // rem
    $div_loop:
        add  eax, eax;       // (rem:quot) << 1
        adc  ebx, ebx;       //  ...
        cmp  ebx, ecx;       // rem >= divisor ?
        jb  $quot_bit_is_0;  // if (rem < divisor)
    $quot_bit_is_1:          // 
        sub  ebx, ecx;       // rem = rem - divisor
        add  eax, 1;         // quot++
    $quot_bit_is_0:
        dec  edx;            // bits_left--
        jnz  $div_loop;      // while (bits_left)
        mov  [quot], eax;    // quot
    }
    return quot;
}
#else
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot, rem, t;
    int bits_left = CHAR_BIT * sizeof (uint32_t);

    quot = dividend;
    rem = 0;
    do {
            // (rem:quot) << 1
            t = quot;
            quot = quot + quot;
            rem = rem + rem + (quot < t);

            if (rem >= divisor) {
                rem = rem - divisor;
                quot = quot + 1;
            }
            bits_left--;
    } while (bits_left);
    return quot;
}
#endif