如何确定宽度为`int`和`unsigned`两倍的整数类型？

Question

中间乘法的值通常需要两倍于输入的位数。

 // 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);
}

考虑到填充的可能性，（这似乎限制了

sizeof()

的有用性）和非 2`s 补整数（这限制了比特位），...

以下是否总是创建所需的类型？ （当它存在时。）
如果不是，即使不完全可移植，如何至少编写一个合理的解决方案？

---

#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

---

[编辑]
限定：“总是”，如果

long

，

long long

和

intmax_t

，不工作就可以

#error

.
我想知道的是，如果

long

、

long long

或

intmax_t

中的至少 1 个可以工作，那么

int2x

会被正确输入吗？

注意：以上假设

xxx_MAX

是 2 的奇次幂减 1。也许是一个好的假设？以上至少适用于 2 个平台，但这并不是一个很好的可移植性测试。

Answer 1

所有 *_MAX 常量的形式都是

(2^n)-1

的假设是有效的。参见6.2.6 Representations of Types，特别是6.2.6.2 Integer types，其中无符号整数类型的表示和有符号整数类型的正值完全定义为纯二进制，因此产生的最大值少一比二的幂。

Answer 2

对于

signed

类型，最好只使用所考虑类型的值范围并进行比较。

首先，人们会尝试计算

INT_MAX*INTMAX+INT_MAX

，以便在表达式

a*b+carry

中获得最大可能的值。通过转换为

intmax_t

似乎是更合理的方法：

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

但是，如果

MAX_EXPRESSION

的真实数学值大于

INTMAX_MAX

，我们就会遇到麻烦。所以，让我们做一些数学来解决这个问题。

让我们表示 c = INT_MAX 和 m = INTMAX_MAX。从数学上讲，我们想知道是否

c*c+c <= m

。这导致我们得出不等式：

c <= (m - c) / c

。由于除法是整数，结果被截断，因此在最后一个运算中丢失了精确的数学运算。因此，我们必须写一个更精确的表达式，像这样：`c<= floor((m - c) / c) + fractional_part_of((m - c) / c).

如果

c > floor((m - c) / c)

，严格来说，那么

c >= floor((m - c) / c) + 1 > (m - c) / c

，其中除法是在数学意义上进行的（精确的小数点）。这给了我们

c*c+c > m

，矛盾。因此，我们再次从数学上得出结论

c <= floor((m - c) / c)

。

这个表达式在 C 中更方便，因为 m - c 在使用

intmax_t

类型计算时会给我们一个正确的值（换句话说：它不是 out-of-range 值）。现在，除法

(m - c) / c

将再次为我们提供

intmax_t

范围内的整数，尽管可能会被截断，因为除法是整数。实际上，它毫不犹豫地给了我们

floor((m - c) / c

的价值。

如果这个比较成立，那么我们可以说

c*c+c

可以用您系统的最大有符号整数类型表示，即

intmax_t

。特别是：存在一个有符号整数类型，它能够在您的系统中表示值

c*c+c

。

现在，在C代码中，我们可以写：

  #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  

一旦确定

intmax_t

完成了这项工作，您只需开始搜索具有最小等级的有符号整数类型即可解决问题：我们可以再次问与

intmax_t

相同的问题，例如

 long

和

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