为什么这是未定义行为？

Question

我对这个问题的回答是这个函数:

inline bool divisible15(unsigned int x) 
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143 <= 286331153;
}

在我的机器上，使用VS2008编译器它完美地工作了，但是这里它根本不起作用。

有人知道为什么在不同的编译器上会得到不同的结果吗？unsigned溢出不是未定义行为。

重要说明：经过一些测试，确认这比对15取余数更快。（但并非在所有编译器上）

- ST3

---

这比(x % 15) == 0更快吗？ - asveikau

这对我来说并不显示为未定义行为？但它很可能是整数溢出。 - PherricOxide

x * 4008636143 能否适应 int 类型？ - andre

好的，这些是“未签名”的整数。溢出行为已经被指定。 - Mysticial

为了更易读，我认为这个代码可以改写成 return x * -(UINT_MAX / 15) <= (UINT_MAX / 15);，这样就能完美避免整个问题了。当我试图理解原来的代码时感到困惑，但当我意识到它可以被改写成这样后，我就明白了它为什么能工作 :) （注：像你的代码一样，这种写法显然假定了 UINT_MAX 的特定值）。 - user743382

Answer 1

在C语言标准的C89和C99之间，存在一个变化，这不是未定义行为，而只是一个破坏性的变化。在C89中，像4008636143这样的整数常量如果放在int或long int里会溢出，但放在unsigned int里则被视为无符号数；但在C99中，这些常量会被视为long int或long long int（哪个类型可以容纳该值就选哪个）。结果，所有表达式都将使用64位来计算，从而导致不正确的答案。

Visual Studio是C89编译器，因此采用C89的行为，但Ideone链接是使用C99模式编译的。

如果使用GCC编译并加上-Wall选项，这一点将变得更为明显:

test.c: In function ‘divisible15’:
test.c:8:3: warning: this decimal constant is unsigned only in ISO C90

C89 §3.1.3.2规定：

整数常量的类型是相应列表中可以表示其值的第一个类型。无后缀的十进制数：int、long int、unsigned long int；无后缀的八进制数或十六进制数：int、unsigned int、long int、unsigned long int; [...]

C99 §6.4.4.1/5-6规定：

5) 整数常量的类型是相应列表中可以表示其值的第一个类型。

Suffix | Decimal Constant | Octal or Hexadecimal Constant
-------+------------------+------------------------------
none   | int              | int
       | long int         | unsigned int
       | long long int    | long int
       |                  | unsigned long int
       |                  | long long int
       |                  | unsigned long long int
-------+------------------+------------------------------
[...]

6) 如果一个整数常量在其列表中没有任何类型能够表示它，那么它可以有扩展整数类型，只要扩展整数类型能够表示它的值。如果常量的类型列表中所有类型都是带符号的，则扩展整数类型必须是带符号的。[...]

为了完整起见，C++03实际上对于当整数常量太大无法适应long int时具有未定义行为。来自C++03 §2.13.1/2：

整型字面量的类型取决于其形式、值和后缀。如果它是十进制的并且没有后缀，则它具有以下类型中的第一个，其值可以表示为： int，long int；如果该值不能表示为long int，则行为未定义。如果它是八进制或十六进制且没有后缀，则它具有以下类型中的第一个，其值可以表示为：int，unsigned int，long int，unsigned long int。[...]

C++11的行为与C99相同，参见C++11 §2.14.2/3。

为了确保代码在编译为C89、C99、C++03和C++11时的行为一致，简单的修复方法是通过在4008636143后加上u来使常量无符号化，即4008636143u。

- Adam Rosenfield

---

+1；作为补充，在C++中，没有后缀的十进制常量始终是有符号的（即使在C++03中也是如此）。 - avakar

Answer 2

由于您正在使用 int 常量，编译器可以利用未定义的溢出来捷径代码。如果您按照以下方式使用 U 进行修改，则“有效”。

inline bool divisible15(unsigned int x) 
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143u <= 286331153u;
}

测试使用：

#include <iostream>


inline bool divisible15a(unsigned int x) 
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
//    return x * 4008636143 <= 286331153;
    return x * 4008636143u <= 286331153;
}

inline bool divisible15b(unsigned int x) 
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
//    return x * 4008636143 <= 286331153;
    return x * 4008636143 <= 286331153;
}


int main()
{
    for(unsigned int i = 0; i < 100; i++)
    {
    if (divisible15a(i))
    {
        std::cout << "a:" << i << std::endl;
    }
    if (divisible15b(i))
    {
        std::cout << "b:" << i << std::endl;
    }
    }
}

输出：

a:0
b:0
a:15
a:30
a:45
a:60
a:75
a:90

代码：

_Z12divisible15aj:
.LFB1192:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    imull   $-286331153, %eax, %eax
    cmpl    $286331153, %eax
    setbe   %al
    popq    %rbp
    ret

_Z12divisible15bj:
.LFB1193:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %edx
    movl    $4008636143, %eax
    imulq   %rdx, %rax
    cmpq    $286331153, %rax
    setle   %al
    popq    %rbp
    ret

所以，是的，我同意Carl/Adam的分析，它无法适应32位整数，因此被提升为long或long long。

- Mats Petersson

---

默认的整数提升已经使其正确运行了，对吧？如果有一个太大的常量，它会自动“升级”，我记得是这样的吧？ - Carl Norum

至少在使用'u'和不使用它之间，g++ 4.6.3的行为似乎有所不同。当然可能是一个错误。 - Mats Petersson

clang也是一个选择。再考虑一下。 - Carl Norum

@CarlNorum：啊哈，问题是没有 u，字面量被解释为 signed long，因此 x 也被提升为 signed long 了？ - Oliver Charlesworth

或者 long long，是的。 - Carl Norum