59

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

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

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

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

重要提示：经过一些测试，确认它比除以 15 的其余部分更快。（但并非在所有编译器上）

4

2 回答 2

98

这不是未定义的行为，它只是 C89 和 C99 之间 C 语言标准的一个重大变化。

在 C89 中，像 4008636143 这样不适合 anint或long int但适合 an的整数常量unsigned int是无符号的，但在 C99 中，它们是long intor 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) 如果一个整数常量不能用它的列表中的任何类型表示，它可能有一个扩展的整数类型，如果扩展的整数类型可以表示它的值。如果常量列表中的所有类型都带符号，则扩展整数类型应带符号。[...]

为了完整起见，当整数常量太大而无法放入long int. 从 C++03 §2.13.1/2 开始：

整数文字的类型取决于它的形式、值和后缀。如果它是十进制且没有后缀，则它具有以下类型中的第一个，可以在其中表示其值：int, long int; 如果该值不能表示为 a 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 时的行为一致，简单的解决方法是通过使用uas后缀将常量 4008636143 设为无符号4008636143u。

于 2013-09-09T21:11:43.823 回答
9

由于您使用的是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 位 int，因此提升为longor long long。

于 2013-09-09T21:07:08.517 回答