c++equalityunsignedsignedinteger-overflow

Why is (18446744073709551615 == -1) true?

When I was working on string::npos I noticed something and I couldn't find any explanation for it on the web. 

(string::npos == ULONG_MAX)

and 

(string::npos == -1)

are true.

So I tried this:

(18446744073709551615 == -1)

which is also true.

How can it be possible? Is it because of binary conversation?

Solution

  • 18,446,744,073,709,551,615

    This number mentioned, 18,446,744,073,709,551,615, is actually 2^64 − 1. The important thing here is that 2^64-1 is essentially 0-based 2^64. The first digit of an unsigned integer is 0, not 1. So if the maximum value is 1, it has two possible values: 0, or 1 (2).

    Let's look at 2^64 - 1 in 64bit binary, all the bits are on.

    1111111111111111111111111111111111111111111111111111111111111111b

    The -1

    Let's look at +1 in 64bit binary.

    0000000000000000000000000000000000000000000000000000000000000001b

    To make it negative in One's Complement (OCP) we invert the bits.

    1111111111111111111111111111111111111111111111111111111111111110b

    Computers seldom use OCP, they use Two's Complement (TCP). To get TCP, you add one to OCP.

    1111111111111111111111111111111111111111111111111111111111111110b (-1 in OCP)
+                                                              1b (1)
-----------------------------------------------------------------
1111111111111111111111111111111111111111111111111111111111111111b (-1 in TCP)

    "But, wait" you ask, if in Twos Complement -1 is,

    1111111111111111111111111111111111111111111111111111111111111111b

    And, if in binary 2^64 - 1 is 

    1111111111111111111111111111111111111111111111111111111111111111b

    Then they're equal! And, that's what you're seeing. You're comparing a signed 64 bit integer to an unsigned 64bit integer. In C++ that means convert the signed value to unsigned, which the compiler does.

    Update

    For a technical correction thanks to davmac in the comments, the conversion from -1 which is signed to an unsigned type of the same size is actually specified in the language, and not a function of the architecture. That all said, you may find the answer above useful for understanding the arch/languages that support two's compliment but lack the spec to ensure results you can depend on.