如何在 C++ 中打印非常大的数字

发布于 2024-07-07 14:47:15 字数 5660 浏览 15 评论 0原文

我有这段代码，

#include <iostream>

using namespace std;

int main(int argc,char **argv) {

    unsigned long long num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995LL;
    unsigned long long num2 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996LL;
    unsigned long long num3 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997LL;
    unsigned long long num4 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998LL;
    unsigned long long num5 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999LL;

    cout << (unsigned long long)(num1 * num2 * num3 * num4 * num5) << endl;
    return 0;
}

正如你所看到的，数字是巨大的，但是当我在那里进行数学计算时，我得到了这个： 18446744073709551496

在编译时我收到以下警告：

warning: integer constant is too large for its type|
In function `int main(int, char**)':|
warning: this decimal constant is unsigned only in ISO C90|
...

原文

I have this code

#include <iostream>

using namespace std;

int main(int argc,char **argv) {

    unsigned long long num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995LL;
    unsigned long long num2 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996LL;
    unsigned long long num3 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997LL;
    unsigned long long num4 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998LL;
    unsigned long long num5 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999LL;

    cout << (unsigned long long)(num1 * num2 * num3 * num4 * num5) << endl;
    return 0;
}

As you can see the numbers are enormous, but when I do the math there I get this:
18446744073709551496

At compile time I get these warnings:

warning: integer constant is too large for its type|
In function `int main(int, char**)':|
warning: this decimal constant is unsigned only in ISO C90|
...

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

余生再见 2024-07-14 14:47:15

您的结果大于 long long 类型 - 您需要查看 BigInteger 或任意精度库，例如gmp

回复收藏 0 原文

苦笑流年记忆 2024-07-14 14:47:15

这些数字不适合任何 C++ 数据类型。如果您只想打印它们，请将数字存储在字符串中。如果您想对其进行数学计算，请找到一个任意精度的数学库并使用它。

回复收藏 0 原文

潜移默化 2024-07-14 14:47:15

如果您希望代码中的文字这么大，则必须将它们作为字符串文字输入并将它们加载到某种 BigInt 类中。现在没有办法在源代码中表达那么大的整数文字（尽管 C++0x 希望能够解决这个缺陷）。

如果您使用的是 BigInteger 库，请查看 stringToBigUnsigned 函数在 BigIntegerUtils.hh 中，用于从字符串构建大整数。

#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"     

 BigUnsigned  num1 = stringToBigUnsigned (
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999995"
    );

If you want literals this big in your code, you'll have to enter them as string literals and load them into a BigInt class of some sort. There's no way to express integer literals that big in source code right now (although C++0x will hopefully address that shortfall).

If you're using the BigInteger library, take a look at the stringToBigUnsigned function in BigIntegerUtils.hh for building a big integer from a string.

#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"     

 BigUnsigned  num1 = stringToBigUnsigned (
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999995"
    );

回复收藏 0 原文

土豪 2024-07-14 14:47:15

你想做什么？您了解二进制和十进制数的基础知识吗？为什么 8 位只能保存值 0 到 255，12 位只能保存值 0 - 4095 等？需要多少位来保存您感兴趣的数字？或者更好的是，您有兴趣创建多大的数字？您是否使用 9 来使数字更大？那么十六进制 0xF... 呢？如果您想要最大的无符号数（在标准整数类型之一内）为什么不：

unsigned long long a,b;

a = -1; //这似乎是错误的混合有符号和无符号，但它是有效的，数字在存储之前转换为无符号

b = 0; b——； //与上面做同样的事情

你真的需要那个级别的精度吗？您是否意识到乘法可能需要每个操作数大小两倍的结果？ 0xFF * 0xFF = 0xFE01，如果在这种情况下您使用的是 8 位整数，则无法进行数学计算。当您继续乘以 0xFF * 0xFF * 0xFF = 0xFD02FF 时，情况只会变得更糟。

正在努力做什么？

看到你的回复：

我以前没见过欧拉8号。听起来是一个很好的面试问题，因为只需要几行代码就可以解决。

您的其他回答：

数字...

可能是因为我们有 10 个手指（也许还有 10 个脚趾），所以我们从小就以“10 为基数”长大。我们的时钟大部分以 60 为基数，但它与 10 基数混合在一起，使其更加混乱。无论如何，基数 10 意味着对于每个数字占位符，您有 10 个唯一数字之一，当您达到该位置的最大值时，您将滚动到下一个位置。这都是小学的东西了。

000
001
002
003
...
008
009
010
011
012
...

看看最右边的数字如何有 10 个符号 (0,1,2,3,4,5,6,7,8,9)，当到达最后一个符号时，它会重新开始，左边的符号是它增加一。此规则适用于所有基本编号系统。

对于基数 2 也是如此，只不过只有两个符号：0 和 1

000
001
010
011
100
101
...

八进制也是如此，但是 8 个符号 (0,1,2,3,4,5,6,7)

000
001
002
003
004
005
006
007
010
011
012
013
...

十六进制也是如此，16 个符号(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f)

000
001
002
003
004
005
006
007
008
009
00a
00b
00c
00d
00e
00f
010
011
012
013
...

我正要探讨在计算机中使用二进制而不是其他基数（例如 10）的原因。最重要的是，很容易有两种状态：开或关，或高和低。两种状态就像基数 2 中的两个符号 1 和 0。试图将电子设备在可用电压内调整到两种以上的状态是很困难的，至少过去是这样，保持电压接近零伏或高于某个小伏特是很困难的。相对容易，因此数字电子产品使用两种状态，二进制。

即使对于人类来说，二进制的简单任务也是冗长的，简单的二年级数学仍然有很多 1 和 0。因此八进制变得流行，因为它允许您以三位为一组进行思考，并且可以使用我们熟悉的数字 0、1、2、3、4、5、6、7 等符号。但是 4 组（2 的另一种幂）为人类提供了比八进制更多的心理计算能力，十六进制基于 4 位，这也是 2 的幂。我们必须在从 10 中借用的 10 中添加更多符号。传统阿拉伯语以 10 为基数，因此使用字母表的前 6 位。八进制很少使用，如果他们认为八进制而不是十六进制，你可以告诉他们的年龄。（我来自十六进制一代，但曾与八进制一代的人一起工作，他们与十六进制斗争，因为他们无法在头脑中从八进制到二进制再到十六进制）。

计算机中的基数 10 就像人类一般的十六进制思维一样。计算机不做基数 10（对于懒惰的人来说，他们以前做 bcd），它们做基数 2。计算机中的十进制数 1234 实际上是 0x4D2 或 0b010011010010。这是一个值，假设您想将 1234 加上其他一些数字相加，您需要该值，该值与符号 1、2、3 和 4 无关。但是要在 stackoverflow 上发布此答案，我们不使用我们的数字使用 ASCII，因此 1234 在 ascii 中是 0x31、0x32、0x33、0x34，这对于您的欧拉解决方案来说很重要，假设 1000 位数字作为 ascii 字符串提供，它必须是，否则您必须将其转换从二进制到 ascii，因为该问题是基数 10 的问题，而不是定义上基数 2 的问题。

回到我问的问题。假设你有 4 位内存来存储一个数字，你可以存储多大的数字？如果您只考虑以 10 为基数，您可能会认为该数字是 9，因为您被训练考虑在每个存储位置中使用最大的符号，如果您在 10 基数中有 5 个存储位置，则 99999 是最大数字。回到四位不过，单个位的最大符号是 1，将这个数字放入每个存储位置，您将得到 1111（四个一）。只需查看这四个数字，您应该能够在脑海中轻松看到相同数字 17 八进制或 F 十六进制的八进制和十六进制版本。要看到小数需要数学，或者在本例中需要记忆，该数字是十进制的 15。因此，您可以拥有的最大四位数字是 0xF 或 15，而不是 9。那么 8 位数字呢？ 0xFF 或 255（2 的 8 次方减 1）。最大的 16 位数字？ 65535 等。

所以当我问你想使用多少位时，这就是我的意思。看看这个数字 99999。同样以 10 为基数，你会认为这是最大的数字，但对于计算机来说，它只是其中的一部分，99999 十进制是 0x1869F，它需要 17 位内存来存储，这是你可以存储的最大 17 位数字store 是 0x1FFFF，即 131071，比 99999 稍大一些。因此，当您想在计算机上考虑大数字和数学时，您必须考虑二进制（或十六进制）。

最初你正在做乘法，这仍然是欧拉问题的一部分，但我要问的是与精度和位存储有关。这里有一些基础知识，我不会深入讨论，但你可以明白为什么我们依赖计算机中的浮点单元。

取最大的4位数字1111（二进制），即十进制的15。将其与最大的四位数字相加，得到 15+15 = 30 = 0x1E 或 11110 二进制。因此，要将两个四位数字相加，您需要五位来保存答案。计算机为这个额外的位保留一个“进位”位。本质上，计算机中的加/减整数数学函数允许您拥有 N+1 位。因此，如果它是 32 位计算机，则基本上有 33 位用于加/减数学运算。

问题是乘法和除法，即使在今天，许多处理器也不支持（是的，许多处理器没有 FPU，只做加法和减法，有时乘法，但除法很少见。乘法和除法需要大量电子设备，权衡是你可以用软件中的加法和减法来完成它们）。对四位系统采用最坏情况乘法
1111 * 1111 = 11100001 因此需要 8 位来存储 4 位乘法的结果，您很快就会发现，如果您有一个 4 位系统，则大多数您想要执行的乘法将产生一个无法存储在 4 中的数字位。因此，当我看到您采用 64 位整数（无符号 long long 通常是 64 位）并乘以四次时，这意味着您需要 64*5 或 320 位整数来存储您的答案，您试图将该答案放入64 个大结果，这通常取决于编译器和计算机会很乐意这样做，并且会截断高位，留下结果的低 64 位，这很容易看起来比任何操作数都小，这就是我的想法你一开始可能已经这么做了。

浮点与科学记数法没什么区别，但在二进制中，如果您想使用科学记数法将数字 1234 和 5678 相乘，则需要 1.234*10^3 乘以 5.678*10^3 并得到 7.007*10^6。您可以保持精度并能够表示更广泛的数字。我不会详细介绍它在二进制中是如何工作的。但它不适用于你原来的问题。

啊，最后一件事是澄清我在问题/回答中所做的事情。二进制负整数。由于加法和减法与基本系统之间的关系，您可以玩一些技巧。假设我想使用二进制从数字 7（十进制）中减 1。好吧，不存在减法电路这样的东西，而是添加一个负数，因此它不是 7 - 1，而是真正的 7 + (-1)，它会产生区别：

0111 + ???? = 0110

你可以将什么数加到 7 得到 6...二进制？

0111 + 1111 = 0110

二进制中的负数称为“二进制补码”，长话短说，答案是“反转并加 1”。负1如何用二进制表示？加一 0001 然后将其反转，意思是使个为零，零个为一（也称为补码）1110，然后加一 1111。减一在计算机中（以及任何地方）都是一个特殊数字，无论您有多少位被表示为全部。所以当你看到有人这样做时：

unsigned char a;

a = -1;

编译器首先查看 -1 并认为 ...11111（二进制），然后它查看等号和另一边，哦，你希望 a 为全一，它会看到你有一个有符号整数和一个无符号整数但转换只是将位移过来，所以你上面说你想要 a = 0xFF; （假设是 8 位无符号字符）。

有些编译器可能会抱怨您试图将负数存储在无符号数中。其他编译器会查看 -1 并将其视为 32 位或现在可能是 64 位有符号整数常量，然后当它将等于值评估为 8 位无符号时，您将收到一条警告，指出您无法将 -1 存储在有符号中或没有类型转换的 unsigned char。但如果你这样做：

a = 0; A - ;

所有编译器都会喜欢这样。并且不会抱怨，它只是在运行时而不是编译时消耗计算周期。

现在，一位朋友告诉我一本连续进行二进制数学运算的书。例如，要否定一个数字，通常您会执行反转并广告一个技巧，但使用铅笔和纸，有些人可能会告诉您另一个技巧。从右侧开始复制 0 直到第一个 1（包括第一个 1），然后反转，即负 2

0010
1110

从右边开始复制 0，然后复制第一个，然后向左反转剩余的位。

负 6

0110
1010

减 4

0100
1100

据说有做加法和减法的技巧（嗯，这些很简单），还有乘法和除法。如果您连续执行它们，那么您可以使用相同的 alu 以二进制形式执行无限长的数学运算。如果您知道如何做到这一点，您可以在软件中实现它，并且您最初的乘以大常数的问题（假设保留所有精度）在任何计算机上都是微不足道的。

What is it you are trying to do? Do you understand the basics of binary and decimal numbers? Why 8 bits only holds the values 0 to 255, 12 bits 0 - 4095, etc? How many bits does it take to hold the number you are interested in? Or better, how big of a number are you interested in creating? And are you using 9s to make the number bigger? What about hex 0xF... instead? If you want the biggest unsigned number (within one of the standard integer types) why not:

unsigned long long a,b;

a = -1; //which just seems wrong mixing signed and unsigned but it is valid, the number is converted to unsigned before storing

b = 0; b--; //does the same thing as above

Do you really need precision at that level? You realize that multiplies can require a result twice the size of each operand? 0xFF * 0xFF = 0xFE01, if in this case you were using 8 bit integers you could not do the math. It only gets worse as you continue to multiply 0xFF * 0xFF * 0xFF = 0xFD02FF.

What are trying to do?

Seeing your response:

I have not seen euler number 8 before. Sounds like a good interview question as it only takes a few lines of code to solve.

Your other response:

Numbers...

Likely because we have 10 fingers (and perhaps 10 toes) we grow up with "base 10". Our clocks are base 60 for the most part but it has been mixed with base 10 to make it more confusing. Anyway, base 10, means for each number placeholder you have one of 10 unique digits, when you reach the maximum in that place you roll over to the next place. This is all elementary school stuff.

000
001
002
003
...
008
009
010
011
012
...

See how the right most digit has 10 symbols (0,1,2,3,4,5,6,7,8,9) and when it reaches the last symbol it starts over and the one to the left of it increments by one. This rule is true for all base numbering systems.

It is true for base 2 except there are only two symbols, 0 and 1

000
001
010
011
100
101
...

Same is true for octal, but 8 symbols (0,1,2,3,4,5,6,7)

000
001
002
003
004
005
006
007
010
011
012
013
...

And the same is true for hexadecimal, 16 symbols(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f)

000
001
002
003
004
005
006
007
008
009
00a
00b
00c
00d
00e
00f
010
011
012
013
...

I was about to go into the whys of using binary over other bases (like 10) in computers. The bottom line it is easy to have two states on or off, or high and low. Two states is like two symbols 1 and 0 in base 2. Trying to keep electronics tuned to more than two states within the available voltage is tough, at least it used to be, keeping it near zero volts or above some small number of volts is relatively easy, so digital electronics use two states, binary.

Even a simple task for a human in binary is long winded, simple second grade math is still a lot of ones and zeros. So octal became popular because it allowed you to think in groups of three bits and you could use symbols we are familiar with as numbers 0,1,2,3,4,5,6,7. But groups of four which is another power of 2, gives the humans a lot more mental computing power than octal, hex is based on 4 bits which is also a power of 2. We had to add more symbols to the 10 we borrowed from the traditial arabic base 10, so the first 6 of the alphabet was used. Octal is rarely if ever used, you can tell someones age if they think octal instead of hex. (I am from the hex generation but have worked with those from the octal generation that struggle with hex because they cannot get from octal to binary to hex in their mind).

Base 10 in a computer is like the average human thinking in hex. computers dont do base 10 (well for lazy humans they used to do bcd), they do base 2. The decimal number 1234 in a computer is really 0x4D2 or 0b010011010010. That is as a value, say you want to add 1234 plus some other number you need that value which has nothing to do with the symbos 1, 2, 3, and 4. But to post this answer on stackoverflow we dont use the number we use ASCII, so 1234 in ascii is 0x31, 0x32, 0x33, 0x34, which is important to know for your euler solution assuming the 1000 digit number was provided as an ascii string, which it would have to be or you would have to convert it from binary to ascii since the problem is a base 10 problem and not base 2 by definition.

So back to what I had asked. Say you had 4 bits of memory to store a number, how big of a number could you store? If you think base 10 only you might think that number is a 9, because you are trained to think of using the biggest symbol in each storage location, 99999 is the biggest number if you have 5 storage locations in base 10. Back to four bits though, the biggest symbol for a single bit is 1, put that number in each storage location you get 1111 (four ones). Just by looking at those four ones you should be able to in your mind easily see the octal and hex version of that same number 17 octal or F hex. To see decimal takes math, or in this case memorization, that number is 15 decimal. So the biggest four bit number you can have is 0xF or 15 not 9. What about an 8 bit number? 0xFF or 255 (2 to the 8th power minus one). Biggest 16 bit number? 65535, etc.

So when I ask how many bits are you trying to use this is what I mean. Look at this number 99999. Again base 10 you would think that is the biggest number, but to a computer it is only part way there, 99999 decimal is 0x1869F, which takes 17 bits of memory to store, the biggest 17 bit number you can store is 0x1FFFF which is 131071 which is a bit bigger than 99999. So when you want to think big numbers and math on a computer you have to think binary (or hex).

Originally you were doing multiplications, which is still part of the euler problem, but what was I was asking about was related to precision and bit storage. Here are some fundamentals, and I wont get into it but you can see why we rely on floating point units in computers.

Take the largest 4 bit number 1111(binary), which is 15 decimal. Add that with the largest four bit number and you get 15+15 = 30 = 0x1E or 11110 binary. So to add two four bit numbers you need five bits to hold your answer. Computers keep a "carry" bit for this extra bit. Essentially the add/subtract integer math functions in the computer allow you to have N+1 bits. So if it is an 32 bit computer you basically have 33 bits for add/sub math.

The problem is multiply and divide, which even today many processors do not support (yes many have no fpu and only do add and subtract, sometimes multiply, but divide is rare. Multiply and divide take a lot of electronics the trade off is you can do them with adds and subtracts in software). Take the worst case multiply for a four bit system
1111 * 1111 = 11100001 so it takes 8 bits to store the result of a 4 bit multiply, you will quickly find that if you had a 4 bit system MOST of the multiplies you want to do will result a number that cannot be stored in 4 bits. So when I saw you taking 64 bit integers (the unsigned long long is often 64 bits) and multiplying four times, that means you need 64*5 or a 320 bit integer to store your answer, you were trying to put that answer in a 64 big result, which quite often, depending on the compiler and computer will happily do and will truncate the upper bits leaving you with the lower 64 bits of the result which can easily look smaller than any of your operands, which is what I had thought you might have done at first.

Floating point is not much more than scientific notation but in binary, if you wanted to multiply the number 1234 and 5678 using scientific notation you would take 1.234*10^3 times 5.678*10^3 and get 7.007*10^6. You keep your precision and are able to represent a wider range of numbers. I wont get into how this works in binary. But it doesnt work for your original question.

Ahh, the last thing to clarify what I was doing in my question/response. Negative integers in binary. Because of the relationships between addition and subtraction and base systems you can play some tricks. Say I wanted to subtract 1 from the number 7(decimal) using binary. Well there is no such thing as a subtract circuit, you instead add a negative number so instead of 7 - 1 it is really 7 + (-1), it makes a difference:

0111 + ???? = 0110

What number could you add to 7 to get 6...in binary?

0111 + 1111 = 0110

Negative numbers in binary are called "twos complement", long story short the answer is "invert and add 1". How do you represent minus 1 in binary? take plus one 0001 then invert it meaning make the ones zeros and the zeros ones (also known as ones complement) 1110 then add one 1111. Minus one is a special number in computers (well everywhere) as no matter how many bits you have it is represented as all ones. So when you see someone do this:

unsigned char a;

a = -1;

The compiler first looks at that -1 and thinks ...11111(binary) then it looks at the equals sign and the other side, oh, you want a to be all ones, it sees that you have a signed integer and an unsigned but the conversion is to just move the bits over so you are saying above that you want a = 0xFF; (assuming an 8 bit unsigned char).

Some compilers may complain that you are trying to store a negative number in an unsigned number. Other compilers will look at that -1 and see it as a 32 bit or these days maybe 64 bit signed integer constant and then when it evaluates the equals into an 8 bit unsigned you will get a warning that you cannot store -1 in a signed or unsigned char without a typecast. But if you do this:

a = 0; a--;

All compilers will like that. and wont complain, it just burns computing cycles at runtime instead of compile time.

Now somewhere a friend told me of a book that does binary math serially. For example to negate a number, usually you do the invert and ad one trick, but with pencil and paper some may tell you the other trick. Starting from the right copy the zeros up to and including the first 1 then invert after that, so minus 2

0010
1110

Starting from the right copy the 0 then the first one, then invert the remaining bits as you go left.

minus 6

0110
1010

minus 4

0100
1100

Supposedly there are tricks to do add and subtract (well duh, those are easy) but also multiply and divide. If you do them serially then you can do infinitely long math in binary with the same alu. If you were to know how to do that you could implement that in software and your original question of multiplying big constants (with the assumption of retaining all the precision) is trivial on any computer.

回复收藏 0 原文

温柔少女心 2024-07-14 14:47:15

您得到的答案 18446744073709551496 是由于您的 999...9 在分配给 long long 时被截断，加上多个操作溢出。它是确定性的，但实际上只是随机的位集合。

回复收藏 0 原文

只怪假的太真实 2024-07-14 14:47:15

unsigned int 代表系统字。现在，该字的最大长度为 2^32 -1 或 2^64 - 1，具体取决于您的系统是 32 位还是 64 位。你正在触及上限。

您必须编写一个 bignum 类或使用网络上的一个类。

你为什么要做这个问题呢？

回复收藏 0 原文

另类 2024-07-14 14:47:15

这些数字不适合 unsigned long long 范围，因此您可以使用 GMP 库或使用字符串来表示大数字，就像我在计算 50 等数字的阶乘时所做的那样：

http://codepad.org/bkWNV0JC

#include <cmath>
#include <iostream>
using namespace std;
int main()
{
  unsigned int nd, nz;   
  unsigned char *ca;   
  unsigned int j, n=50, q, temp;
  int i;
  double p;
    p = 0.0;
    for(j = 2; j <= n; j++)
    {
      p += log10((double)j);  
    }
    nd = (int)p + 1;

    ca = new unsigned char[nd+1];
    if (!ca)
    {
      cout << "Could not allocate memory!!!";
      exit(0);
    }
    for (i = 1; (unsigned)i < nd; i++)
    {
      ca[i] = 0;
    }
    ca[0] = 1;

    p = 0.0;
    for (j = 2; j <= n; j++)
    {
      p += log10((double)j);   
      nz = (int)p + 1;        
      q = 0;                  
      for (i = 0;(unsigned) i <= nz; i++)
      {
        temp = (ca[i] * j) + q;
        q = (temp / 10);
        ca[i] = (char)(temp % 10);
      }
    }

    cout << "\nThe Factorial of " << n << " is: ";
    for( i = nd - 1; i >= 0; i--)
    {
      cout << (int)ca[i];
    }
  //  delete []ca;    
  return 0;
}

The numbers can't fit in unsigned long long range so either you could use GMP library or use string to represent big numbers like I did for calculating factorial of number like 50:

http://codepad.org/bkWNV0JC

#include <cmath>
#include <iostream>
using namespace std;
int main()
{
  unsigned int nd, nz;   
  unsigned char *ca;   
  unsigned int j, n=50, q, temp;
  int i;
  double p;
    p = 0.0;
    for(j = 2; j <= n; j++)
    {
      p += log10((double)j);  
    }
    nd = (int)p + 1;

    ca = new unsigned char[nd+1];
    if (!ca)
    {
      cout << "Could not allocate memory!!!";
      exit(0);
    }
    for (i = 1; (unsigned)i < nd; i++)
    {
      ca[i] = 0;
    }
    ca[0] = 1;

    p = 0.0;
    for (j = 2; j <= n; j++)
    {
      p += log10((double)j);   
      nz = (int)p + 1;        
      q = 0;                  
      for (i = 0;(unsigned) i <= nz; i++)
      {
        temp = (ca[i] * j) + q;
        q = (temp / 10);
        ca[i] = (char)(temp % 10);
      }
    }

    cout << "\nThe Factorial of " << n << " is: ";
    for( i = nd - 1; i >= 0; i--)
    {
      cout << (int)ca[i];
    }
  //  delete []ca;    
  return 0;
}

回复收藏 0 原文

放肆 2024-07-14 14:47:15

如果您可以使用Boost，您可以尝试 cpp_int。它可能比 GMP 慢一点，但它是一个只有标头的库。

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main()
{
   using namespace boost::multiprecision;
// Repeat at arbitrary precision:
   cpp_int u = 1;
   for(unsigned i = 1; i <= 100; ++i)
      u *= i;

   // prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 (i.e. 100!)
   std::cout << u << std::endl;

   return 0;
}

If you can use Boost you can try cpp_int. It might be a bit slower than GMP but it is a header only library.

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main()
{
   using namespace boost::multiprecision;
// Repeat at arbitrary precision:
   cpp_int u = 1;
   for(unsigned i = 1; i <= 100; ++i)
      u *= i;

   // prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 (i.e. 100!)
   std::cout << u << std::endl;

   return 0;
}

回复收藏 0 原文

~没有更多了~