Martha Wg

Greenhorn

Posts: 7

posted 6 years ago

could you please look at my question,and let me know where I get wrong? I am greatly appreciate any tips or suggestions.

The question is asked to give the last value of i where a[i] output correctly.

my solution: a[i+2] = 2^{i+2} - 1, and a[i+2] is a integer so that it is stored in 32 bits. 2^{i+2} - 1 <= 2^{32}, and I get i = 30.

but the correct answer is a = 31.

how to get a = 31?

The question is asked to give the last value of i where a[i] output correctly.

my solution: a[i+2] = 2^{i+2} - 1, and a[i+2] is a integer so that it is stored in 32 bits. 2^{i+2} - 1 <= 2^{32}, and I get i = 30.

but the correct answer is a = 31.

how to get a = 31?

posted 6 years ago

- 1

int cannot go up to 2^{32}, it can only go up to 2^{31}-1. So if you need to go beyond that you must use long.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Kurt Van Etten

Ranch Hand

Posts: 98

posted 6 years ago

Hi Martha,

Just to expand a little on why that program works for a[31] = (2^31) - 1. Now, since the largest possible positive int value is (2^31) - 1, you're right that you would get numeric overflow if you tried to calculate it in that order: the (2^31) will overflow before you have a chance to subtract the 1. However, if you unwind the calculation that is being done in line 12 of the program, what is actually being calculated is essentially (2^30) + (2^30 - 1). So the final step is an addition, and no overflow takes place.

[edit:] In looking back over your question, I realized that maybe you're confused about a different aspect of the problem. In the loop iteration when i = 31, it is true that the calculation for a[i+2] is going to be wrong due to overflow (as will have been a[i+1]). But that doesn't matter, because what is being printed in that iteration is a[i], which was calculated two iterations back and is correct.

Just to expand a little on why that program works for a[31] = (2^31) - 1. Now, since the largest possible positive int value is (2^31) - 1, you're right that you would get numeric overflow if you tried to calculate it in that order: the (2^31) will overflow before you have a chance to subtract the 1. However, if you unwind the calculation that is being done in line 12 of the program, what is actually being calculated is essentially (2^30) + (2^30 - 1). So the final step is an addition, and no overflow takes place.

[edit:] In looking back over your question, I realized that maybe you're confused about a different aspect of the problem. In the loop iteration when i = 31, it is true that the calculation for a[i+2] is going to be wrong due to overflow (as will have been a[i+1]). But that doesn't matter, because what is being printed in that iteration is a[i], which was calculated two iterations back and is correct.