我想知道如果两个 n 位二进制数相乘，是否有任何公式或方法可以找出最大位数。我为此搜索了很多，但无法在任何地方找到答案。
user2776916
问问题
36854 次
5 回答
13
表示数字 N 所需的底数 B 的位数是 floor(log_B(N)+1)。对数有一个很好的性质，即 log(X*Y)=log(X)+log(Y)，这表明 X*Y 的位数大致是表示 X 和 Y 的位数的总和。
于 2013-09-13T16:04:04.373 回答
10
可以通过示例简单地得出结论：
11*11（因为 11 是最大的 2 位数字）=1001（4 位）
111*111=110001（6位）
1111*1111=11100001(8位)
11111*11111=1111000001(10位)
所以从上面我们可以看到你的答案是 2*n
于 2013-09-13T15:31:26.983 回答
8
考虑这一点的最简单方法是考虑乘积的最大值，当我们使用两个被乘数中的最大值时，就会得到最大值。
如果 valuex是 n 位数，则最多为 2^n - 1。想想看，2^n 需要一个 1 后跟 n 个零。
因此，两个 n 位数的最大可能乘积将是：
(2^n - 1)^2 = 2^(2n) - 2^(n+1) + 1
现在 n=1 是一种特殊情况，因为 1*1 = 1 又是一个一位数。但通常我们看到，当 n > 1 时，最大乘积是一个 2n 位数。例如，如果 n=3，最大被乘数是x=7，平方 49 是一个六位数。
于 2013-09-13T15:32:41.160 回答
4
值得注意的是，位置系统的基础并不重要。无论你想出的十进制乘法公式都适用于二进制乘法。
让我们应用一点推论并乘以两个具有相对质数位数的数字：分别为 2 位和 3 位。
可能的最小数字：
10 * 100 = 1000 有 4 位数字
可能的最大数字：
99 * 999 = 98901 有 5 位数字
因此，对于 n 位数乘以 m 位数的数，我们推导出上限和下限分别为n+m和n+m-1位数。让我们确保它也适用于二进制：
10 * 100 = 1000 有 4 位数字
11 * 111 = 10101 有 5 位数字
所以，它确实适用于二进制，我们可以期望它适用于任何基础。
于 2013-09-13T15:34:39.243 回答
3
x 有 n 个二进制数字意味着 2^(n-1) <= x < 2^n，也假设 y 有 m 个二进制数字。这意味着：
2^(m+n-2)<=x*y<2^(m+n)
所以 x*y 可以有 m+n-1 或 m+n 位。很容易构建两种情况都可能的示例：
- m+n-1：2*2 有 3 个二进制数（m = n = 2）
- m+n: 7*7=49=(binary)110001 有 6 个二进制位，m = n = 3
于 2013-09-13T15:28:10.597 回答