본문 바로가기
카테고리 없음

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

by Luyin 2012. 5. 8.

■ 종이와 연필 방법

  • 보기: 100110 ÷ 101 (38 ÷ 5 = 7 ...3)

    0111 몫 Q = q3 q2 q1 q0
    +---------
    제수 V 101 | 100110 피제수 D = R
    4
    000 q
    3 23 V
    ----------
    100110 R
    3
    101 q
    2 22 V
    ----------
    10010 R
    2
    101 q
    1 21 V
    ----------
    1000 R
    1
    101 q
    0 20 V
    ----------
    011 R
    0 = 나머지

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

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

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

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

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

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

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

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

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

연산이 종료됩니다.

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

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

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

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

다음과 같이 구현합니다.

제수 V 101 100110 피제수 D = R4 Q = q3 q2 q1 q0
000 q
3 23 V 0
----------
100110 R
3
1001100 2 x R3
101 q
2 23 V 01
----------
10010 R
2
100100 2 x R
2
101 q
1 23 V 011
----------
10000 R
1
100000 2 x R
1
101 q
0 23 V 0111
----------
011000 R0 = 23 R
나머지 = 011 몫 = 0111

■ 나눗셈 기본

  • 부호 없는 다음의 수에 대한 나눗셈을 살펴봅시다.
    - 피제수(dividend):
    D
    - 제수(divisor):
    V
    - 몫(quotient):
    Q = qn-1 qn-2 ... q1 q0
    - 나머지(remainder):
    R
  • 다음 조건을 만족하는 QR을 찾으시오.

    - D = Q x V + R
    - 0 ≤ R < V

  • 상기 조건을 이용하여 피제수(D = Q x V + R)를 다시 표현하면

    D = qn-1 2n-1 V + qn-2 2n-2 V + ... + q0 20 V + R -------------------- (1)
    - 주어진 수:
    D, V
    - 주어진 범위: 모든 i 에 대하여
    qi = 0 혹은 1
    0 ≤ R < V
  • qi 0 혹은 1 이므로 식 (1)에서 qn-10 혹은 1이다. qn-11 이면 현재 자리에서 나누어진다는 의미이고 0 이면 현재 자리에서 나누어지지 않고 몫의 크기를 줄이는 자리 이동을 한 후에 다시 나누어 보아야 합니다. 즉,
    만약
    D - 2n-1 V >= 0 이면 qn-1 = 1 이며

    D - 2n-1 V = qn-2 2n-2 V + qn-3 2n-3 V + ... + q0 20 V + R -------- (2)

    그렇지 않으면
    qn-1 = 0 이며

    D = qn-2 2n-2 V + qn-3 2n-3 V + ... + q0 20 V + R --------------- (3)
  • 이제 몫의 최상위 비트 값 qn-1을 구했다. (2)의 결과든 (3)의 결과든 상관없이 각 식의 좌변을 새로운 피제수 D로 설정하고 동일한 과정을 반복하면 qn-2, qn-3, ..., q0를 구할 수 있습니다.



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


출처 - 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)));