無算術運算符執行位分割

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. 而被除數<除數 在商數 小數點後添加零，並通過1
2. 右移股息現在檢查如果在除數位的數目是在股息 如果等於比特數不是，移位除數直到被除數中的位數等於除數中的位數。
3. 現在扣除被除數，除數 並添加1至商，請確保您有1到正確的地方的商（像小數點位置）

重複上述過程，直到紅利爲0或1

Answer 2

這裏就不多說了，這只是一些基本的數學中基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

在下面的代碼中，我使用與問題中相同的想法實現加法和減法。唯一實際的區別是在我的實現中，這兩個函數還會帶入一個進位/借入位併產生一個進位/借位位。

進位位用於通過加法實現減法，該位有助於獲得進位和退出位的正確值。基本上，我用狀態寄存器中的進位標誌來實現典型的類CPU加法和減法。

進位/借位位然後用於通過減法來實現比較。我在沒有>=算子的情況下執行比較，我也認爲算術算術，因爲它不太具有比特性。由於使用了restoring division algorithm，所以在除法功能中需要比較功能。

我也避免使用!運營商和使用^1來代替。

除法函數將除數作爲2 unsigned ints，它是最重要和最不重要的部分。最後，它將最重要的部分替換爲剩餘部分，將最不重要的部分替換爲商。因此，它可以進行除法和模運算，並以類似CPU的方式執行它們（例如，像x86 DIV指令）。該函數成功時返回1，溢出/除法時返回0.

主函數做了一個簡單的測試。它將劃分功能的結果與直接劃分的結果進行比較，並以不匹配的錯誤消息結束。

我在測試部分使用unsigned long long可以測試除數= UINT_MAX而不會陷入無限循環。測試分紅和除數的整個範圍值可能需要很長時間，這就是爲什麼我分別將它們限制在0xFFFF和0xFF而不是UINT_MAX。

代碼：

#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; 
}