如果两个n位数相乘,则结果将是最大位长

Question

我想知道如果有两个n位二进制数相乘,是否有任何公式或方法可以找出更多的最大位.我搜索了很多,但无法在任何地方找到答案.

Answer 1

可以使用示例简单地得出结论:

11*11(因为11是最大2位数)= 1001(4位)

111*111 = 110001(6位)

1111*1111 = 11100001(8位)

11111*11111 = 1111000001(10位)

从上面我们可以看到你的答案是2*n

Answer 2

表示数字N所需的基数B中的位数是floor(log_B(N)+1).对数有一个很好的属性log(X*Y)= log(X)+ log(Y),它暗示X*Y的位数大致是表示X和Y的位数之和.

Answer 3

考虑这一点的最简单方法是考虑产品的最大值,这是在我们使用两个被乘数中的最大值时获得的.

如果value x是n位数,则最多为2 ^ n - 1.想想看,2 ^ n需要一个后跟n个零.

因此,两个n位数的最大可能乘积将是:

(2 ^ n - 1)^ 2 = 2 ^(2n) - 2 ^(n + 1)+ 1

现在n = 1是一种特殊情况,因为1*1 = 1再次是一位数.但是通常我们看到最大乘积是2n位数,只要n> 1.例如,如果n = 3,则最大被乘数为x=7,而正方形49为6位数.