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
, wherey
andz
arelong long int
, but the value ofy
andz
are small (say 100), would it cause overflow ?When you do something like
int x = (a*b) % prime
whena, b, prime
are 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 int
instead 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
1
that is being shifted as a long long.I think this may be helpful: http://www.cplusplus.com/articles/DE18T05o/
long long
behaves absolutely the same asint
(and the same aslong
), but can contain bigger values).a * b
will 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 ofint
is Undefined Behaviour for C++11 and older (in newer versions it's not an Undefined Behaviour), but overflow ofunsigned int
is not (same withlong
,long long
andunsigned long
,unsigned long long
).)point
(as GCC would say: maybe you meantfloat
), butfloat
,double
andlong double
just 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
inf
or-inf
(that's how they are printed, and you can get them either bydouble inf = 1. / 0
or bystd::numeric_limits<double>::infinity()
, don't forget to#include <limits>
in second case).long long
andint
are pretty the same, because now everybody has 64-bit processors, but becauselong long
is bigger thanint
, then you can have less values oflong long
in cache, than inint
's. So usingint
is faster just because of caching. (Kind of proof: 39782428 withint
, 40590461 withlong long
)long double
works incorrectly on some platforms and you can get WAs, just becauselong double
is not supported correctly. Precision oflong double
is 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,float
is bad because of precision problems.vector
s or just usingstring
or some hacks with modulos (maybe you just don't need to use such big integers)1
isint
,30
isint
, then(1 << 30)
isint
. Pretty logical, so(1 << 30)
is2^30
.Same with
(1 << 31)
, butint
can contain only integers in range:[-2^31; 2^31 - 1]
.2^31
is not in that range, so overflow occurs and2^31 -> -2^31
, so(1 << 31) == -2^31
or just(1 << 31) == INT_MIN
, then you assign it tounsigned long long
which contains integers in range:[0; 2^64 - 1]
. That's actually not an overflow, but type conversion fromint
tounsigned long long
, but it works absolutely the same: so you get2^64 - 2^31
.With
z
we have different case:2
is int, butx
isunsigned long long
, so2 * x
will beunsigned long long
, and that's absoultely logically2^31
which we can represent inunsigned long long
(no overflow or anything else).More info:
u
,l
, andll
.Example given:
1u
isunsigned int
,1ll
, islong long
,1ull
isunsigned long long
.(1u << 31)
->1u
isunsigned int
,31
isint
, then the result (1u << 31
) isunsigned int
(if we havesigned
andunsigned
as 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^31
and isunsigned int
.INT_MIN
is-2^31
and 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^31
asunsigned int
s, which is, of course, true.Output is:
Here we can see integer promotion,
char
,signed char
,unsigned char
,short
andunsigned short
on any operation (even unary, like+
or-
as in example) are promoted toint
.But wit
unsigned int
we stay onunsigned int
, so-ui
isunsigned int
and that's overflow.