如何确定整数类型的宽度是`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()的有用性）和非二进制补码整数（限制了位操作），...

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

---

#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有效，那么int2x是否会被正确地输入？

注：以上假设xxx_MAX是某些奇数2的幂减1。这可能是一个好的假设吗？以上在至少两个平台上运行良好，但这并不是很好的可移植性测试。

- chux - Reinstate Monica

---

对于这个有趣的问题，我给一个赞，但是为了得到一个“合理的解决方案”和“完全可移植性”，为什么不一直采用 long long 来保险呢？毕竟你最后还是要将其强制转换回 int，那么在中间变量上节省开销又有什么意义呢？ - barak manos

不，它没有涵盖奇怪的可能性。它并没有说一定存在你正在寻找的那种类型。我会将 INT_MAX 与 INT16_MAX 和 INT32_MAX 进行比较，以确定 int 是 16 还是 32 位宽度。然后分别为 int2x 使用 int_least32_t 或 int_least64_t。 - Jens Gustedt

这似乎是徒劳无功的练习；如果您想要可重复的数学运算，为什么不直接使用明确大小的类型（int16_t等）呢？ - Oliver Charlesworth

请注意，问题不一定是可解的。特别地，int、long和long long都可以完全相同的大小（只要它们是64位或更大）。在这种情况下，您可以自己将乘法分解为半大小的单元，而不是使用#error。 - R.. GitHub STOP HELPING ICE

@Jens Gustedt 1）请提供一个失败的“怪异可能性”示例。2）#else #error难道不能捕获“类型...必须存在。”吗？3）考虑使用UINT16_MAX/UINT32_MAX方法，但这会导致预处理器出现问题。应该重新考虑INT16_MAX/INT32_MAX方法。除了它无法处理18/36位int和其他非2次幂宽度之外，它似乎更为直接，我认为这些在今天很少见，但我不确定。 - chux - Reinstate Monica

Answer 1

假设所有的*_MAX常量都是形如(2^n)-1的，这是可行的。详见6.2.6 类型的表示，特别是6.2.6.2 整数类型，其中定义了无符号整数类型和有符号整数类型的正数值是纯二进制表示，因此得到的最大值比二的幂小一。

- R.. GitHub STOP HELPING ICE

---

我本希望能获得一个更清晰地回答该帖子的答案，但是徒劳无功。由于这个答案更清晰地回答了帖子的某些部分，因此奖励你50点。 - chux - Reinstate Monica

赏金似乎不像以前那样突出显示了。我已经很长时间没有注意到赏金了... :-( - R.. GitHub STOP HELPING ICE

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中，这个表达式更方便，因为当使用类型intmax_t计算时，m - c将给我们一个正确的值（换句话说：它不是一个超出范围的值）。现在，除法(m - c) / c将再次给我们一个intmax_t范围内的整数，尽管可能被截断，因为除法是整数。实际上，它毫不犹豫地给出了floor((m - c) / c)的值。

如果这个比较返回 true，那么我们可以说 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

- pablo1977

---

想法：INT_MIN*INT_MIN + INT_MAX难道不可能比INT_MAX*INT_MAX+INT_MAX更大吗？ - chux - Reinstate Monica

可以的。嗯...也许如果我在答案结尾添加一条关于这个问题的注释就足够了。 - pablo1977

但是，那么大的值不会影响其余方程式吗？以至于它们与后面的差别很小？ - chux - Reinstate Monica

可能负值需要另一种分析。我现在无法做到这一点，稍后我会考虑。 - pablo1977