符号なし8ビット整数のビンジュム除算。 C

Question

私は、最大255バイトの整数を8ビット整数で除算するためのアルゴリズムを作成しました。誰か、それについてのコメントや改善提案はありますか？この目的のためのより良いアルゴリズムはありますか？私はbignum除算アルゴリズムによってbignumを望んでいない、2番目の整数は8ビットの整数です。それはで動作します

：

ベスト今のところ解決策（小エンディアン）：ビッグエンディアンと

typedef struct{ 
    u_int8_t * data; 
    u_int8_t length; 
}CBBigInt; 
void CBBigIntEqualsDivisionByUInt8(CBBigInt * a,u_int8_t b,u_int8_t * ans){ 
    // base-256 long division. 
    u_int16_t temp = 0; 
    for (u_int8_t x = a->length-1;; x--) { 
     temp <<= 8; 
     temp |= a->data[x]; 
     ans[x] = temp/b; 
     temp -= ans[x] * b; 
     if (!x) 
      break; 
    } 
    a->length -= ans[a->length-1]? 0 : 1; // If last byte is zero, adjust length. 
    memmove(a->data, ans, a->length); // Done calculation. Move ans to "a". 
} 

旧ソリューション除数が2の累乗である場合

1. 、ん右にビットシフト。
2. これを除いて、被除数よりも大きくなる前に除数を左シフトする必要があり、16ビット整数を左にシフトしたように除数にする必要があります。これは減算に使用されます。
3. 答えにシフト量に対応するビットを設定します。行われたことは、被除数が2の累乗に至るまで除数に収まる金額が見つかったことです。
4. 余りを作成するために被除数からシフトされたバイトを削除します。
5. 除数が残りよりも大きくなるまで、残りは手順2を繰り返します。これが起こると、答えが見つかる。

---

typedef struct{ 
    u_int8_t * data; 
    u_int8_t length; 
}CBBigInt; 
u_int8_t CBPowerOf2Log2(u_int8_t a){ 
    switch (a) { 
     case 1: 
      return 0; 
     case 2: 
      return 1; 
     case 4: 
      return 2; 
     case 8: 
      return 3; 
     case 16: 
      return 4; 
     case 32: 
      return 5; 
     case 64: 
      return 6; 
    } 
    return 7; 
} 
u_int8_t CBFloorLog2(u_int8_t a){ 
    if (a < 16){ 
     if (a < 4) { 
      if (a == 1){ 
       return 0; 
      } 
      return 1; 
     } 
     if (a < 8){ 
      return 2; 
     } 
     return 3; 
    } 
    if (a < 64){ 
     if (a < 32) { 
      return 4; 
     } 
     return 5; 
    } 
    if (a < 128){ 
     return 6; 
    } 
    return 7; 
} 
void CBBigIntEqualsRightShiftByUInt8(CBBigInt * a,u_int8_t b){ 
    u_int8_t deadBytes = b/8; // These bytes fall off the side. 
    a->length -= deadBytes; // Reduce length of bignum by the removed bytes 
    u_int8_t remainderShift = b % 8; 
    if (!remainderShift) { // No more work 
     return; 
    } 
    u_int16_t splitter; 
    u_int8_t toRight = 0; // Bits taken from the left to the next byte. 
    for (u_int8_t x = 0; x < a->length; x++) { 
     splitter = a->data[x] << 8 - remainderShift; // Splits data in splitters between first and second byte. 
     a->data[x] = splitter >> 8; // First byte in splitter is the new data. 
     a->data[x] |= toRight; // Take the bits from the left 
     toRight = splitter; // Second byte is the data going to the right from this byte. 
    } 
} 
void CBBigIntEqualsDivisionByUInt8(CBBigInt * a,u_int8_t b,u_int8_t * ans){ 
    if (!(b & (b - 1))){ 
     // For powers of two, division can be done through bit shifts. 
     CBBigIntEqualsRightShiftByUInt8(a,CBPowerOf2Log2(b)); 
     return; 
    } 
    // Determine how many times b will fit into a as a power of two and repeat for the remainders 
    u_int8_t begin = 0; // Begining of CBBigInt in calculations 
    bool continuing = true; 
    u_int8_t leftMost; 
    bool first = true; 
    while (continuing){ 
     // How much does b have to be shifted by before it becomes larger than a? Complete the shift into a shiftedByte 
     int16_t shiftAmount; 
     u_int16_t shiftedByte; 
     if (a->data[begin] > b){ 
      shiftAmount = CBFloorLog2(a->data[begin]/b); 
      shiftedByte = b << 8 + shiftAmount; 
     }else if (a->data[begin] < b){ 
      shiftAmount = -CBFloorLog2(b/a->data[begin]); 
      shiftedByte = b << 8 + shiftAmount; 
      // Shift right once again if "shiftedByte > (a->data[begin] << 8) + a->data[begin+1]" as the shifted divisor should be smaller 
      if (shiftedByte > ((a->data[begin] << 8) + a->data[begin+1])){ 
       shiftedByte >>= 1; 
       shiftAmount--; // Do not forget about changing "shiftAmount" for calculations 
      } 
     }else{ 
      shiftAmount = 0; 
      shiftedByte = b << 8; 
     } 
     // Set bit on "ans" 
     if (shiftAmount < 0){ // If "shiftAmount" is negative then the byte moves right. 
      ans[begin+1] |= 1 << (8 + shiftAmount); 
      if (first) leftMost = 1; 
     }else{ 
      ans[begin] |= 1 << shiftAmount; // No movement to right byte, jsut shift bit into place. 
      if (first) leftMost = 0; 
     } 
     first = false; // Do not set "leftMost" from here on 
     // Take away the shifted byte to give the remainder 
     u_int16_t sub = (a->data[begin] << 8) + a->data[begin+1] - shiftedByte; 
     a->data[begin] = sub >> 8; 
     if (begin != a->length - 1) 
      a->data[begin + 1] = sub; // Move second byte into next data byte if exists. 
     // Move along "begin" to byte with more data 
     for (u_int8_t x = begin;; x++){ 
      if (a->data[x]){ 
       if (x == a->length - 1) 
        // Last byte 
        if (a->data[x] < b){ 
         // b can fit no more 
         continuing = false; 
         break; 
        } 
       begin = x; 
       break; 
      } 
      if (x == a->length - 1){ 
       continuing = false; // No more data 
       break; 
      } 
     } 
    } 
    a->length -= leftMost; // If the first bit was onto the 2nd byte then the length is less one 
    memmove(a->data, ans + leftMost, a->length); // Done calculation. Move ans to "a". 
} 

ありがとう！

Answer 1

これを「ベース2ロングディビジョン」と表現します。より良い選択肢は、 "base 256 long division"です。エヘンLOL

typedef struct{ 
    u_int8_t * data; 
    u_int8_t length; 
} CBBigInt; 


u_int8_t CBBigIntEqualsDivisionByUInt8(CBBigInt * a, u_int8_t b, u_int8_t * ans) { 
    int i; 
    unsigned int temp = 0; 

    i = a.length; 
    while(i > 0) { 
     i--; 
     temp <<= 8; 
     temp |= a.data[i]; 
     ans.data[i] = temp/b; 
     temp -= ans.data[i] * b; 
    } 
    return temp; // Return remainder 
}