Why unsigned int 0xFFFFFFFF is equal to int -1?

30
votes

In C or C++ it is said that the maximum number a size_t (an unsigned int data type) can hold is the same as casting -1 to that data type. for example see Invalid Value for size_t

Why?

I mean, (talking about 32 bit ints) AFAIK the most significant bit holds the sign in a signed data type (that is, bit 0x80000000 to form a negative number). then, 1 is 0x00000001.. 0x7FFFFFFFF is the greatest positive number a int data type can hold.

Then, AFAIK the binary representation of -1 int should be 0x80000001 (perhaps I'm wrong). why/how this binary value is converted to anything completely different (0xFFFFFFFF) when casting ints to unsigned?? or.. how is it possible to form a binary -1 out of 0xFFFFFFFF?

I have no doubt that in C: ((unsigned int)-1) == 0xFFFFFFFF or ((int)0xFFFFFFFF) == -1 is equally true than 1 + 1 == 2, I'm just wondering why.

6
c++ccastingbinary
Read about "Two's complement" on Wikipedia; this is the most common way of encoding negative numbers in binary. – Artelius
en.wikipedia.org/wiki/Two%27s_complement – anon
You'll notice that, just as with unsigned numbers, adding 1 to the highest possible number will give you the lowest possible number. – Drew Dormann
The binary representation of negative one has to be that representation that yields zero when one is added to it. This is 0xFFFFFFFF. – David Schwartz

6 Answers

50
votes

C and C++ can run on many different architectures, and machine types. Consequently, they can have different representations of numbers: Two's complement, and Ones' complement being the most common. In general you should not rely on a particular representation in your program.

For unsigned integer types (size_t being one of those), the C standard (and the C++ standard too, I think) specifies precise overflow rules. In short, if SIZE_MAX is the maximum value of the type size_t, then the expression

(size_t) (SIZE_MAX + 1)

is guaranteed to be 0, and therefore, you can be sure that (size_t) -1 is equal to SIZE_MAX. The same holds true for other unsigned types.

Note that the above holds true:

  • for all unsigned types,
  • even if the underlying machine doesn't represent numbers in Two's complement. In this case, the compiler has to make sure the identity holds true.

Also, the above means that you can't rely on specific representations for signed types.

Edit: In order to answer some of the comments:

Let's say we have a code snippet like:

int i = -1;
long j = i;

There is a type conversion in the assignment to j. Assuming that int and long have different sizes (most [all?] 64-bit systems), the bit-patterns at memory locations for i and j are going to be different, because they have different sizes. The compiler makes sure that the values of i and j are -1.

Similarly, when we do:

size_t s = (size_t) -1

There is a type conversion going on. The -1 is of type int. It has a bit-pattern, but that is irrelevant for this example because when the conversion to size_t takes place due to the cast, the compiler will translate the value according to the rules for the type (size_t in this case). Thus, even if int and size_t have different sizes, the standard guarantees that the value stored in s above will be the maximum value that size_t can take.

If we do:

long j = LONG_MAX;
int i = j;

If LONG_MAX is greater than INT_MAX, then the value in i is implementation-defined (C89, section 3.2.1.2).

30
votes

It's called two's complement. To make a negative number, invert all the bits then add 1. So to convert 1 to -1, invert it to 0xFFFFFFFE, then add 1 to make 0xFFFFFFFF.

As to why it's done this way, Wikipedia says:

The two's-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract. This property makes the system both simpler to implement and capable of easily handling higher precision arithmetic.

7
votes

Your first question, about why (unsigned)-1 gives the largest possible unsigned value is only accidentally related to two's complement. The reason -1 cast to an unsigned type gives the largest value possible for that type is because the standard says the unsigned types "follow the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer."

Now, for 2's complement, the representation of the largest possible unsigned value and -1 happen to be the same -- but even if the hardware uses another representation (e.g. 1's complement or sign/magnitude), converting -1 to an unsigned type must still produce the largest possible value for that type.

3
votes

Two's complement is very nice for doing subtraction just like addition :)

    11111110 (254 or -2)
   +00000001 (  1)
   ---------
    11111111 (255 or -1)

    11111111 (255 or -1) 
   +00000001 ( 1)
   ---------
   100000000 ( 0 + 256)
1
votes

That is two's complement encoding.

The main bonus is that you get the same encoding whether you are using an unsigned or signed int. If you subtract 1 from 0 the integer simply wraps around. Therefore 1 less than 0 is 0xFFFFFFFF.

-2
votes

Because the bit pattern for an int -1 is FFFFFFFF in hexadecimal unsigned. 11111111111111111111111111111111 binary unsigned. But in int the first bit signifies whether it is negative. But in unsigned int the first bit is just extra number because a unsigned int cannot be negative. So the extra bit makes an unsigned int able to store bigger numbers. As with an unsigned int 11111111111111111111111111111111 (binary) or FFFFFFFF (hexadecimal) is the biggest number a uint can store. Unsigned Ints are not recommended because if they go negative then it overflows and goes to the biggest number.