How to programmatically determine maximum and minimum limit of int data in C?

Question

I am attempting exercise 2.1 of K&R. The exercise reads:

Write a program to determine the ranges of char, short, int, and long variables, both signed and unsigned, by printing appropriate values from standard headers and by direct computation. Harder if you compute them: determine the ranges of the various floating-point types.

Printing the values of constants in the standards headers is easy, just like this (only integer shown for example):

printf("Integral Ranges (from constants)\n");
printf("int max: %d\n", INT_MAX);
printf("int min: %d\n", INT_MIN);
printf("unsigned int max: %u\n", UINT_MAX);

However, I want to determine the limits programmatically.

I tried this code which seems like it should work but it actually goes into an infinite loop and gets stuck there:

printf("Integral Ranges (determined programmatically)\n");

int i_max = 0;

while ((i_max + 1) > i_max) {
        ++i_max;
}

printf("int max: %d\n", i_max);

Why is this getting stuck in a loop? It would seem that when an integer overflows it jumps from 2147483647 to -2147483648. The incremented value is obviously smaller than the previous value so the loop should end, but it doesn't.

Answer 1

Ok, I was about to write a comment but it got too long...

Are you allowed to use sizeof?

If true, then there is an easy way to find the max value for any type:

For example, I'll find the maximum value for an integer:

Definition: INT_MAX = (1 << 31) - 1 for 32-bit integer (2^31 - 1)

The previous definition overflows if we use integers to compute int max, so, it has to be adapted properly:

INT_MAX = (1 << 31) - 1
        = ((1 << 30) * 2) - 1
        = ((1 << 30) - 1) * 2 + 2) - 1
        = ((1 << 30) - 1) * 2) + 1

And using sizeof:

INT_MAX = ((1 << (sizeof(int)*8 - 2) - 1) * 2) + 1

You can do the same for any signed/unsigned type by just reading the rules for each type.

Answer 2

So it actually wasn't getting stuck in an infinite loop. C code is usually so fast that I assume it's broken if it doesn't complete immediately.

It did eventually return the correct answer after I let it run for about 10 seconds. Turns out that 2,147,483,647 increments takes quite a few cycles to complete.

I should also note that I compiled with cc -O0 to disable optimizations, so this wasn't the problem.

A faster solution might look something like this:

int i_max = 0;
int step_size = 256;

while ((i_max + step_size) > i_max) {
    i_max += step_size;
}

while ((i_max + 1) > i_max) {
    ++i_max;
}

printf("int max: %d\n", i_max);

However, as signed overflow is undefined behavior, probably it is a terrible idea to ever try to programmatically guess this in practice. Better to use INT_MAX.

Answer 3

The simplest I could come up with is:

signed int max_signed_int = ~(1 << ((sizeof(int) * 8) -1));
signed int min_signed_int =  (1 << ((sizeof(int) * 8) -1));
unsigned int max_unsigned_int = ~0U;
unsigned int min_unsigned_int = 0U;

In my system:

// max_signed_int = 2147483647  
// min_signed_int = -2147483648
// max_unsigned_int = 4294967295  
// min_unsigned_int = 0

Answer 4

Assuming a two's complement processor, use unsigned math:

unsigned ... smax, smin;
    smax = ((unsigned ...)0 - (unsigned ...)1) / (unsigned ...) 2;
    smin = ~smax;

Answer 5

As it has been pointed here in other solutions, trying to overflow an integer in C is undefined behaviour, but, at least in this case, I think you can get an valid answer, even from the U.B. thing:

The case is tha if you increment a value and compare the new value with the last, you always get a greater value, except on an overflow (in this case you'll get a value lesser or equal ---you don't have more values greater, that's the case in an overflow) So you can try at least:

int i_old = 0, i = 0;
while (++i > i_old)
    i_old = i;
printf("MAX_INT guess: %d\n", i_old);

After this loop, you will have got the expected overflow, and old_i will store the last valid number. Of course, in case you go down, you'll have to use this snippet of code:

int i_old = 0, i = 0;
while (--i < i_old) 
    i_old = i;
printf("MIN_INT guess: %d\n", i_old);

Of course, U.B. can even mean program stopping run (in this case, you'll have to put traces, to get at least the last value printed)

By the way, in the ancient times of K&R, integers used to be 16bit wide, a value easily accessible by counting up (easier than now, try 64bit integers overflow from 0 up)

Answer 6

I would use the properties of two's complement to compute the values.

unsigned int uint_max = ~0U;
signed int int_max = uint_max >> 1;
signed int int_min1 = (-int_max - 1);
signed int int_min2 = ~int_max;

2^3 is 1000. 2^3 - 1 is 0111. 2^4 - 1 is 1111.

w is the length in bits of your data type.

uint_max is 2^w - 1, or 111...111. This effect is achieved by using ~0U.

int_max is 2^(w-1) - 1, or 0111...111. This effect can be achieved by bitshifting uint_max 1 bit to the right. Since uint_max is an unsigned value, the logical shift is applied by the >> operator, means it adds in leading zeroes instead of extending the sign bit.

int_min is -2^(w-1), or 100...000. In two's complement, the most significant bit has a negative weight!

This is how to visualize the first expression for computing int_min1:

...
011...111   int_max          +2^(w-1) - 1
100...000   (-int_max - 1)   -2^(w-1)      == -2^(w-1) + 1 - 1
100...001   -int_max         -2^(w-1) + 1  == -(+2^(w-1) - 1)
...

Adding 1 would be moving down, and subtracting 1 would be moving up. First we negate int_max in order to generate a valid int value, then we subtract 1 to get int_min. We can't just negate (int_max + 1) because that would exceed int_max itself, the biggest int value.

Depending on which version of C or C++ you are using, the expression -(int_max + 1) would either become a signed 64-bit integer, keeping the signedness but sacrificing the original bit width, or it would become an unsigned 32-bit integer, keeping the original bit width but sacrificing the signedness. We need to declare int_min programatically in this roundabout way to keep it a valid int value.

If that's a bit (or byte) too complicated for you, you can just do ~int_max, observing that int_max is 011...111 and int_min is 100...000.

Keep in mind that these techniques I've mentioned here can be used for any bit width w of an integer data type. They can be used for char, short, int, long, and also long long. Keep in mind that integer literals are almost always 32-bits by default, so you may have to cast the 0U to the data type with the appropriate bit width before bitwise NOTing it. But other than that, these techniques are based on the fundamental mathematical principles of two's complement integer representation. That said, they won't work if your computer uses a different way of representing integers, for example ones' complement or most-significant sign-bit.

Answer 7

The assignment says that "printing appropriate values from standard headers" is allowed, and in the real world, that is what you would do. As your prof wrote, direct computation is harder, and why make things harder for its own sake when you're working on another interesting problem and you just want the result? Look up the constants in <limits.h>, for example, INT_MIN and INT_MAX.

Since this is homework and you want to solve it yourself, here are some hints.

The language standard technically allows any of three different representations for signed numbers: two's-complement, one's-complement and sign-and-magnitude. Sure, every computer made in the last fifty years has used two's-complement (with the partial exception of legacy code for certain Unisys mainframes), but if you really want to language-lawyer, you could compute the smallest number for each of the three possible representations and find the minimum by comparing them.

Attempting to find the answer by overflowing or underflowing a signed value does not work! This is undefined behavior! You may in theory, but not in practice, increment an unsigned value of the same width, convert to the corresponding signed type, and compare to the result of casting the previous or next unsigned value. For 32-bit long, this might just be tolerable; it will not scale to a machine where long is 64 bits wide.

You want to use the bitwise operators, particularly ~ and <<, to calculate the largest and smallest value for every type. Note: CHAR_BITS * sizeof(x) gives you the number of bits in x, and left-shifting 0x01UL by one fewer than that, then casting to the desired type, sets the highest bit.

For floating-point values, the only portable way is to use the constants in <math.h>; floating-point values might or might not be able to represent positive and negative infinity, are not constrained to use any particular format. That said, if your compiler supports the optional Annex G of the C11 standard, which specifies IEC 60559 complex arithmetic, then dividing a nonzero floating-point number by zero will be defined as producing infinity, which does allow you to "compute" infinity and negative infinity. If so, the implementation will #define __STDC_IEC_559_COMPLEX__ as 1.

If you detect that infinity is not supported on your implementation, for instance by checking whether INFINITY and -INFINITY are infinities, you would want to use HUGE_VAL and -HUGE_VAL instead.

Answer 8

#include <stdio.h>

int main() {
    int n = 1;
    while(n>0) {
     n=n<<1;
    }
    int int_min = n;
    int int_max = -(n+1);
    printf("int_min is: %d\n",int_min);
    printf("int_max is: %d\n", int_max);

    return 0;
}

Answer 9

    unsigned long LMAX=(unsigned long)-1L;
    long SLMAX=LMAX/2;
    long SLMIN=-SLMAX-1;

If you don't have yhe L suffix just use a variable or cast to signed before castong to unsigned.

For long long:

    unsigned long long LLMAX=(unsigned long long)-1LL;