25

I encountered a strange thing when I was programming under c++. It's about a simple multiplication.

Code:

unsigned __int64 a1 = 255*256*256*256;
unsigned __int64 a2= 255 << 24; // same as the above

cerr()<<"a1 is:"<<a1;
cerr()<<"a2 is:"<<a2;

interestingly the result is:

a1 is: 18446744073692774400 
a2 is: 18446744073692774400

whereas it should be:(using calculator confirms)

4278190080

Can anybody tell me how could it be possible?

Eric Leschinski
  • 146,994
  • 96
  • 417
  • 335
Hamid Bazargani
  • 847
  • 1
  • 15
  • 30
  • It's called undefined behaviour – Tony The Lion Sep 20 '12 at 13:50
  • Serious passions on post rating :) From -3 to 2 and back in 5 seconds. – Ivan Akulov Sep 20 '12 at 13:51
  • 9
    Don't see why this received 8 upvotes... –  Sep 20 '12 at 13:51
  • 10
    @H2CO3: Because it's a "non-obvious language quirk that is super interesting" and not because the question is well formulated or researched... – Xeo Sep 20 '12 at 13:52
  • 18
    @H2CO3: Yeah, let's nobody code anything ever in a language we don't 110% understand. You do realize, don't you, that if we took that mindset we'd never learn anything new? – cHao Sep 20 '12 at 13:55
  • 28
    An annoying thing about C++ compilers is that using them without turning warnings on will let you make tons of mistakes you shouldn't have to. When I compile this code in GCC with `g++ -Wall -Wextra -pedantic`, the compiler tells me quite clearly: "warning: integer overflow in expression [-Woverflow]". Microsoft Visual Studio also diagnoses this problem: "warning C4307: '*' : integral constant overflow". I hope this serves as a lesson to compile with warnings on in the future. – R. Martinho Fernandes Sep 20 '12 at 13:59
  • Kind of the same thing: http://stackoverflow.com/questions/12487923/why-overflow-happens-on-calculation-depending-on-the-data-type-when-the-type-whe#comment16802182_12487923 – chris Sep 20 '12 at 14:10
  • @R.MartinhoFernandes For the multiplication, my g++ (4.5.1, yeah, old) warns with default warning level. – Daniel Fischer Sep 20 '12 at 14:11
  • 1
    Another way to avoid overflow might be using literal suffixes. Depending on your compiler, `255ULL * 256 * 256 * 256` could work. – aschepler Sep 20 '12 at 14:20
  • @aschepler Not only "could", _must_, per the standard. – Daniel Fischer Sep 20 '12 at 14:22
  • @DanielFischer: Is `unsigned long long` guaranteed to have at least 64 bits? (Admittedly, it would be silly for a compiler to support a `__int64` type and not make it an alias for `long long`.) – aschepler Sep 20 '12 at 14:28
  • 2
    @DanielFischer: hence "depending on your compiler", since everyone's still busy implementing the current standard. `unsigned long long` isn't in C++03, so to use it you need either a compiler-specific extension to C++03 or (for the time being) a compiler-specific partial implementation of C++11. In practice *everybody* has `long long`. – Steve Jessop Sep 20 '12 at 14:28
  • @SteveJessop Ah, yes, I forgot how lagging C++ was in that respect. – Daniel Fischer Sep 20 '12 at 14:30
  • @aschepler: the minimum conforming value of `ULLONG_MAX` is `18446744073709551615`, which is the standard's way of saying "at least 64 bits". – Steve Jessop Sep 20 '12 at 14:30

5 Answers5

39
 255*256*256*256

all operands are int you are overflowing int. The overflow of a signed integer is undefined behavior in C and C++.

EDIT:

note that the expression 255 << 24 in your second declaration also invokes undefined behavior if your int type is 32-bit. 255 x (2^24) is 4278190080 which cannot be represented in a 32-bit int (the maximum value is usually 2147483647 on a 32-bit int in two's complement representation).

C and C++ both say for E1 << E2 that if E1 is of a signed type and positive and that E1 x (2^E2) cannot be represented in the type of E1, the program invokes undefined behavior. Here ^ is the mathematical power operator.

ouah
  • 142,963
  • 15
  • 272
  • 331
  • Thanks,It worked with unsigned __int64 a1 = 255*256*256; a1=a1*256; – Hamid Bazargani Sep 20 '12 at 13:55
  • just my curiosity, but is int64 should have 64 bits? and 255*256*256*256 = ff 00 00 00 and is 32bit number – user902383 Sep 20 '12 at 13:56
  • 6
    @user902383: Those 255s and 256s are ints. So C++ does all the intermediate steps with ints (which are more than likely 32 bits). Numerically, it winds up with 0xFF000000. Convert that to signed 64-bit, and you get 0xFFFFFFFFFF000000 (sign extension). This is just one way it could happen, but it's by far the most common one. – cHao Sep 20 '12 at 13:59
  • Isn't this different than in C, where the type of a literal is determined by its size? – rubenvb Sep 20 '12 at 14:10
  • @rubenvb: AFAIK, even in C, whole-number literals are ints unless you specifically tell them to be otherwise (via a cast or suffix). They just get converted to the appropriate size as needed, which in this case is *after* all the math is done. – cHao Sep 20 '12 at 14:13
  • @cHao No, since C99, the type is determined by size, the first in a list (`int`, `long int`, `long long int` for decimal constants without suffix, plus the corresponding `unsigned` types for octal or hexadecimal constants; minus the types excluded by a suffix) the constant fits in is the type. – Daniel Fischer Sep 20 '12 at 14:16
  • 1
    Anyway, `256` is guaranteed to have type `int` since it fits in an `int`. Multiplying it by something else doesn't change that, the literals are all small. – Steve Jessop Sep 20 '12 at 14:17
  • One could argue the whole multiplication is a constant literal, but I'm sure I'm wrong. "If only C(++) was designed to be nice" is very applicable here. – rubenvb Sep 20 '12 at 14:20
  • 2
    @rubenvb: yeah, you couldn't argue that based on the standard, because the definition of a literal in the standard is a simple matter of syntax, and `256*255` isn't it :-) – Steve Jessop Sep 20 '12 at 14:26
  • 1
    @rubenvb It's a "constant expression", and overflow in that makes the program ill-formed. – Daniel Fischer Sep 20 '12 at 14:28
17

Your literals are int. This means that all the operations are actually performed on int, and promptly overflow. This overflowed value, when converted to an unsigned 64bit int, is the value you observe.

Puppy
  • 144,682
  • 38
  • 256
  • 465
  • 6
    The fundamental mistake of the OP is far wider spread than this example: It's the misguided assumption that the type of the *left-hand side* somehow exudes magic powers on the right hand side and makes it clairvoyantly change behaviour. – Kerrek SB Sep 20 '12 at 14:03
  • 4
    @KerrekSB Come on. People simply don't expect overflow since the end of the 8 bit era, and it's not unreasonable to expect literals (or expressions of only literals) to be typed automatically. – Potatoswatter Sep 20 '12 at 14:07
  • 1
    @Potatoswatter: I think it would be fairly insane if the *type* of an expression depended on the *values* of its constituents... how would you even specify that? What's the type of `256 * n`? – Kerrek SB Sep 20 '12 at 14:10
  • @KerrekSB hence, "only literals." But it's common (or good practice, IMHO) to specify a large constant number as a product of several smaller ones. This does happen in real life. – Potatoswatter Sep 20 '12 at 14:13
  • @KerrekSB, Doesn't Pyhton do that? I think I saw something about it upgrading the type upon overflow. – chris Sep 20 '12 at 14:16
  • @Potatoswatter: I know that you meant only literals, but again, how would you specify that? It seems to me that you'd get into a mess. – Kerrek SB Sep 20 '12 at 14:17
  • @chris: yes, Python does that, by dynamically allocating enough memory for the value. That's "too heavyweight" for C. – Steve Jessop Sep 20 '12 at 14:21
  • 5
    @Kerrek: I don't think it would be difficult to define "expressions only involving literals", no more difficult than defining "integer constant expression" in C++. But even if the standard did do that, someone would want another special case where the type is different, and the rules would get more complicated again. Btw, the lhs does exude magical powers on the rhs in one case, which is assigning a function or member function pointer from an overloaded name. Dig deep enough and even misguided assumptions can become guided in special cases ;-) – Steve Jessop Sep 20 '12 at 14:22
16

It is perhaps worth explaining what happened to produce the number 18446744073692774400. Technically speaking, the expressions you wrote trigger "undefined behavior" and so the compiler could have produced anything as the result; however, assuming int is a 32-bit type, which it almost always is nowadays, you'll get the same "wrong" answer if you write

uint64_t x = (int) (255u*256u*256u*256u);

and that expression does not trigger undefined behavior. (The conversion from unsigned int to int involves implementation-defined behavior, but as nobody has produced a ones-complement or sign-and-magnitude CPU in many years, all implementations you are likely to encounter define it exactly the same way.) I have written the cast in C style because everything I'm saying here applies equally to C and C++.

First off, let's look at the multiplication. I'm writing the right hand side in hex because it's easier to see what's going on that way.

255u * 256u               = 0x0000FF00u
255u * 256u * 256u        = 0x00FF0000u
255u * 256u * 256u * 256u = 0xFF000000u (= 4278190080)

That last result, 0xFF000000u, has the highest bit of a 32-bit number set. Casting that value to a signed 32-bit type therefore causes it to become negative as-if 232 had been subtracted from it (that's the implementation-defined operation I mentioned above).

(int) (255u*256u*256u*256u) = 0xFF000000 = -16777216

I write the hexadecimal number there, sans u suffix, to emphasize that the bit pattern of the value does not change when you convert it to a signed type; it is only reinterpreted.

Now, when you assign -16777216 to a uint64_t variable, it is back-converted to unsigned as-if by adding 264. (Unlike the unsigned-to-signed conversion, this semantic is prescribed by the standard.) This does change the bit pattern, setting all of the high 32 bits of the number to 1 instead of 0 as you had expected:

(uint64_t) (int) (255u*256u*256u*256u) = 0xFFFFFFFFFF000000u

And if you write 0xFFFFFFFFFF000000 in decimal, you get 18446744073692774400.

As a closing piece of advice, whenever you get an "impossible" integer from C or C++, try printing it out in hexadecimal; it's much easier to see oddities of twos-complement fixed-width arithmetic that way.

zwol
  • 135,547
  • 38
  • 252
  • 361
  • The conversion to unsigned types is prescribed by the standard (4.7. in C++03, probably somewhere similar in C++11; 6.3.1.3 in C99 and C11) to be reduction modulo `2^WIDTH`. – Daniel Fischer Sep 20 '12 at 18:49
0

The answer is simple -- overflowed.

Lingfeng Xiong
  • 1,131
  • 2
  • 9
  • 25
0

Here Overflow occurred on int and when you are assigning it to unsigned int64 its converted in to 18446744073692774400 instead of 4278190080

Rahul
  • 591
  • 1
  • 7
  • 21