-2

Consider the following code:

#include <iostream>
int main(int argc, char* argv[])
{
    int i = /* something */;
    for (std::size_t n = 0; n < 100; ++n) {
        i *= 2;
        std::cout << i << std::endl;
    }
}

Overflowing on signed integers is undefined behavior. However, I don't quite get why this code seem to always end up with 0. Any explanation?

Vincent
  • 57,703
  • 61
  • 205
  • 388
  • `* 2` is equivalent to `<< 1` (undefined behaviour notwithstanding). – Oliver Charlesworth Jul 23 '17 at 23:16
  • 2
    It's a power of 2, it will always have one bit set and all the rest 0, after you pass the 32 bits of your integer you will get 0, then you multiply `0*something = 0`. If I am not mistaken :) – Tony Tannous Jul 23 '17 at 23:17
  • Hint: a 32-bit can hold the value (2^32) - 1. You loop is multiplying by powers of 2 up to 100. You will need at least a 101 bit number. In otherwords, you overflow at `n==32`. – Thomas Matthews Jul 23 '17 at 23:19
  • 1
    `char** argv[]` is an illegal parameter type for `main`. And please provide a reference where undefined behaviour excludes the result you see. – too honest for this site Jul 23 '17 at 23:26
  • "Undefined behaviour" means anything can happen - setting i to zero seems like a sensible behaviour on a standard computer when it gets to 2^32 (or 2^64, or however big your integers are), but on non-twos-complement architecture this may not be sensible, or other architecture might throw an overflow exception, or yet further architecture might fire out a boxing glove to punch you on the nose. – Ken Y-N Jul 23 '17 at 23:28
  • be aware that overflow of signed ints is undefined. It's common that it will wrap to 0 but it is not guaranteed. I was bitten by assuming it was when switching from gcc to llvm. It cost my company $60k in a bug bounty program. I was using code like `a = b * c; if (a < b) { error-oveflow; }`. That code was working and then started failing when switching to llvm. That's when I learned the [overflow behavior of signed ints is undefined](https://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c). – gman Jul 23 '17 at 23:35
  • 1
    If you understand undefined behavior and you understand that you're causing it, why are you asking why you get a behavior? Did you look at the generated code? You didn't provide enough information to actually give you an answer since we don't know what platform you're actually using, but unless you're suggesting the hardware is broken, there's really no answer. It's going to 0 because that's what the generated instructions do. Go look at the code the compiler generates then look up that instruction for your architecture and see that that's the behavior. – xaxxon Jul 24 '17 at 01:06

1 Answers1

5

Imagine multiplying a decimal number by ten repeatedly. Every time you do a multiplication, an additional zero is added to the decimal representation:

12345         // Initial value
123450        // × 10
1234500       // × 100
12345000      // × 1000
123450000     // × 10000
1234500000    // × 100000
12345000000   // × 1000000
123450000000  // × 10000000
1234500000000 // × 100000000

If your number representation had a finite number of K digits, and kept the lower K digits after multiplication, the resulting representation would become zero after at most K multiplications (fewer for numbers divisible by a power of ten).

The same thing happens to binary numbers, because 2 to a binary number is what 10 is for decimal numbers (in fact, two in binary is also 10; this is true for numbers in any base: the base of a numeric system is written as 10 in that system itself).

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 3
    A visualisation with base2 like youve done with base10 would make this answer even better – Nick is tired Jul 23 '17 at 23:27
  • 1
    @NickA Not really: people are used to think in decimal system. They learn to multiply by ten in elementary school, so using ten is a pretty powerful tool for visualizing binary math. To me, this was a pretty powerful a-ha moment. – Sergey Kalinichenko Jul 23 '17 at 23:28
  • 3
    @dasblinkenlight from my experience those who care to leave a comment are not the downvoters. – Tony Tannous Jul 23 '17 at 23:30
  • @das interesting, I've always found comparing decimal to binary confusing in examples like overflow on the basis that decimal is always infinite to me whereas binary I feel makes more sense as a finite system, also, I didnt DV – Nick is tired Jul 23 '17 at 23:30
  • 3
    @NickA My teacher in a high school programming class told us that shifting left was the same as multiplying by two, without giving any explanation. I thought about it, tried a few examples, and accepted it as some sort of CPU magic. A few days later it dawned on me that writing zero at the end of a number when multiplying by ten is the same as shifting the number left. This was the moment when I truly "got" binary. – Sergey Kalinichenko Jul 23 '17 at 23:34
  • Maybe that was the moment you "got" the place-value system! – M.M Jul 23 '17 at 23:51
  • @M.M I wouldn't go that far - I did not "get" place-value system until about a year later, after playing with hex numbers, and re-inventing radix-36 for myself. – Sergey Kalinichenko Jul 23 '17 at 23:58