Signed integer multiplication with overflow

Question

I want to solve the following problem: assume that we have two int64_t numbers a and b. And we want to find a * b if the product fits int64_t data type and lowest 64 bits of multiplication result in other way. How can I resolve this ? I know the solution of the similar problem for uint64_t data type using long multiplication, can we apply it here ?

Does your compiler support 128 bit integers as an extension? — user694733
– user694733, Commented Dec 2, 2019 at 14:17
It goes along the lines of if(INT64_MAX / a > b) overflow = true;. You also have to consider negative numbers and INT64_MIN. — Lundin
– Lundin, Commented Dec 2, 2019 at 14:27

Bathsheba · Accepted Answer · 2019-12-02 14:59:55Z

1

By a sheer act of computational devilry, int64_t and uint64_t multiplication have the same bit pattern.

Therefore you can compute 1ULL * a * b and assign that to a uint64_t: the coefficient is there to force type conversion of a and b. Note that if a compiler supports int64_t then it is required to support uint64_t as well.

Then it's a matter of comparing the size of this product cf. a and b to see if it will fit into an int64_t. Wrap-around will have taken place if the product is smaller (in the unsigned sense) than either a and b.

edited Dec 2, 2019 at 14:59

answered Dec 2, 2019 at 14:32

Bathsheba

235k35 gold badges376 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

envy grunt Over a year ago

but i also want to find the lowest bits of correct product

Bathsheba Over a year ago

@envygrunt: The least significant bits will be correctly reported.

envy grunt Over a year ago

oh, okay so. ill try to implement this

Lundin Over a year ago

In theory ULL doesn't have to correspond to 64 bits. It would be more correct to use UINT64_C(1), but that gives uint_least64_t so it's not entirely correct either. The best solution is therefore to simply cast to uint64_t.

Lundin Over a year ago

Just a pedantic remark - it seems insane not to have unsigned long long as 64 bits.

|

Collectives™ on Stack Overflow

Signed integer multiplication with overflow

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related