비트 연산을 이용한 곱셈 나눗셈

■ 종이와 연필 방법

• 보기: 100110 ÷ 101 (38 ÷ 5 = 7 ...3)
  
  0111 몫 Q = q₃ q₂ q₁ q₀
  +---------
  제수 V 101 | 100110 피제수 D = R₄
  000 q₃ 2³ V
  ----------
  100110 R₃
  101 q₂ 2² V
  ----------
  10010 R₂
  101 q₁ 2¹ V
  ----------
  1000 R₁
  101 q₀ 2⁰ V
  ----------
  011 R₀ = 나머지

상기 나눗셈 방법은 피제수로부터 제수에 대한 뺄셈 연산의 반복인데

한 번씩 뺄셈 연산 후의 결과를 부분 나머지(partial remainder)라고 하며

이 부분 나머지가 제수보다 큰 경우엔 뺄셈 과정을 계속 반복하며

적을 경우에 연산이 종료됩니다. 이 과정을 보다 효과적으로 하기 위하여

피제수에서 그냥 제수를 빼지 않고 제수의 ...,

8, 4, 2, ... 배 (2의 승수 배)를 빼 줍니다.

즉, 두 번째 뺄셈과정은 q₂ 2² V를 피제수로부터 뺄셈 연산을 하는데

이는 제수 V를 네 번 반복하여 뺄셈 연산을 수행하는 것과 동일합니다.

이 과정의 반복으로 부분 나머지가 0 보다 크고 제수보다 적을 때

연산이 종료됩니다.

■ 종이와 연필 방법: 컴퓨터 구현

앞서 살펴본 나눗셈 100110 ÷ 101 (38 ÷ 5 = 7 ...3)을 컴퓨터로 구현할 경우에는

제수의 배수에 대한 뺄셈 연산하기 위하여 제수에 대한 자리 이동을 하지 않고,

반대로 제수는 그대로 둔 채 피제수를 반대 방향으로 자리 이동함으로써

다음과 같이 구현합니다.

제수 V 101 100110 피제수 D = R₄ Q = q₃ q₂ q₁ q₀
000 q₃ 2³ V 0
----------
100110 R₃
1001100 2 x R₃
101 q₂ 2³ V 01
----------
10010 R₂
100100 2 x R₂
101 q₁ 2³ V 011
----------
10000 R₁
100000 2 x R₁
101 q₀ 2³ V 0111
----------
011000 R₀ = 2³ R
나머지 = 011 몫 = 0111

■ 나눗셈 기본

• 부호 없는 다음의 수에 대한 나눗셈을 살펴봅시다.
  - 피제수(dividend): D
  - 제수(divisor): V
  - 몫(quotient): Q = q_n-1 q_n-2 ... q₁ q₀
  - 나머지(remainder): R
  
• 다음 조건을 만족하는 Q와 R을 찾으시오.
  
  - D = Q x V + R
  - 0 ≤ R < V
  
• 상기 조건을 이용하여 피제수(D = Q x V + R)를 다시 표현하면
  
  D = q_n-1 2^n-1 V + q_n-2 2^n-2 V + ... + q₀ 2⁰ V + R -------------------- (1)
  - 주어진 수: D, V
  - 주어진 범위: 모든 i 에 대하여 q_i = 0 혹은 1
  0 ≤ R < V
  
• q_i 가 0 혹은 1 이므로 식 (1)에서 q_n-1 도 0 혹은 1이다. q_n-1 이 1 이면 현재 자리에서 나누어진다는 의미이고 0 이면 현재 자리에서 나누어지지 않고 몫의 크기를 줄이는 자리 이동을 한 후에 다시 나누어 보아야 합니다. 즉,
  만약 D - 2^n-1 V >= 0 이면 q_n-1 = 1 이며
  
  D - 2^n-1 V = q_n-2 2^n-2 V + q_n-3 2^n-3 V + ... + q₀ 2⁰ V + R -------- (2)
  
  그렇지 않으면 q_n-1 = 0 이며
  
  D = q_n-2 2^n-2 V + q_n-3 2^n-3 V + ... + q₀ 2⁰ V + R --------------- (3)
  
• 이제 몫의 최상위 비트 값 q_n-1을 구했다. (2)의 결과든 (3)의 결과든 상관없이 각 식의 좌변을 새로운 피제수 D로 설정하고 동일한 과정을 반복하면 q_n-2, q_n-3, ..., q₀를 구할 수 있습니다.

■ 비트 연산을 이용한 곱셈 나눗셈

출처 - KLDP.org

 

/*+-------------------------------------------------------------------------+ 
  |  FILE: math.c                                                           | 
  |  Version: 0.1                                                           | 
  |  <math.c>                                                                       | 
  |  Copyright (c) 2003 Chun Joon Sung                                      | 
  |  Email: chunjoonsung@hanmail.net                                        | 
  +-------------------------------------------------------------------------+*/ 
long multiply(multiplicand, multiplier) 
long multiplicand; 
long multiplier; 
{ 
    long i=0, sign=0, sum=0; 

    if( multiplicand & (1<<31) ) 
    { 
        multiplicand = ~multiplicand + 1; 
        sign++; 
    } 
    if( multiplier & (1<<31) ) 
    { 
        multiplier = ~multiplier + 1; 
        sign++; 
    } 
    for(i=0, sum=0; i<32; i++) 
    { 
        if( (multiplier>>i) & 0x01 ) 
            sum += (multiplicand<<i); 
    } 
    if( sign & 0x01 ) 
    { 
        sum = ~sum + 1; 
    } 
    return sum; 
} 

long divide(dividend, divisor) 
long dividend; 
long divisor; 
{ 
    long i=0, sign=0, div=0, mod\0; 

    sign = 0; 
    if( dividend < 0 ) 
    { 
        dividend = ~dividend + 1; 
        sign++; 
    } 
    if( divisor < 0 ) 
    { 
        divisor = ~divisor + 1; 
        sign++; 
    } 
    if( dividend < divisor ) 
    { 
        div = 0; 
    } 
    else 
    { 
        for(i=0; i<32; i++) 
        { 
            if( dividend < (divisor<<i) ) 
            { 
                if( i > 0 ) i--; 
                break; 
            } 
            else if( dividend == (divisor<<i) ) 
            { 
                break; 
            } 
        } 

        div = 0; 
        for(; i>=0; i--) 
        { 
            if( dividend < divisor ) 
                break; 

            if( dividend >= (divisor<<i) ) 
            { 
                dividend -= (divisor<<i); 
                div      += (1<<i); 
            } 
        } 
    } 
    if( sign & 0x01 ) 
    { 
        div = ~div + 1; 
    } 
    return div; 
} 

long mod(dividend, divisor) 
long dividend; 
long divisor; 
{ 
    return (dividend - mul(divisor,div(dividend,divisor))); 
} 

[출처] 펌] 비트연산을 이용한 곱셈나눗셈|작성자 OzOn