c - 如何在不使用 C 语言中的整数类型的情况下将 2 uint8 模乘一个大数

Question

<分区>

Answer 1

一般来说，没有简单的方法可以做到这一点。

首先，您需要为每个 uint8_t block 实现 A 和 B 之间的进位乘法。查看答案here .

用 2^16 划分实际上意味着“忽略”最后 16 位，“不要使用”最后两个 uint8_t(因为您使用 int 数组.).由于您有模数运算符，这意味着恰恰相反，因此您只需要获取最后两个 uint8_t。

取 A 的最低两个 uint8(比如 a0 和 a1)和 B(比如 b0 和 b1):

将每个uint8分成高低部分

a0h = a0 >> 4;    ## the same as a0h = a0/16;
a0l = a0 % 16;    ## the same as a0l = a0 & 0x0f;
a1h = a1 >> 4;
a1l = a1 % 16;

b0h = b0 >> 4;
b0l = b0 % 16;
b1h = b1 >> 4;
b1l = b1 % 16;

首先将较低的部分相乘(x 是一个缓冲区变量)

x = a0l * b0l;

结果的第一部分是x的后四位，我们称它为s0l

s0l = x % 16;  

x 的最高位是进位。

c = x>>4;   

将第一个 uint8 的高位相乘并加进位。

x = (a0h * b0h) + c;

结果的第一部分是x的后四位，我们称它为s0h。我们需要再次携带。

s0h = x % 16;
c = x>>4;

我们现在可以合并 s0:

s0 = (s0h << 4) +  s0l;

对 s1 执行完全相同的操作(但不要忘记添加进位!):

x = (a1l * b1l) + c;
s1l = x % 16;
c = x>>4;
x = (a1h * b1h) + c;
s1h = x % 16;
c = x>>4;
s1 = (s1h << 4) +  s1l;

此时您的结果是c、s1 和s0(下一次乘法需要进位，例如。s2, s3, s4,)。正如你的公式所说的 %(2^16) 你已经有了你的结果 - s1 和 s2。如果你必须用别的东西除法，你应该做类似于上面代码的事情，但除法。在这种情况下，小心捕捉除以零，它会给你 NAN 或其他东西!

您可以将 A、B、C 和 S 放入数组中并通过索引对其进行循环以使代码更简洁。