主页 / 问题 / 1139350
Accepted
MGNeo
Asked:2020-06-11 00:49:00 +0800 CST2020-06-11 00:49:00 +0800 CST

无符号整数相乘时是否可以使用 static_assert 检查溢出？

  • 772

考虑以下代码：

static_assert(X > 0);
static_assert(Y > 0);
static_assert(((X * Y) / X) == Y);

WhereX和Y是模板参数，类型为size_t.

此代码应该检查无符号整数的可能溢出（在编译时）。

我的问题是：是否可以保证编译器会首先诚实地计算乘积X * Y，然后才诚实地除以X？

由于X和Y是无符号的，在我看来，编译器必须考虑在可能溢出的情况下失去意义。因此，他必须先乘，再除。但我不确定。

c++

1 个回答

  1. Best Answer

    编译器有权将表达式简化X * Y / X == Y为true当且仅当确定这种简化不会违反程序的可观察行为。

    参见例如[intro.abstract] / 1：

    本文档中的语义描述定义了一个参数化的非确定性抽象机。本文档对一致性实现的结构没有任何要求。特别是，它们不需要复制或模仿抽象机器的结构。相反，需要符合要求的实现来模拟（仅）抽象机的可观察行为，如下所述。四

    4) 这个规定有时被称为“as-if”规则，因为只要从可观察到的情况可以确定，只要结果是好像已经遵守了要求，实现就可以自由地忽略本文档的任何要求程序的行为。例如，如果一个实际的实现可以推断出它的值没有被使用并且没有产生影响程序可观察行为的副作用，那么它就不需要评估表达式的一部分。

    此外，在[expr.pre] / 5中规定了不允许违反程序观察到的行为的优化：

    [注意：实现可以根据通常的数学规则重新组合运算符，仅当运算符真正是关联的或可交换的。51例如，在以下片段中

    int a, b;
/* ... */
a = a + 32760 + b + 5;

    表达式语句的行为与

    a = (((a + 32760) + b) + 5);

    由于这些运算符的关联性和优先级。因此，总和的结果(a + 32760)接下来被添加到b，然后将该结果添加到5分配给 的值的结果中a。在溢出产生异常并且由 an 表示的值范围是的机器int上[-32768, +32767]，实现不能将此表达式重写为

    a = ((a + b) + 32765);

    因为如果和的值分别是a和，求和会产生异常，而原始表达式不会；也不能将表达式重写为b-32754-15a + b

    a = ((a + 32765) + b);

    或者

    a = (a + (b + 32765));

    因为 和 的值a可能b分别是4和-8或-17和12。但是在溢出不会产生异常并且溢出结果是可逆的机器上，上述表达式语句可以由实现以上述任何方式重写，因为将发生相同的结果。--结束注]

    现在让我们处理表达式中的“可观察行为” X * Y / X == Y。让表达式X和Y具有这些表达式的类型unsigned int和值大于零。

    如果乘积X * Y不超过该值UINT_MAX（即没有溢出），则等式X * Y / X == Y为真。
    现在让产品X * Y大于UINT_MAX。如果我们以实数进行计算，那么我们可以写出以下关系：

    `X * Y == k * (UINT_MAX + 1) + r`, где `k >= 1`, `0 <= r <= UINT_MAX`,
(k * (UINT_MAX + 1) + r) / X == Y,
k * (UINT_MAX + 1) / X + r / X == Y.

    但是，无符号整数的计算是根据模运算规则[basic.fundamental] / 2执行的：

    [...]无符号整数类型与相应的有符号整数类型具有相同的宽度N。无符号类型的可表示值范围为0to 2^N − 1（含）；无符号类型的算术是模执行的2^N。[注意：无符号算术不会溢出。有符号算术溢出会产生未定义的行为 (7.1)。--结束注]

    这意味着当溢出时，乘积X * Y将不等于k * (UINT_MAX + 1) + r，而只有r。因此，表达式X * Y / X == Y等价于表达式r / X == Y，即为假（毕竟，当溢出k * (UINT_MAX + 1) / X大于一时，我们只是将其丢弃！）

    X因此，要检查两个非空表达式和Y一个类型相乘时是否没有溢出，unsigned int很有可能使用 check X * Y / X == Y。通常，编译器无权假设这种相等性总是正确的。

    在某些实现中，定义类型值的位数unsigned short是 16，定义类型值的位数int是 32。那么，如果X和Y具有 type unsigned short，那么X * Y / X == Y即使乘积X * Y不能表示为，表达式也可以为真类型unsigned short。

    在计算乘积之前，使用普通算术转换X * Y将二元运算符的算术操作数转换*为通用类型。在这种特殊情况下，泛型类型是.int

    让X和分别Y相等。该值不能由 type 表示，但它完全适合 32 位 type ，并且是这种类型的操作数相乘。然后将该值除以，结果为，显然等于。65535265535 * 2unsigned shortint65535 * 2655352Y

    让X两者Y相等65535。值65535 * 65535不能用 type 表示unsigned short，但也不能用 32 位类型表示int。尽管我们最初将无符号类型的值相乘，但仍会发生未定义的行为——通过正常算术转换将操作数强制转换为的有符号整数类型的溢出。

    类型std::size_t只是其他整数类型的别名。而且语言标准并没有具体说明是哪一种。语言标准允许存在在正常算术转换期间将类型操作数std::size_t转换为有符号整数类型的实现（但是，我无法给出具有这种行为的编译器的单个真实示例）。因此，用表达式检查非溢出X * Y / X == Y是有潜在危险的。

    PS
    您可以使用以下表达式检查 product 是否存在溢出X * Y， whereX和Ytype std::size_t：

    std::numeric_limits<std::size_t>::max() / X >= Y

    如果操作数可以变为零，那么：

    X == 0 || std::numeric_limits<std::size_t>::max() / X >= Y
    • 12

相关问题