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 言語標準の重大な変更です。

intC89 では、4008636143 のようにorには収まらないが、にはlong int収まる整数定数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 から:

整数定数の型は、その値を表すことができる対応するリストの最初のものです。接尾辞なしの 10 進数: int、long int、unsigned long int; 接尾辞なしの 8 進数または 16 進数: 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 には実際には、整数定数が大きすぎて a に収まらない場合の未定義の動作がありlong intます。C++03 §2.13.1/2 から:

整数リテラルの型は、その形式、値、および接尾辞によって異なります。10 進数で接尾辞がない場合は、値を表すことができる次の型の最初のものを持ちます: int, long int; 値を として表すことができない場合long int、動作は未定義です。8 進数または 16 進数で接尾辞がない場合は、値を表すことができる最初の型 ( 、 、 、 )intをunsigned int持ちlong intますunsigned long int。[...]

C++11 の動作は C99 と同じです。C++11 §2.14.2/3 を参照してください。

C89、C99、C++03、および C++11 としてコンパイルされたときにコードが一貫して動作するようにするには、簡単な修正として、定数 4008636143 の末尾に as を付けて符号なしにしuます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

したがって、はい、32 ビットの int に収まらないため、longorに昇格するという Carl/Adam の分析に同意しlong longます。

于 2013-09-09T21:07:08.517 に答える