Bignum除法与无符号8位整数。 C

我已经创建了一个算法，用于将整数最大为255字节的整数除以8位整数，并且它可以用于我已经完成的测试。 有没有人对此有任何意见或任何改进建议？ 有没有更好的算法用于此目的？ 我不希望bignum通过bignum除法算法，第二个整数是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 <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". } 

大端的旧解决方案：

它的工作原理是：

1. 如果除数是2的幂，请向右移一点。
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 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 length; x++) { splitter = a->data[x] <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 <data[begin] data[begin]); shiftedByte = b < (a->data[begin] <data[begin+1]" as the shifted divisor should be smaller if (shiftedByte > ((a->data[begin] <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 <data[begin] <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] 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”。

这是一个（未经测试的，可能是错误的）示例：

 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 }