# Grains C++ Integer Overflow

Hi,

Why do I get an overflow in the total function? Shouldn’t I be able to call `square(64ULL)` inside the `total()` function? I pass the first 7 tests but not the last test 8. Here is my code.

``````#include "grains.h"

#include <vector>
#include <numeric>
#include <limits>

namespace grains {

long long unsigned square(long long unsigned square) {
long long unsigned grain {1};

for (int i = 1; i < static_cast<int>(square); ++i) {
grain *= 2ULL;
}

return grain;
}

long long unsigned total() {
// This line makes the test pass.
//return std::numeric_limits<long long unsigned>::max();
// This line fails the test 8.
return square(65ULL);
}

}  // namespace grains
``````

What is the maximal value that an `unsigned long long` can represent?
What is the “mathematical” value of `square(65)`?

Or put differently:
When `square(65)` gets called the `for` loop loops 64 times (`1` to `65` exclusive). What’s the value of `grain` in the last two iterations of the loop?

1 Like

Hi Matthias!

I have changed the code because I thought I could solve the exercise.
The maximum value that a long long unsigned int can hold in C++ is `18,446,744,073,709,551,615`.

Before I was getting this positive integer `9223372036854775808`.

`9223372036854775808 x 2 = 18446744073709551616`

`18446744073709551616` overflows the long long unsigned int type.

I added an index to the print out. The last two values now look like this:

``````63 -9223372036854775808
0
``````

New code.

``````#include "grains.h"

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>

namespace grains {

long long unsigned square(int sqr) {
long long signed grain {1};
int index {0};

do {
std::cout << index << " " << grain << "\n";
grain *= 2;
index++;
} while (grain != 0);

return static_cast<long long unsigned>(grain);
}

long long unsigned total() {
return square(10);
}

}  // namespace grains

int main() {
std::cout << '\n' << grains::square(64) << '\n';

return 0;
}

// OUTPUT

0 1
1 2
2 4
3 8
4 16
5 32
6 64
[...truncated...]
60 1152921504606846976
61 2305843009213693952
62 4611686018427387904
63 -9223372036854775808 // ????
0
``````

In this second snippet you changed the type of the variable `grain` from `unsigned long long` to `signed long long`. Why that?
A `signed long long` can represent even fewer values that an `unsigned long long`, if it overflows you get undefined behavior (UB). In practice you get a negative value (`-9223372036854775808`).

You will have to find a way to implement the two functions without overflow (or in a way that an overflow does not affect the correct result).
The implementation of `square()` from your first snippet did that, it calculated the correct result for any of the 64 squares.

But when you call `square(65)` an `unsigned long long` cannot represent the mathematically correct value, you get `0`.
Can you find an implementation of `total()` that does not call `square(65)`?

1 Like

Matthias,
Thank you so much for the assistance. I was able to write code to pass the test. Calling `square(65)` inside of `total()` was not a good idea.

Thanks again.