使用字节数组和8位整数的模算法：8位 = 字节 % 8位。

Question

使用字节数组和8位整数的模算法：8位 = 字节 % 8位。

4

我需要创建一个用C语言实现的算法，用于在任意数量的字节和一个字节之间进行模算术运算。请参考以下内容:

typedef struct{
    u_int8_t * data;
    u_int16_t length;
}UBigInt;
u_int8_t UBigIntModuloWithUInt8(UBigInt a,u_int8_t b){

}

对于2的幂次方，可以使用a&(b-1)，但是对于非2的幂次方呢？

我知道一种方法是：a - b*(a/b)

这需要使用UBigIntDivisionWithUInt8、UBigIntMultiplicationWithUInt8和UBigIntSubtractionWithUBigInt。可能有更有效的方法来做到这一点吗？

谢谢。

这是我现在的实现：

u_int8_t UBigIntModuloWithUInt8(UBigInt a,u_int8_t b){
    if (!(b & (b - 1)))
        return a.data[a.length - 1] & b - 1; // For powers of two this can be done
    // Wasn't a power of two.
    u_int16_t result = 0; // Prevents overflow in calculations
    for(int x = 0; x < a.length; x++) {
        result *= (256 % b);
        result %= b;
        result += a.data[x] % b;
        result %= b;
    }
    return result;
}

- Matthew Mitchell

你说 a 是任意字节数；那么你能说出关于 b 的什么吗？它是常数吗？如果是，它的值是多少？ - violet313

OpenSSL似乎非常不错。我会试一试，可能会进行修改以删除不必要的部分，并确保它与我的库文档格式匹配，以便我可以将其包含在我的文档中。 - Matthew Mitchell

OpenSSL使用“unsigned int”而不是字节。由于C语言的内存块和数组应该是连续的（对吧），所以转换不是问题吧？ - Matthew Mitchell

@MatthewMitchell - 取决于转换的方向：你可以将(unsigned int*)强制转换为(char*)，但相反的操作可能会出现严重问题：指针对齐。此外，你可以尝试使用MPIR，它专门设计成易于使用并基于GMP。 - K.Steff

@MatthewMitchell 我觉得你缺少对 b=0 的检查（当 b = 0 时，!(b&(b-1)) 为真，所以你在除以 256），而且作为美观的特性，你可以将 b - 1 放在括号中。在我查看了 C 的运算符优先级表之前，这让我感到紧张。 - K.Steff

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- K.Steff · Accepted Answer

您可以使用Horner方法的变形。使用以下公式逐字节处理：a % b = ((a // 256) % b) * (256 % b) + (a % 256) % b，其中x // y是四舍五入除法（常规C整数除法）。之所以能够运作，是因为模b同余是等价关系。
使用这种方法，您将拥有一个O(length)算法，或O(log(a))。例如片段（未经测试，我的C技巧有点生疏）：

u_int16_t result = 0; // Just in case, to prevent overflow
for(i = 0, i<a.length; i++) {
    result *= (256 % b);
    result %= b;
    result += (a[i] % b);
    result %= b;
}

一些解释：由于 a = (a // 256) * 256 + (a % 256)，因此 a % b = ((a // 256) * 256) % b + ((a % 256) % b)。然而，a % 256 = a[n-1]，a // 256 = a[0 .. n-2]。以类似Horner's规则的方式反转操作，即可得到所示代码片段。