2

我遇到了一个在 URL 查询字符串中使用 50 位十进制整数 ID 的网站，这似乎有点过分。

最小的 50 位十进制数是1.0 x 10^49，也称为：

1000000000
0000000000
0000000000
0000000000
0000000000
  1. 二进制表示包含多少位？
  2. 考虑到无符号 32 位整数或 64 位整数的范围限制，您将如何将如此大的十进制数转换为二进制数？

我只是出于纯粹的程序员好奇心而问——这不是大学问题、工作问题或面试难题！

4

8 回答 8

8

通过取数字的对数（以 2 为底）可以找到最小二进制表示（具有整数精度）。在这种情况下，二进制位的最小数量为 log(10^49) = 162.77。我们需要一个整数，所以我们只称它为 163 位。

如果我必须表示那个数字，并且浮点表示的精度不够，我会使用一些BigInteger库。

于 2009-07-15T08:36:48.623 回答
7

  1. 49 * log(10) / log(2) = 162.774477，所以二进制表示将包含 163 位。

  2. 使用 bigint 类并应用标准算法将十进制转换为二进制。

于 2009-07-15T08:37:52.130 回答
4

由于每个十进制数字都传达与位相同的信息lb 10，因此任何 50 位数字都适合ceil(lb(10)*50) = 167位。

具体来说，即使手动将十进制转换为二进制也不难。只需除以二，然后将模数（如果最后一位为奇数，则为 1，如果为偶数，则为 0）放在二进制结果的末尾。如果您在程序中需要如此高的数字，只需使用您平台的大整数实现，例如BigInteger在 Java 中和仅int在 python 中。如果没有，请寻找一个数字库。

哦，二进制的 10^49 是 163 位长：

110
1101 0111 1001 1111 1000 0010 0011 0010
1000 1110 1010 0011 1101 1010 0110 0001
1110 0000 0110 0110 1110 1011 1011 0010
1111 1000 1000 1010 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
于 2009-07-15T08:33:44.823 回答
1

可以使用合适的长整数操作库来转换这些数字。如果不允许使用，则阅读源代码可以提供有关如何有效完成此类事情的有用知识。

关于位数，您只需要解方程：

2 N = 10 50

取两个部分的 log 2 ：

N = 对数2 10 50

现在将 log 2转换为 log 10：

N = log 2 10 50 = log 10 10 50 /log 10 2 = 50 / log 10 2

取 N 的下一个整数 (ceil) - 这就是所需的位数。

于 2009-07-15T08:38:09.463 回答
0

1) 2^10 ~ 10^3 所以 10^48 ~ 2^160; 10^49 将是 164 位的数量。

2) 使用 BigInteger 或 MPI 类（如果您的语言标准 API 库没有提供这些类，则可以找到很多）。Knuth 有详细信息。

于 2009-07-15T08:34:12.543 回答
0

存储数字 X 到底是什么意思？

  1. 你的意思是存储0到X之间的所有数字吗？
  2. 或者 -X 和 X 之间的所有数字？
  3. 或者只存储信息：null / X。

我的直觉是面试官可能指的是第三个。答案是 1 位。

于 2009-07-15T08:38:20.570 回答
0

我会使用一种高级语言来为我处理大整数。示例 irb (Ruby) 会话：

>> (10**49).to_s
=> "10000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2)
=> "1101101011110011111100000100011001010001110101000111101101001100001111000000110011011101011101100101111100010001010000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2).size
=> 163
于 2009-07-15T08:40:20.643 回答
0

50 位十进制整数的范围从 10^49 到 10^50-1。10^49 是 163 位，10^50-1 是 167 位。如果您想要确切的位数，则需要直接取这些大数的对数，而不是仅计算“快捷方式” 50*log 10 (2)。

作为替代方案，您可以使用任意精度的十进制二进制转换器将数字转换为二进制并计算位数（顺便说一句，我链接到的转换器会为您计算位数）。

于 2009-07-15T12:27:10.080 回答