仅使用整数常量表达式计算 sqrt(SIZE_MAX+1)，以适应奇怪的 ABI

Question

OpenBSD 的 C 库有一个名为 reallocarray(3) 的扩展名哪个realloc(array, size*nmemb)如果乘法溢出而不会爆炸。 The implementation包含此片段:

/*
 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
 */
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))

Over on Programmers.SE该计算的修改版本因技术错误而受到影响。 4显然应该是 CHAR_BIT/2 ，但这不是唯一的问题。假设一个不寻常的 ABI，其中 size_t有填充位。 (这并非难以置信:考虑一个具有 32 位寄存器但具有 24 位地址空间的微 Controller 。)那么 SIZE_MAX小于 1 << (sizeof(size_t)*CHAR_BIT) [无限精度算术] 计算错误。

所以，问题:你能计算出floor(sqrt(SIZE_MAX+1))吗？仅使用 C99 整数常量表达式算法，不对 ABI 做任何假设，除了 C99 要求的内容以及您可以从中学到的内容 <limits.h> ？注意 SIZE_MAX可能等于 UINTMAX_MAX ，即可能没有任何类型可以表示 SIZE_MAX+1没有溢出。

编辑:我认为 SIZE_MAX对于某个正整数 n 要求为 2ⁿ − 1，但不一定必须是 2²ⁿ − 1 — 考虑 S/390，其中一个 ABI 具有 31 位地址空间。因此:如果sqrt(SIZE_MAX+1)不是整数，则所需结果(给定此常量的使用方式)为 floor()的真实值(value)。

Answer 1

常量 SIZE_MAX是非负的，类型为 size_t .为简短起见，我将定义:

  #define S SIZE_MAX  

数学值S+1正如您所指出的，超出或可能超出任何整数类型的范围。
我会写 S1对于 S+1 的数学值.
如果我们考虑 S1 的对数(如果需要，以 2 为底) ，那么我们有:

 logarithm(sqrt(S1)) == (1.0/2.0) logarithm(S1)

另一方面，在几乎可以肯定的每种现实情况下，我们都会有 S表示为只有 1 的二进制数位。编号b通常，这些位的数量是 CHAR_BIT乘以 2 的幂，乘以 CHAR_BIT:16、32、64、128...我将用 p 表示该幂的指数.因此，对于 CHAR_BIT == 8，我们有:

16 == CHAR_BIT * 2 ----> p == 1
32 == CHAR_BIT * 4 ----> p == 2
64 == CHAR_BIT * 8 ----> p == 3

现在我们有:

logarithm(S1) == b == CHAR_BIT * (2 ** p)   (I am denoting with ** to the "power math. operator").

logarithm(sqrt(S1)) == logaritm(S1) / 2.0 == CHAR_BIT * (2 ** p) / 2.0 == CHAR_BIT * (2 ** (p - 1))

通过假设或知道 size_t 中的每一位仅用于表示整数的位，我们有这个等式，对于 p 的一些(未知)值:

sizeof(size_t) == b == CHAR_BIT * (2 ** p)

我们可以假设，对于 2014 年的最先进技术，p <= 5 的值，说(你可以在下面将这个神奇的数字 5 增加到更大的值)。

现在，考虑以下表达式，旨在“搜索并找到”b 的值，假设p <= 5 :

#define S_1 ((size_t)1ULL)
#define b (sizeof(size_t))
#define bitexpr(p) ((size_t)(CHAR_BIT * (S_1 << (p))))
#define expr(p) ((size_t) (S_1 << (p)))
#define exp2_expr_1(p) ((size_t)(S_1 << bitexpr(p-1)))
// SRSM() stands for: Square Root SizeMax
#define SRSM  ( \
    (expr(1)==b)? exp2_expr_1(1) :             \
        (expr(2)==b)? exp2_expr_1(2) :         \
            (expr(3)==b)? exp2_expr_1(3) :     \
              (expr(4)==b)? exp2_expr_1(4) :   \
                (expr(5)==b)? exp2_expr_1(5) : \
                   (size_t)0  /* Error! */     \
    ) /* end-of-macro*/

宏SRSM实际上，带来了 S+1 的平方根，但我想你可以弄清楚如何处理这个数字。

这里重要的是 SIZE_MAX 的平方根可以通过使用纯整数常量表达式 获得。

如果你愿意，“神奇”的数字 5 可以换成另一个。

一种更通用的方法，旨在解决任意情况，在任何符合标准的可能机器上，它会更复杂。
这篇文章中使用的方法与具有 CHAR_BIT 的值无关, 但它使用字节数是 2 的幂。

已编辑:我稍微更改了“搜索”的方法，从 1 开始，然后逐渐增加，以避免与 << 可能出现的“错误”匹配。运算符和大数字(一个人永远不知道...)。现在，第一场比赛肯定是正确的。