산술 연산자없이 비트 나누기 수행

Question

이진 산술을 위해 세 가지 함수를 작성해야하는 과제를 완료하려고합니다. badd()가 제공되었으므로 bsub() 및 bmult() 함수를 작성하는 데 사용했습니다. 그러나 bdiv() 함수를 어떻게 수행해야하는지 이해하는 데 문제가 있습니다. 나는 비트를 통해 오른쪽 시프트와 bsubb() 함수를 사용하여 반복 할 필요가 있음을 알고 있지만 구현 방법을 모른다. 아래는 지금까지 작성한 함수입니다. 내가 작성한 실수 (bsub()와 bmult())를 발견하면 알려주십시오. 감사. 배당 < 제수 몫 에서 소수점 제로를 추가 한

의해 오른쪽 배당 시프트

/** This function adds the two arguments using bitwise operators. Your  
* implementation should not use arithmetic operators except for loop 
* control. Integers are 32 bits long. This function prints a message 
* saying "Overflow occurred\n" if a two's complement overflow occurs 
* during the addition process. The sum is returned as the value of 
* the function. 
*/ 
int badd(int x,int y){ 

int i; 

char sum; 
char car_in=0; 
char car_out; 
char a,b; 

unsigned int mask=0x00000001; 
int result=0; 

for(i=0;i<32;i++){ 

    a=(x&mask)!=0; 
    b=(y&mask)!=0; 
    car_out=car_in & (a|b) |a&b; 
    sum=a^b^car_in; 

    if(sum) { 
    result|=mask; 
    } 

    if(i!=31) { 
    car_in=car_out; 
    } else { 
    if(car_in!=car_out) { 
printf("Overflow occurred\n"); 
    } 
    } 

    mask<<=1; 
} 

return result; 
} 

// subracts two integers by finding the compliemnt 
// of "y", adding 1, and using the badd() function 
// to add "-y" and "x" 
int bsub(int x, int y){ 

return badd(x, badd(~y, 1)); 
} 


//add x to total for however many y 
int bmult(int x,int y){ 

int total; 
int i; 
for(i=0; i < = y; i++) 
{ 
total = badd(total,x) 
} 
return total; 
} 

// comment me 
unsigned int bdiv(unsigned int dividend, unsigned int divisor){ 

// write me 
return 0; 
} 

Answer 1

1. 하면서 제수의 비트 수 배당 경우의 비트 수와 동일한 경우에 현재 검사 배수의 비트 수가 제수의 비트 수와 같을 때까지 시프트 제수를 남겨 둡니다.
2. 이제 (소수점 위치와 마찬가지로) 적절한 장소에서 지수에 1을 갖추고 있는지 확인하십시오,

배당까지 과정이 반복 0 또는 1

Answer 2

을 배당, 제수 을 빼고 지수에 1을 추가

많은 여기선 말, 그것은 기본-2 단지 몇 가지 기본적인 수학의 :

unsigned int bmult(unsigned int x, unsigned int y) 
{ 
    int total = 0; 
    int i; 

    /* if the i-th bit is non-zero, add 'x' to total */ 
    /* Multiple total by 2 each step */ 
    for(i = 32 ; i >= 0 ; i--) 
    { 
     total <<= 1; 
     if((y & (1 << i)) >> i) 
     { 
      total = badd(total, x); 
     } 
    } 

    return total; 
} 

unsigned int bdiv(unsigned int dividend, unsigned int divisor) 
{ 
    int i, quotient = 0, remainder = 0; 

    if(divisor == 0) { printf("div by zero\n"); return 0; } 

    for(i = 31 ; i >= 0 ; i--) 
    { 
     quotient <<= 1; 
     remainder <<= 1; 
     remainder |= (dividend & (1 << i)) >> i; 

     if(remainder >= divisor) 
     { 
      remainder = bsub(remainder, divisor); 
      quotient |= 1; 
     } 
    } 

    return quotient; 
} 

이 두 기사는 이러한 샘플 코드에 충분 : Div 및 Mul.

Answer 3

다음 코드에서는 질문과 같은 생각을 사용하여 더하기와 빼기를 구현합니다. 실제적인 차이점은 내 구현에서이 두 함수는 carry-in/borrow-in 비트를 가져 와서 carry-out/borrow-out 비트를 생성한다는 것입니다.

carry-in 비트는 덧셈을 통해 빼기를 구현하는 데 사용되며이 비트는 carry-out 및 borrow-out 비트의 올바른 값을 얻는 데 도움이됩니다. 기본적으로 상태 레지스터에 캐리 플래그가있는 전형적인 CPU와 같은 덧셈과 뺄셈을 구현합니다.

carry/borrow 비트는 뺄셈을 통해 비교를 구현하는 데 사용됩니다. 나는 비트가 현명한 성격이 아니기 때문에 산술을 고려한 >= 연산자를 사용하지 않고 비교를 구현합니다. 비교 함수는 restoring division algorithm을 사용하기 때문에 나누기 함수에서 필요합니다.

나는 ! 연산자를 사용하지 않고 대신 ^1을 사용합니다.

나누기 함수는 제수가 2 unsigned ints이며, 가장 큰 부분과 가장 중요하지 않은 부분입니다. 마지막에는 가장 중요한 부분을 나머지와 가장 중요한 부분으로 바꿉니다. 따라서, 그것은 나눗셈과 모듈로를 모두 수행하고 일반적인 CPU와 비슷한 방식으로 수행합니다 (예 : x86 DIV 명령어와 같이). 이 함수는 성공시 1을 반환하고 오버 플로우/나눗셈이 0 인 경우 0을 반환합니다.

주 기능은 간단한 테스트를 수행합니다. 이 함수는 나누기 함수의 결과를 직접 나누기의 결과와 비교하고 불일치하는 오류 메시지와 함께 종료합니다.

테스트 부분에 unsigned long long을 사용하면 무한 루프에 빠지지 않고 제수 = UINT_MAX을 테스트 할 수 있습니다.배당금과 제수의 전체 범위를 테스트하는 데 너무 많은 시간이 걸릴 수 있습니다. 따라서 나는 UINT_MAX 대신 0xFFFF와 0xFF를 각각 캡핑합니다.

코드 : 당신은 ([이 간단한 방정식을 해결하기에 의해, 몫과 알림을 모두 계산 곱셈과 뺄셈을 결합해야처럼

#include <stdio.h> 
#include <limits.h> 

unsigned add(unsigned a, unsigned b, unsigned carryIn, unsigned* carryOut) 
{ 
    unsigned sum = a^b^carryIn; 
    unsigned carryOuts = a & b | (a | b) & carryIn; 
    *carryOut = 0; 
    if (sum & (carryOuts << 1)) 
    sum = add(sum, carryOuts << 1, 0, carryOut); 
    else 
    sum |= carryOuts << 1; 
    *carryOut |= (carryOuts & (UINT_MAX/2 + 1)) >> (sizeof(unsigned) * CHAR_BIT - 1); // +-*/ are OK in constants 
    return sum; 
} 

unsigned sub(unsigned a, unsigned b, unsigned borrowIn, unsigned* borrowOut) 
{ 
    unsigned diff = add(a, ~b, borrowIn^1, borrowOut); 
    *borrowOut ^= 1; 
    return diff; 
} 

unsigned less(unsigned a, unsigned b) 
{ 
    unsigned borrowOut; 
    sub(a, b, 0, &borrowOut); 
    return borrowOut; 
} 

int udiv(unsigned* dividendh, unsigned* dividendl, unsigned divisor) 
{ 
    int i; 
    unsigned tmp; 

    if (less(*dividendh, divisor)^1/* *dividendh >= divisor */) 
    return 0; // overflow 

    for (i = 0; i < sizeof(unsigned) * CHAR_BIT; i++) 
    { 
    if (less(*dividendh, UINT_MAX/2 + 1)^1/* *dividendh >= 0x80...00 */) 
    { 
     *dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1)); 
     *dividendl <<= 1; 

     *dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */ 
     *dividendl |= 1; 
    } 
    else 
    { 
     *dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1)); 
     *dividendl <<= 1; 

     if (less(*dividendh, divisor)^1/* *dividendh >= divisor */) 
     { 
     *dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */ 
     *dividendl |= 1; 
     } 
    } 
    } 

    return 1; 
} 

int udiv2(unsigned* dividendh, unsigned* dividendl, unsigned divisor) 
{ 
    unsigned long long dividend = 
    ((unsigned long long)*dividendh << (sizeof(unsigned) * CHAR_BIT)) | *dividendl; 

    if (*dividendh >= divisor) 
    return 0; // overflow 

    *dividendl = (unsigned)(dividend/divisor); 
    *dividendh = (unsigned)(dividend % divisor); 

    return 1; 
} 


int main(void) 
{ 
    unsigned long long dividend, divisor; 

    for (dividend = 0; dividend <= /*UINT_MAX*/0xFFFF; dividend++) 
    for (divisor = 0; divisor <= /*UINT_MAX*/0xFF; divisor++) 
    { 
     unsigned divh = 0, divl = (unsigned)dividend, divr = (unsigned)divisor; 
     unsigned divh2 = 0, divl2 = (unsigned)dividend; 

     printf("0x%08X/0x%08X=", divl, divr); 

     if (udiv(&divh, &divl, divr)) 
     printf("0x%08X.0x%08X", divl, divh); 
     else 
     printf("ovf"); 

     printf(" "); 

     if (udiv2(&divh2, &divl2, divr)) 
     printf("0x%08X.0x%08X", divl2, divh2); 
     else 
     printf("ovf"); 

     if ((divl != divl2) || (divh != divh2)) 
     { 
     printf(" err"); 
     return -1; 
     } 

     printf("\n"); 
    } 

    return 0; 
}