How to determine integer types that are twice the width as `int` and `unsigned`?

Question

Values of intermediate multiplication typically need twice the number of bits as inputs.

 // Example
int foo(int a, int b, int carry, int rem) {
  int2x c;  // Some type that is twice as wide at `int`
  c = (int2x)a * b + carry;
  return (int) (c % rem);
}

Considering the potential for padding, (which appears to limit sizeof() usefulness) and non-2`s complement integers (which limits bit dibbling), ...

Does the following always create the needed type? (when it exists.)
If not, how to code at least a reasonable solution, even if not entirely portable?

---

#include <limits.h>
#include <stdint.h>

#if LONG_MAX/2/INT_MAX - 2 == INT_MAX
  typedef long int2x;
  typedef unsigned long unsigned2x;
#elif LLONG_MAX/2/INT_MAX - 2 == INT_MAX
  typedef long long int2x;
  typedef unsigned long long unsigned2x;
#elif INTMAX_MAX/2/INT_MAX - 2 == INT_MAX
  typedef intmax_t int2x;
  typedef uintmax_t unsigned2x;
#else
  #error int2x/unsigned2x not available
#endif

---

[Edit]
Qualify:"always", if long, long long and intmax_t, do not work it is OK to #error.
What I want to know is if at least 1 of long, long long, or intmax_t will work, will int2x be correctly typed?

Notes: The above assumes xxx_MAX are some odd power-of-2 minus 1. Maybe a good assumption? The above works on at least 2 platforms, but that is hardly a great portability test.

Answer 1

For signed types it's better to work just with the range of values of the considered types and compare them.

Firstly, one would try to calculate INT_MAX*INTMAX+INT_MAX in order to have the maximum possible value in the expression a*b+carry. By casting to intmax_t seems the more reasonable approach:

 #define MAX_EXPRESSION ((intmax_t) INT_MAX * INTMAX + INT_MAX)

However, we can fall in trouble if the true mathematical value of MAX_EXPRESSION is greater than INTMAX_MAX. So, let's do some maths to surround this problem.

Let's denote c = INT_MAX and m = INTMAX_MAX. We want to know if c*c+c <= m, mathematically speaking. This leads us to the inequation: c <= (m - c) / c. Since the division is integer, the result is truncated, so the exact maths are lost in the last operation. Thus, we have to write a more precise expression, like this: `c <= floor((m - c) / c) + fractional_part_of((m - c) / c).

If c > floor((m - c) / c), strictly, then c >= floor((m - c) / c) + 1 > (m - c) / c, where the division is taken in mathematical sense (with exact decimals). which gives us c*c+c > m, contradiction. So, we conclude that c <= floor((m - c) / c), again, mathematically speaking.

This expression is more handy in C, because m - c will give us a correct value when calculated with type intmax_t (in other words: it's not an out-of-range value). Now, the division (m - c) / c will give us an integer number in the range of intmax_t, again, although possibly truncated, because the division is integer. Actually, it gives us the value floor((m - c) / c, without hesitation.

It this comparisson gives true, then we can say that c*c+c is representable in the greatest signed integer type of your systen, that is, intmax_t. In particular: there exists a signed integer type which is capable of representing the value c*c+c in your system.

Now, in C code, we can write:

  #define c INT_MAX
  #define m INTMAX_MAX

  #if (c <= (m - c) / c)
     // There exists a signed type in your system
     // such that INT_MAX*INTMAX+INT_MAX is representable
     // as a value in that type.
  #else
      #error Sorry, the size of INT_MAX cannot be doubled...
  #endif  

Once you have determined that intmax_t does the job, you simply can start a search for the signed integer type with minimal rank that solves the problem: We can ask again the same question we did for intmax_t, for example for long and long long:

  #include <stdint.h>
  #include <limits.h>
  #define c INT_MAX

  #if (c <= (INTMAX_MAX - c) / c)
      #if (c <= (LLONG_MAX - c) / c)
          #if (c <= (LONG_MAX - c) / c)
             typedef long int2x;
          #else
             typedef long long int2x;
          #endif
      #else
         typedef intmax_t int2x;
      #endif
  #else
      #error Sorry, the size of type "int" cannot be doubled...
  #endif

Answer 2

The assumption that all *_MAX constants are of the form (2^n)-1 is valid. See 6.2.6 Representations of Types, and particularly 6.2.6.2 Integer types, where the representations of unsigned integer types and the positive values of signed integer types are fully defined as pure binary, thus yielding a maximum which is one less than a power of two.