假设我的系统是32位机器。如果我使用 long int 存储 n > 63 的值，那么我的结果将为 0。如何解决这个问题？
如何求2的n次方，其中n的取值范围为0到200。
11
- mousey
7
5你想要用这些数值做什么？ - Andreas Brinck
计算2的n次方，从0到200的结果 ;) - hhafez
这些大数字无法适应 long int 类型，你需要使用更大的数据类型。 - Thorbjørn Ravn Andersen
您可以通过 http://www.wolframalpha.com/input/?i=2^99（根据需要替换）验证您的结果。 - Thorbjørn Ravn Andersen
2的200次方等于1606938044258990275541962092341162602522202993782792835301376。 - Asad Khan
显示剩余2条评论
9个回答
14
double能够完美地精确存储2的幂，直到1023为止。不要让任何人告诉你浮点数总是不精确的，这是一个特殊情况，它们并不总是不精确的！
double x = 1.0;
for (int n = 0; n <= 200; ++n)
{
printf("2^%d = %.0f\n", n, x);
x *= 2.0;
}
程序的部分输出：
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
...
2^196 = 100433627766186892221372630771322662657637687111424552206336
2^197 = 200867255532373784442745261542645325315275374222849104412672
2^198 = 401734511064747568885490523085290650630550748445698208825344
2^199 = 803469022129495137770981046170581301261101496891396417650688
2^200 = 1606938044258990275541962092341162602522202993782792835301376
- fredoverflow
9
你怎么会是唯一一个想到这个的人？其他人是如何得到那么多票数的？ - Potatoswatter
1尽管数字的内部存储是完整和精确的，但我认为将其转换为十进制以进行打印并不保证是精确的。你很幸运。 - Mark Ransom
这在几乎所有情况下都可以工作，但从技术上讲，C标准没有规定浮点值的内部表示。根据实现方式，仍然可能出现舍入误差。在常见平台上，这可能会起作用。 - Thom Smith
@Thom，我在这里假设IEEE754。 - fredoverflow
1IEEE 754-1985 §5.6：“当整数…超出双精度浮点数的10^17范围时，实施者可以选择在第17位之后更改所有重要数字为其他十进制数字，通常为0。”但是这并不妨碍您实现自己完全精确的小数打印机，假设字符串转换与问题相关。 （这样会完整地找到幂，虽然需要花费一些时间。） - Potatoswatter
显示剩余4条评论
7
只需等待256位编译器，然后使用
要实现这个功能，可以使用以下代码片段（未经测试）：
int即可。不过说真的，由于你只想从1开始不断加倍，你最好使用一个大整数库，例如GNU MP。要实现这个功能，可以使用以下代码片段（未经测试）：
#include <stdio.h>
#include "gmp.h"
int main (void) {
int i;
mpz_t num;
mpz_init_set_ui (num, 1);
for (i = 0; i <= 200; i++) {
printf ("2^%d = ", i);
mpz_out_str (NULL, 10, num);
printf ("\n");
mpz_mul_ui (num, num, 2);
}
return 0;
}
如果您想编写自己的数据结构，使用只有两个操作（double和print）的长整型数组是可行的，但我认为使用GMP会更容易。
如果您确实想自己编写，请参考以下内容。这是我过去开发的一些大整数库的变体/简化版本：
#include <stdio.h>
#include <stdlib.h>
// Use 16-bit integer for maximum portability. You could adjust
// these values for larger (or smaller) data types. SZ is the
// number of segments in a number, ROLLOVER is the maximum
// value of a segment plus one (need to be less than the
// maximum value of your datatype divided by two. WIDTH is
// the width for printing (number of "0" characters in
// ROLLOVER).
#define SZ 20
#define ROLLOVER 10000
#define WIDTH 4
typedef struct {
int data[SZ];
} tNum;
// Create a number based on an integer. It allocates the segments
// then initialises all to zero except the last - that one is
// set to the passed-in integer.
static tNum *tNumCreate (int val) {
int i;
tNum *num = malloc (sizeof (tNum));
if (num == NULL) {
printf ("MEMORY ERROR\n");
exit (1);
}
for (i = 0; i < SZ - 1; i++) {
num->data[i] = 0;
}
num->data[SZ-1] = val;
}
// Destroy the number. Simple free operation.
static void tNumDestroy (tNum *num) {
free (num);
}
// Print the number. Ignores segments until the first non-zero
// one then prints it normally. All following segments are
// padded with zeros on the left to ensure number is correct.
// If no segments were printed, the number is zero so we just
// output "0". Then, no matter what, we output newline.
static void tNumPrint (tNum *num) {
int i, first;
for (first = 1, i = 0; i < SZ; i++) {
if (first) {
if (num->data[i] != 0) {
printf ("%d", num->data[i]);
first = 0;
}
} else {
printf ("%0*d", WIDTH, num->data[i]);
}
}
if (first) {
printf ("0");
}
printf ("\n");
}
// Double a number. Simplified form of add with carry. Carry is
// initialised to zero then we work with the segments from right
// to left. We double each one and add the current carry. If
// there's overflow, we adjust for it and set carry to 1, else
// carry is set to 0. If there's carry at the end, then we have
// arithmetic overflow.
static void tNumDouble (tNum *num) {
int i, carry;
for (carry = 0, i = SZ - 1; i >= 0; i--) {
num->data[i] = num->data[i] * 2 + carry;
if (num->data[i] >= ROLLOVER) {
num->data[i] -= ROLLOVER;
carry = 1;
} else {
carry = 0;
}
}
if (carry == 1) {
printf ("OVERFLOW ERROR\n");
exit (1);
}
}
// Test program to output all powers of 2^n where n is in
// the range 0 to 200 inclusive.
int main (void) {
int i;
tNum *num = tNumCreate (1);
printf ("2^ 0 = ");
tNumPrint (num);
for (i = 1; i <= 200; i++) {
tNumDouble (num);
printf ("2^%3d = ", i);
tNumPrint (num);
}
tNumDestroy (num);
return 0;
}
以及它相关的输出：
2^ 0 = 1
2^ 1 = 2
2^ 2 = 4
2^ 3 = 8
2^ 4 = 16
2^ 5 = 32
2^ 6 = 64
2^ 7 = 128
2^ 8 = 256
2^ 9 = 512
: : : : :
2^191 = 3138550867693340381917894711603833208051177722232017256448
2^192 = 6277101735386680763835789423207666416102355444464034512896
2^193 = 12554203470773361527671578846415332832204710888928069025792
2^194 = 25108406941546723055343157692830665664409421777856138051584
2^195 = 50216813883093446110686315385661331328818843555712276103168
2^196 = 100433627766186892221372630771322662657637687111424552206336
2^197 = 200867255532373784442745261542645325315275374222849104412672
2^198 = 401734511064747568885490523085290650630550748445698208825344
2^199 = 803469022129495137770981046170581301261101496891396417650688
2^200 = 1606938044258990275541962092341162602522202993782792835301376
- paxdiablo
3
如果我想使用自己的数据结构，该怎么做？ - mousey
1@mousey：这真的取决于你的数据结构。提出一个数据结构，你可能会得到一些建议。 - Yuliy
@mousey：看看我的解决方案，使用了
String。 - polygenelubricants6
我很久没有认真使用Java了，但是：BigInteger类呢？它具备所有常见的数学（multiply，pow）和位运算（shiftLeft）操作。
不过你的标记有点混乱，你更喜欢哪种语言呢？
- Thorarin
2
1使用BigInteger，只需一行代码即可：http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#pow(int) - Denis Tulskiy
pow是不必要的；shiftLeft就足够了。看看我的答案。 - polygenelubricants6
Python支持大整数。在Linux命令行窗口中，运行以下命令：
$ python -c "for power in range(201): print power, 2**power"
0 1
1 2
2 4
3 8
4 16
5 32
6 64
<snip>
196 100433627766186892221372630771322662657637687111424552206336
197 200867255532373784442745261542645325315275374222849104412672
198 401734511064747568885490523085290650630550748445698208825344
199 803469022129495137770981046170581301261101496891396417650688
200 1606938044258990275541962092341162602522202993782792835301376
如果需要，这可以很容易地制作成一个脚本。请参阅任何Python教程。
- bukzor
1
@Thorarin：我在问题中没有看到任何特定于语言的内容。现在才看到带有C/C++/Java标签，但这意味着他不太关心使用哪种语言。也许我推断得太多了... - bukzor
5
使用
如果
java.math.BigInteger.shiftLeft 方法。 for (int i = 0; i <= 200; i++) {
System.out.format("%d = %s%n", i, BigInteger.ONE.shiftLeft(i));
}
以下是输出结果摘录：
0 = 1
1 = 2
2 = 4
3 = 8
4 = 16
:
197 = 200867255532373784442745261542645325315275374222849104412672
198 = 401734511064747568885490523085290650630550748445698208825344
199 = 803469022129495137770981046170581301261101496891396417650688
200 = 1606938044258990275541962092341162602522202993782792835301376
如果
BigInteger 不可用，您也可以手动进行乘法计算并将其存储在 String 中。 String s = "1";
for (int i = 0; i < 200; i++) {
StringBuilder sb = new StringBuilder();
int carry = 0;
for (char ch : s.toCharArray()) {
int d = Character.digit(ch, 10) * 2 + carry;
sb.append(d % 10);
carry = d / 10;
}
if (carry != 0) sb.append(carry);
s = sb.toString();
System.out.format("%d = %s%n", i + 1, sb.reverse());
}
- polygenelubricants
4
在每次迭代中将
BigInteger.ONE 左移 i 次，而不是将其复制一份并在每次迭代中左移一次，哪种方法更有效呢？ - AngryWhenHungry@Angry：我追求的是简洁易读，而不是效率，但我认为对于
BigInteger 来说，将 1 位移 k 次可能比将 k-1 位（其中大部分是零）移动 1 次更便宜。 - polygenelubricants1你的方法确实更简洁。谢谢你指出在这种情况下它也更有效率。+1 :) - AngryWhenHungry
@Angry：不要只听我的话，看看基准测试吧！http://www.ideone.com/wIRln - polygenelubricants
1
在 Kotlin 中：
var x= readLine()!!.toInt()
var y=BigDecimal(1)
for (i in 1..x)
{
y *= BigDecimal(2)
}
println(DecimalFormat().format(y))
- mostafa
1
欢迎来到Stackoverflow。请解释您的解决方案。 - Jonathan
1
使用Scheme！
1 => (expt 2 200)
1606938044258990275541962092341162602522202993782792835301376
- Fakrudeen
0
如果
unsigned long int 是 64 位，则您可以表示的最大值为 2^63（即 n = 63）：
unsigned long int x = (1UL << n); // n = 0..63
- Paul R
2
使用字符串或数组，我们可以表示更多的内容。 - mousey
我相信这就是你需要的：http://stackoverflow.com/questions/2643487/long-int-long-long-data-types/2643514#2643514 :-) - paxdiablo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接