Can someone suggest any good resources to learn about how various integer data types are manipulated in C++ from a competitive programming perspective ? I'm having problems with understanding them, for example
When you do something like
long int x = y*z, whereyandzarelong long int, but the value ofyandzare small (say 100), would it cause overflow ?When you do something like
int x = (a*b) % primewhena, b, primeare of the order 109 (but still stored in int), would it cause overflow ?What is the difference between double/point/long double etc ? How they're manipulated (like the above) ?
Does using longer (for example, using
long long intinstead ofint) causes the programme to run slower ? If yes, then how much (like a factor of 2 ? a factor of 4 ?)Why almost nobody uses long double in competitive programming ?
When manipulating digits of HUGE orders (like 10500), how that's done in CP ?
Why the strange result in running the following code ?








y = (1LL<<31) should fix your code.
When you do something like long int x = y*z, where y and z are long long int, but the value of y and z are small (say 100), would it cause overflow?
No.
When you do something like int x = (a*b) % prime when a, b, prime are of the order 109 (but still stored in int), would it cause overflow?
Yes.
What is the difference between double/point/long double etc? How they're manipulated (like the above)?
Doubles and long doubles are more precise than floats (storing 8 bytes of data rather than 4). Could you elaborate on what you mean by their manipulation?
Does using longer (for example, using long long int instead of int) causes the programme to run slower? If yes, then how much (like a factor of 2? a factor of 4?)
I'd guess that using long longs would indeed increase runtime due to a greater number of comparisons between bits. This probably leads to an increase by a factor of 2, since ints contain 4 bytes while long longs contain 8 bytes.
Why almost nobody uses long double in competitive programming?
In my experience, doubles and long doubles are functionally the same. You can refer to Stack Overflow for more detail.
When manipulating digits of HUGE orders (like 10500), how that's done in CP?
Some languages such as Python and Java can handle arbitrarily large integers, but in other languages such as C or C++, these numbers can be stored as strings or as an array or vector of digits.
Why the strange result in running the following code?
As lrvideckis said, it can be fixed by making the compiler interpret the
1that is being shifted as a long long.I think this may be helpful: http://www.cplusplus.com/articles/DE18T05o/
long longbehaves absolutely the same asint(and the same aslong), but can contain bigger values).a * bwill beint, so ifa = 10^8,b = 10^8, thena * b = 1874919424. Actually you can calculate it as(a * b + 2^31) % 2^32 - 2^31(here^, of course, means power, not the xor). But also remember that overflowing ofintis Undefined Behaviour for C++11 and older (in newer versions it's not an Undefined Behaviour), but overflow ofunsigned intis not (same withlong,long longandunsigned long,unsigned long long).)point(as GCC would say: maybe you meantfloat), butfloat,doubleandlong doublejust differ in their sizes.float— 32 bits,double— 64 bits,long double— 80 bits. Here you should read about representation of floating point numbers: https://en.wikipedia.org/wiki/Double-precision_floating-point_formatIf overflow occurs in case of floating point numbers, then they the result is either
infor-inf(that's how they are printed, and you can get them either bydouble inf = 1. / 0or bystd::numeric_limits<double>::infinity(), don't forget to#include <limits>in second case).long longandintare pretty the same, because now everybody has 64-bit processors, but becauselong longis bigger thanint, then you can have less values oflong longin cache, than inint's. So usingintis faster just because of caching. (Kind of proof: 39782428 withint, 40590461 withlong long)long doubleworks incorrectly on some platforms and you can get WAs, just becauselong doubleis not supported correctly. Precision oflong doubleis not much higher, than indouble, but calculations indouble's are much faster than inlong double(on some machines). So the wrong implentation and speed are the reasons. BTW,floatis bad because of precision problems.vectors or just usingstringor some hacks with modulos (maybe you just don't need to use such big integers)1isint,30isint, then(1 << 30)isint. Pretty logical, so(1 << 30)is2^30.Same with
(1 << 31), butintcan contain only integers in range:[-2^31; 2^31 - 1].2^31is not in that range, so overflow occurs and2^31 -> -2^31, so(1 << 31) == -2^31or just(1 << 31) == INT_MIN, then you assign it tounsigned long longwhich contains integers in range:[0; 2^64 - 1]. That's actually not an overflow, but type conversion frominttounsigned long long, but it works absolutely the same: so you get2^64 - 2^31.With
zwe have different case:2is int, butxisunsigned long long, so2 * xwill beunsigned long long, and that's absoultely logically2^31which we can represent inunsigned long long(no overflow or anything else).More info:
u,l, andll.Example given:
1uisunsigned int,1ll, islong long,1ullisunsigned long long.(1u << 31)->1uisunsigned int,31isint, then the result (1u << 31) isunsigned int(if we havesignedandunsignedas operands, it comes tounsigned.). So result is2^31, which is represented inunsigned int, so no overflow or anything.(1u << 31) == 2^31.Even more:
(1u << 31) == INT_MIN((1u << 31) == -2^31). Let's look:(1u << 31)is2^31and isunsigned int.INT_MINis-2^31and isint.We don't compare different types, so we convert both of them to the
unsigned int, so-2^31->2^31, so we compare2^31 == 2^31asunsigned ints, which is, of course, true.Output is:
Here we can see integer promotion,
char,signed char,unsigned char,shortandunsigned shorton any operation (even unary, like+or-as in example) are promoted toint.But wit
unsigned intwe stay onunsigned int, so-uiisunsigned intand that's overflow.