casting int to unsigned long long

Question

I was solving a problem wherein the task was to output the result of a pascal triangle at a given row mentioned by a user.

https://leetcode.com/problems/pascals-triangle-ii/

I wrote my solution which had issues storing huge factorial results.

vector<int> getRow(int rowIndex) {

             vector<int> v;

             int C = 1; 
             v.push_back(1);

                for (int i = 1; i <= rowIndex; i++)  
                {
                  printf("%d ", C);  
                  C = C * (rowIndex +1 - i) / i;
                  v.push_back(C);
                }

  return v;
}

On going through these questions,

What range of values can integer types store in C++

How many bytes is unsigned long long?

and going through some other sources, i made the following change which gave me the required result.

    C = (unsigned long long)C * (rowIndex +1 - i) / i;

Since "C" is of type int and my vector v stores int, i wanted to know why would a cast unsigned long long still give me valid results.

Just a guess... Maybe because after division by `i` the value gets back to the region where `int` is a full and legal value? — Alex Lop., Nov 21 '16 at 07:43

score 3 · Accepted Answer · answered Nov 21 '16 at 07:42

The sub-expression C * (rowIndex +1 - i) can overflow before your division. By casting C to a larger data-type then the whole expression becomes that type, so the multiplication will not overflow. Then after the division with i the result is converted to an int again, but because of the division it is within range of an int.

Note that this is only for the values you currently have. If you continue with even higher values then sooner or later you will have overflows that can't be fixed by such a cast.

I was getting confused on how could an unsigned long long value be stored in a int variable.... feel super dumb for breaking my head over for a long time. — xAditya3393, Nov 21 '16 at 08:02

score 1 · Answer 2 · answered Nov 21 '16 at 07:51

1

When you say

(unsigned long long)C

you are not making actual variable C a unsigned long long. You are just saying when doing this

C * (rowIndex +1 - i) / i;

treat C (at the right side) as unsigned long long. That is, only the temporary space to hold C, then hold its multiplication with (rowIndex +1 - i), and then its division with i is done at a space that big. If the whole result was bigger than a value that integer can have, this would not work either.

answered Nov 21 '16 at 07:51

t.m.

1,430
16
29

Was so worried about upcasting unsigned long long to int i didnt end up realising the value could fall in the range... – xAditya3393 Nov 21 '16 at 08:02

casting int to unsigned long long

2 Answers2