gpt4 book ai didi

c - 无符号 8 位整数的 Bignum 除法。 C

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:03:44 33 4
gpt4 key购买 nike

我创建了一个算法,用于将最大 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 <<= 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".
}

大端的旧解决方案:

它的工作原理是:

  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 < 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".
}

谢谢!

最佳答案

我将其描述为“base 2 long division”。更好的选择是“base 256 长除法”。

这是一个(未经测试且可能有错误的)示例:

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
}

关于c - 无符号 8 位整数的 Bignum 除法。 C,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10522379/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com