Integer Types and Overflow

Loading...

Из курса от партнера Saint Petersburg State University

Competitive Programmer's Core Skills

7 оценки

Saint Petersburg State University

Competitive Programmer's Core Skills

7 оценки

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.

Из урока

COMMON STRUGGLES

In competitive programming, there are a lot of things to stumble upon — if you don't know them first! We'll delve into how numbers are represented in computers, identify the most common issues with integer and floating point arithmetic, and learn to overcome them. We'll also discuss how to get stuck less in general, especially when debugging solutions.

Integer Types and Overflow5:36

Dealing with Overflow5:54

Non-integers8:01

Fixed Point Numbers and Errors7:06

Floating Point Numbers6:33

Where and How to Use Doubles10:42

More on Floating Point8:07

Познакомьтесь с преподавателями

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

[MUSIC]

Hi, in this video, we'll talk about numbers.

Numbers are the most fundamental units of the programs but numbers in the computer

don't always behave the same as your usual numbers in math.

And this could lead to very subtle bugs which are very hard to find

if you don't know beforehand.

So in this lesson, we'll learn how numbers are stored in a computer,

what are the most common issues with them, and how to deal with it.

So in this video, we'll begin with integers and

their most common issue, the integer overflow.

What could possibly go wrong with such simple data type?

Well, let's look at the following code in C++.

It just takes two integers and multiplies it, prints out the results.

What do you think the output will be?

It turns out the result is not 2.5 billion, but

some totally unexpected negative number.

And in general, it will be the same, but in Python everything will be fine.

So what happened?

To know, we need to learn a bit more about how numbers are stored in a computer.

You could think of a computer's memory as a very long sequence of bits,

binary digits.

Each taking value of 0 or 1.

And when you write integer constant is set to 13, for computer,

it is in fact 1101 as everything should come in binary.

And indeed, 13 is 1 + 4 + 8.

But in fact, the bits come in chunks of 8, which are called bytes.

So the memory looks more like this.

And it's because you could not take the value of individual bits.

You must take the whole byte.

So when you create an integer variable in language like C++ or

Java, it always takes four bytes in memory.

And we assign some value to it, these bits are set so

that the whole 32-bit number is equal to this value.

So for example for 13, there will be many zeroes in the beginning and

1101 in the end.

So that's the most common integer type, int.

It has 4 bytes, or 32 bits.

So it could store at most 2 to the 32nd different values.

And that's clearly not all integers.

All integers are infinite.

And in fact, it stores just a consecutive range of values.

And half of them are negative.

So it's the range from minus 2 to the 31st, up to 2 to the 31st minus 1.

Since it's simpler for us to work in decimal,

you could just think about 2 to the 31st as a number slightly more than 2 billion.

Now, it's easy to see what's wrong with our example, because 50,000 times

50,000 is 2.5 billion, and that is more than 2 to the 31st.

So that's what is integer overflow, when the result of some

operation do not fit in the range, in fact some other value is stored.

And of course, getting incorrect values somewhere could lead to an incorrect

answer, so we'd like to avoid this.

In fact, fixed integer variables are true for languages like C++ and Java.

In Python, integers are arbitrary sized, meaning that the result of some

operation is too large, the variable size is explained as needed.

So in Python, there is no overflow but you should still think about the magnitude

of the values because larger values mean more space and time.

What could help us outside Python is some larger integer type.

And indeed, most program languages have 64-bit integer type.

In C++, this type is called long long or int64_t.

In fact, the first one is not guaranteed to have exactly 64 bits.

But in fact, in any popular platform, it's solved.

So in computer programming, the first one is used more often.

In Java, this type is called long, as it has 64 bits,

it could take 2 to the 64th different values.

And as for the integers is the range from minus 2 to

the 63rd up to 2 to the 63rd minus 1.

Simple multiplication shows that if you multiply two ints,

then the result will always fit in our long, and that's very useful.

And even more so, if you take two values, each no greater than a billion,

then the result will also fit.

So in this video we learned, what is overflow, and

what integer variables do exist?

And in the next, we'll finally learn how to avoid it.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play