¿Por qué es esto un comportamiento indefinido?

Question

¿Por qué es esto un comportamiento indefinido?

Mi respuesta a esta pregunta fue esta función:

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

Funcionó perfectamente en mi máquina con el compilador VS2008, sin embargo aquí no funciona en absoluto.

¿Alguien tiene una idea, por qué obtengo diferentes resultados en diferentes compiladores? unsigned el desbordamiento no es un comportamiento indefinido.

Nota importante: después de algunas pruebas se confirmó que es más rápido que tomar el resto de la división por 15. (Sin embargo no en todos los compiladores)

60

undefined-behavior c

Author: Community, 2013-09-10

Source

2 answers

Dado que está utilizando constantes int, el compilador puede "usar" el desbordamiento es indefinido para abreviar el código. Si modifica con U como se muestra a continuación, "funciona".

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

Probando con:

#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;
    }
    }
}

Salida:

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

Código:

_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

Así que, sí, estoy de acuerdo con el análisis de Carl/Adam de que no encaja en un int de 32 bits, por lo tanto promovido a long o long long.

9

Author: Mats Petersson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-09-09 21:21:56

score 98 · Accepted Answer

No es un Comportamiento Indefinido, es solo un cambio radical en el estándar del lenguaje C entre C89 y C99.

En C89, las constantes enteras como 4008636143 que no caben en un int o long int pero caben en un unsigned int no tienen signo, pero en C99, son long int o long long int (dependiendo del que sea el más pequeño que pueda contener el valor). Como resultado, todas las expresiones se evalúan usando 64 bits, lo que resulta en la respuesta incorrecta.

Visual Studio es un C89 el compilador y así resulta en el comportamiento de C89, pero ese enlace de Ideone está compilando en modo C99.

Esto se hace más evidente si compilas con GCC usando -Wall:

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

De C89 §3.1.3.2:

El tipo de una constante entera es la primera de las lista en la que se puede representar su valor. Decimal sin fijar: int, long int, unsigned long int; octal o hexadecimal no fijado: int, unsigned int, long int, unsigned long int; [...]

C99 §6.4.4.1 / 5-6:

5) El tipo de una constante entera es la primera de la lista correspondiente en la que su valor puede estar representado.
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) Si una constante entera no puede ser representada por ningún tipo en su lista, puede tener una tipo entero extendido, si el tipo entero extendido puede representar su valor. Si todos los los tipos en la lista para la constante están firmados, el tipo entero extendido debe estar firmado. [...]

Para completar, C++03 realmente tiene un Comportamiento Indefinido para cuando la constante entera es demasiado grande para caber en un long int. De C++03 §2.13.1/2:

El tipo de un literal entero depende de su forma, valor y sufijo. Si es decimal y no tiene sufijo, tiene el primero de estos tipos en el que se puede representar su valor: int, long int; si el valor no se puede representar como long int, el comportamiento es indefinido. Si es octal o hexadecimal y no tiene sufijo, tiene el el primero de estos tipos en el que se puede representar su valor: int, unsigned int, long int, unsigned long int. [...]

El comportamiento de C++11 es idéntico al de C99, véase C++11 §2.14.2/3.

Para asegurarse de que el código se comporta consistentemente cuando se compila como C89, C99, C++03 y C++11, la solución simple es hacer que la constante 4008636143 no tenga signo mediante el sufijo u como 4008636143u.