26

I think first 400*400=160000 is converted to 28928 by starting from 0 and going 160000 time in a circular fashion for int type (say sizeof(int) = 2 bytes) assuming it like:

enter image description here

And then 28928 is divided by 400, floor of which gives 72 and the result varies with the type of variable. Is my assumption correct or there is any other explanation?

Innat
  • 16,113
  • 6
  • 53
  • 101
Imran Rana
  • 11,899
  • 7
  • 45
  • 51
  • 3
    What size is the int on your platform ? `sizeof(int)` – cnicutar Jan 29 '12 at 09:12
  • 1
    Actually int is an example(assuming it 2 byte), what i really wanted to know that if datatypes works in circular fashion or not, i mean wraparound works for datatypes or not. – Imran Rana Jan 29 '12 at 09:18
  • 1
    If you are interested in such subjects, I suggest you learn what is [congruence](http://en.wikipedia.org/wiki/Congruence_relation), check the binary representation of "unsigned" numbers vs "2's complement" and draw the relation. Then you'd understand that all unsigned or 2's complement operations are congruent `2^n` where `n` is the number of bits in the data type. This congruence is what you are calling "circular" – Shahbaz Jan 29 '12 at 13:04
  • I came to know about congruence in a Discrete Mathematics course long ago :) – Imran Rana Jan 29 '12 at 18:49

3 Answers3

42

Assuming you're using a horrifically old enough compiler for where int is only 16 bits. Then yes, your analysis is correct.*

400 * 400 = 160000 

//  Integer overflow wrap-around.
160000 % 2^16 = 28928

//  Integer Division
28928 / 400 = 72 (rounded down)

Of course, for larger datatypes, this overflow won't happen so you'll get back 400.

*This wrap-around behavior is guaranteed only for unsigned integer types. For signed integers, it is technically undefined behavior in C and C++.

In many cases, signed integers will still exhibit the same wrap-around behavior. But you just can't count on it. (So your example with a signed 16-bit integer isn't guaranteed to hold.)

Although rare, here are some examples of where signed integer overflow does not wrap around as expected:

Community
  • 1
  • 1
Mysticial
  • 464,885
  • 45
  • 335
  • 332
  • Thanks, it was just an example, what i really wanted to know that if datatypes works in circular fashion or not, i mean wraparound works for datatypes or not. – Imran Rana Jan 29 '12 at 09:19
  • 2
    Yes that's correct. But do be aware that only the unsigned integer types are guaranteed to have the wrap-around behavior. Signed integer types are undefined behavior upon overflow (though in most cases, they still exhibit the same wrap-around behavior). – Mysticial Jan 29 '12 at 09:21
  • Thanks i was little bit confused about signed-integer overflow as it was giving correct result according to my assumption. – Imran Rana Jan 29 '12 at 09:27
  • @ImranRana: It may be correct in your case, but you just need to keep in mind that if you use a different compiler or you compile for a different type of CPU, then the results may not be what you expect. – dreamlax Jan 29 '12 at 09:29
  • @ImranRana: The bottom line is that you should avoid performing calculations that will overflow. As the answer says, the behavior is undefined; that means that anything can happen (crashing your program is one of the friendlier behaviors), and once the overflow has happened it's too late to do anything about it. Even if it seems to work, optimizing compilers can easily cause such code to misbehave very badly. In this particular case, using `long` rather than `int` will avoid the problem. – Keith Thompson Jan 29 '12 at 09:39
  • Thank u sir, i'm not using that calculation, i was only eager to know about da circular/wrap-around fact of data-types, again thnx for u'r support. – Imran Rana Jan 29 '12 at 09:46
  • 4
    Not only "horrifically old" compilers, but also plenty of C implementations for modern microcontroller architectures have a 16-bit `int`. – Andrey Vihrov Jan 29 '12 at 17:20
  • The *unsigned* integer types do wrap around always, the *signed* ones do whatever the underlying CPU does (signed overflow is undefined behaviour, so the compiler doesn't have to consider it could happen; if the code executes some instruction that does that, well...) – vonbrand Jan 20 '13 at 15:17
  • @Mysticial: *Of course, for larger datatypes, this overflow **will** happen*, too. Just it will happen at larger values: for 32-bit integer 70000*70000/70000 results in 8643. – CiaPan Oct 08 '15 at 05:15
  • @CiaPan: More interestingly, gcc for 32-bit platforms will sometimes process `unsigned mul_mod_65535(uint16_t x, uint16_t y) { return (x*y) & 65535;}` in a way that malfunctions if the product would exceed INT_MAX before truncation. – supercat May 22 '17 at 04:51
6

It certainly seems like you guessed correctly.

If int is a 16-bit type, then it'll behave exactly as you described. Your operation happens sequentially and 400 * 400 produces 160000, which is 10 0111 0001 0000 0000

when you store this in 16-bit register, top "10" will get chopped off and you end up with 0111 0001 0000 0000 (28,928).... and you guessed the rest.

Which compiler/platform are you building this on? Typical desktop would be at least 32-bit so you wouldn't see this issue.

UPDATE #1

NOTE: This is what explain your behavior with YOUR specific compiler. As so many others were quick to point out, DO NOT take this answer to assume all compilers behave this way. But YOUR specific one certainly does.

To complete the answer from the comments below, the reason you are seeing this behavior is that most major compilers optimize for speed in these cases and do not add safety checks after simple arithmetic operations. So as I outlined above, the hardware simply doesn't have room to store those extra bits and that's why you are seeing "circular" behavior.

DXM
  • 4,413
  • 1
  • 19
  • 29
  • 2
    It won't necessarily behave as described. Signed integer overflow in C and C++ is undefined behaviour. – dreamlax Jan 29 '12 at 09:17
  • 1
    @dreamlax: and NULL is also left as "open to compiler interpretation" in actual specification but in all compilers I know of it is always 0. You may be right in general, I only have experience with HP-UX and Windows (VS and Intel compilers). Those all behave this way and I can't speak for all other compilers. But it certainly seems likely that OP's compiler behaves exactly as I described. I was only trying to answer the question, not explain general language specification – DXM Jan 29 '12 at 09:21
  • `NULL` is not "open to compiler interpretation". `NULL` is defined by the C standard as the integer expression 0, or such an expression cast as a `void *`, i.e. `((void *) 0)`. In the C++ specification it is defined as `0`. Also, this answer is misleading, even though it may be "correct" in this case, the OP may think that all C implementations will behave this way. – dreamlax Jan 29 '12 at 09:26
  • @dreamlax: fine you win. Of all the language's "undefined" behavior I clearly picked the wrong one. – DXM Jan 29 '12 at 09:31
  • 2
    @DXM: When we say that signed overflow causes "undefined behavior", that term has a very specific technical definition in the C standard. Some implementations overflow, some terminate the program, and they're allowed to make demons fly out your nose. Well-known compilers optimize your program assuming an int never overflows, causing poorly-written loops to never terminate (for example). – Dietrich Epp Jan 29 '12 at 09:41
  • I never disagreed with anyone here. I'm definitely more of a Windows/VS person than general C++ compiler guru. I merely tried to explain what OP was seeing. Answer updated based on the comments provided here. Thanks everyone for learning me something new. – DXM Jan 29 '12 at 09:51
  • @dreamlax: Yes, according the C standard, an implementation could behave a different way. In practice, they don't. – dan04 Jan 29 '12 at 09:56
  • @dan04: really? after I was chewed out and down voted, you really wanted to jump into this with an alternate opinion? I kinda appreciate it, but why would you do that.... walk away, I'll take one for the team. – DXM Jan 29 '12 at 09:59
  • 2
    @dan04: In practice they *do*. There are instances where optimisations alter the behaviour of signed integer overflow because the optimiser is "legally" allowed to assume that a signed integer type won't overflow. See [here](http://www.airs.com/blog/archives/120) for an in-depth explanation. – dreamlax Jan 29 '12 at 10:15
  • See the "unwarranted assumptions" in [this question](http://stackoverflow.com/questions/3457967/what-belongs-in-an-educational-tool-to-demonstrate-the-unwarranted-assumptions-p). *Nobody* found a counterexample to #6 or #7. – dan04 Jan 29 '12 at 10:22
  • 1
    @dan04: There are counterexamples in the question you provided (Commodore PET) and also counterexamples in the article I linked to. The optimiser in GCC can ***and does*** assume that signed integers don't wrap around, *as evidenced in the article I linked to*. Nobody found a counterexample in a very small and trivial operation on signed integer types, but that does not at all mean that it is supported in any way. – dreamlax Jan 29 '12 at 10:28
  • @dreamlax: Oops. I didn't see the Commodore PET output before (with it being a screenshot instead of nice circular text). I'll concede. – dan04 Jan 29 '12 at 10:41
5

The first thing you have to know is, in C, integer overflows are undefined behavior.

(C99, 6.5.5p5) "If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined."

C says it very clear and repeats it here:

(C99, 3.4.3p3) "EXAMPLE An example of undefined behavior is the behavior on integer overflow."

Note that integer overflows only regard signed integer as unsigned integer never overflow:

(C99, 6.2.5p9) "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type."

Your declaration is this one:

int i = 400 * 400 / 400;

Assuming int is 16-bit in your platform and the signed representation is two's complement, 400 * 400 is equal to 160000 which is not representable as an int, INT_MAX value being 32767. We are in presence of an integer overflow and the implementation can do whatever it wants.

Usually, in this specific example, the compiler will do one of the two solutions below:

  1. Consider the overflow wraps around modulo the word size like with unsigned integers then the result of the 400 * 400 / 400 is 72.
  2. Take advantage of the undefined behavior to reduce the expression 400 * 400 / 400 to 400. This is done by good compilers usually when the optimization options are enabled.

Note that that integer overflows are undefined behavior is specific to C language. In most languages (Java for instance) they wrap around modulo the word size like unsigned integers in C.

In gcc to have overflow always wrap, there is the -fno-strict-overflow option that can be enabled (disabled by default). This is for example the choice of the Linux kernel; they compile with this option to avoid bad surprises. But this also constraints the compiler to not perform all optimizations it can do.

ouah
  • 142,963
  • 15
  • 272
  • 331