Curious arithmetic error- 255x256x256x256=18446744073692774400

Question

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?

Answer 1

 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.

Answer 2

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.

Answer 3

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 2³² 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 2⁶⁴. (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.