algorithm - 给定 x=1000 位和 y=500 位的情况下，x+y 和 xy 是什么？

Question

给定 x=1000 位和 y=500 位，x+y 和 xy 的最长长度是多少？

仅供参考：x+y 和 750k 的答案不应该是 1500，这就是我感到困惑的原因:(

Answer 1

如果x的长度介于 0 和 1000 位之间，则x的值介于 0 和 2 ¹⁰⁰⁰ -1 之间。同样，0 ≤  y  < 2 ⁵⁰⁰。

所以，0 ≤  x  +  y  ≤ 2 ¹⁰⁰⁰  + 2 ⁵⁰⁰  − 2 < 2 ¹⁰⁰¹，所以x  +  y的长度最多为 1001。

同样， 0 ≤  xy  < 2 ¹⁵⁰⁰，xy的长度最多为 1500。

Answer 2

把它想象成给定一个 0-99 的数字，然后添加一个 0-9 的数字，您最多需要多少位数字？3 (2+1)。如果你有一个 0-9999 的数字并添加一个 0-99 的数字，你最多需要 5 个数字 (4+1)。注意它是最大数字的位数加一。所以答案是 1001。

Answer 3

答案取决于您要如何处理溢出（以及如何定义函数+和*）。

让我们采用符号var:bitwidth来表示变量具有位宽位。这意味着您有以下声明，

x:1000
y:500

此外，我们采用了这些以 bigendian 顺序存储的约定（最右边的位是最小的位，最左边的位是最大的位）。我们很快得出结论，x+y需要 1001 来处理溢出位，即

z0:1000, z1:1001
z0 = x + y //overflow possible, ex: x=2^1000-1, y=1
z1 = x + y //overflow not possible

乘法更难，考虑a:8, b:8，最宽的结果是什么？

a:8, b:8
a = 11111111b //= 255
b = 11111111b //= 255
a * b == 1111111000000001 //=65025
//16 bits

期望乘法所需的位数是位的总和似乎是合理的，除非您只想有一个溢出位用于乘法溢出。

x:1000, y:5000
z:1500
z2:1499
z = x * y //would not have overflow
z2 = x * y //could have overflow

综上所述，普通微处理器只使用较大的 ( :1000) 的宽度，或者丢弃溢出或设置溢出位。所以答案是:1000或:1000加号:1

Answer 4

考虑 2 位数字。在最坏的情况下，您可以获得：

11b + 11b = 110b 

所以 3 位就足够了，而不是 2 + 2。对于最多N需要ceil(log(N))位的数字（其中log表示带底的对数2）。因此，如果您最多有两个数字N并且最多M需要ceil(log(N+M))位。

对于乘法，考虑 3 位数字：

111b * 111b = 110001b

这就是为什么它也不是参数位数的简单乘法。与上面的乘法类似，您需要ceil(log(N*M))位。