Блог пользователя kirankumarmitra

Автор kirankumarmitra, история, 6 лет назад, По-английски

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, where y and z are long long int, but the value of y and z are small (say 100), would it cause overflow ?

  • 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 ?

  • 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 of int) 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 ?

code
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

y = (1LL<<31) should fix your code.

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

I think this may be helpful: http://www.cplusplus.com/articles/DE18T05o/

  1. no overflow will be caused. (That's pretty obvious. long long behaves absolutely the same as int (and the same as long), but can contain bigger values).
  2. will cause overflow. (a * b will be int, so if a = 10^8, b = 10^8, then a * 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 of int is Undefined Behaviour for C++11 and older (in newer versions it's not an Undefined Behaviour), but overflow of unsigned int is not (same with long, long long and unsigned long, unsigned long long).)
  3. Don't know what is point (as GCC would say: maybe you meant float), but float, double and long 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_format
    If 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 by double inf = 1. / 0 or by std::numeric_limits<double>::infinity(), don't forget to #include <limits> in second case).
  4. Operations on long long and int are pretty the same, because now everybody has 64-bit processors, but because long long is bigger than int, then you can have less values of long long in cache, than in int's. So using int is faster just because of caching. (Kind of proof: 39782428 with int, 40590461 with long long)
  5. long double works incorrectly on some platforms and you can get WAs, just because long double is not supported correctly. Precision of long double is not much higher, than in double, but calculations in double's are much faster than in long double (on some machines). So the wrong implentation and speed are the reasons. BTW, float is bad because of precision problems.
  6. Doing long arithmetics with usage of vectors or just using string or some hacks with modulos (maybe you just don't need to use such big integers)
  7. Overflow occurs. Let's look closely:

1 is int, 30 is int, then (1 << 30) is int. Pretty logical, so (1 << 30) is 2^30.
Same with (1 << 31), but int can contain only integers in range: [-2^31; 2^31 - 1]. 2^31 is not in that range, so overflow occurs and 2^31 -> -2^31, so (1 << 31) == -2^31 or just (1 << 31) == INT_MIN, then you assign it to unsigned long long which contains integers in range: [0; 2^64 - 1]. That's actually not an overflow, but type conversion from int to unsigned long long, but it works absolutely the same: so you get 2^64 - 2^31.
With z we have different case: 2 is int, but x is unsigned long long, so 2 * x will be unsigned long long, and that's absoultely logically 2^31 which we can represent in unsigned long long (no overflow or anything else).

More info:

  1. To make integers constants to have different types you can add suffixes u, l, and ll.
    Example given: 1u is unsigned int, 1ll, is long long, 1ull is unsigned long long.
    (1u << 31) -> 1u is unsigned int, 31 is int, then the result (1u << 31) is unsigned int (if we have signed and unsigned as operands, it comes to unsigned.). So result is 2^31, which is represented in unsigned 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) is 2^31 and is unsigned int.
    INT_MIN is -2^31 and is int.
    We don't compare different types, so we convert both of them to the unsigned int, so -2^31 -> 2^31, so we compare 2^31 == 2^31 as unsigned ints, which is, of course, true.
unsigned char uc = 255;
unsigned int ui = -1; // UINT_MAX, because overflow occurs, BTW no Undefined Behaviour.
cout << +uc << " " << ui << endl; // +uc so it converts to int
cout << -uc << " " << -ui << endl;

Output is:

255 4294967295
-255 1

Here we can see integer promotion, char, signed char, unsigned char, short and unsigned short on any operation (even unary, like + or - as in example) are promoted to int.
But wit unsigned int we stay on unsigned int, so -ui is unsigned int and that's overflow.