c++ - ¿Por qué es esto un comportamiento indefinido?

undefined-behavior

Question

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, pero aquí no funciona en absoluto.

¿Alguien tiene una idea, por qué obtengo resultados diferentes en diferentes compiladores? unsigned desbordamiento unsigned 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)

Answer 1

Como está utilizando constantes int , el compilador puede "usar" el desbordamiento para definir el atajo. Si modificas con U como 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

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

Answer 2

No es un comportamiento indefinido, es solo un cambio radical en el estándar de lenguaje C entre C89 y C99.

En C89, las constantes enteras como 4008636143 que no encajan en int o long int pero que encajan en un unsigned int sin signo no están firmadas, pero en C99, son long int o long long int (dependiendo de cuál sea la más pequeña) eso puede contener el valor). Como resultado, todas las expresiones se evalúan utilizando 64 bits, lo que da como resultado una respuesta incorrecta.

Visual Studio es un compilador C89 y, por lo tanto, da como resultado el comportamiento C89, pero ese enlace Ideone se está compilando en modo C99.

Esto se vuelve más evidente si compila 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 la lista correspondiente en la que se puede representar su valor. Decimales no reagrupados: int, long int, unsigned long int; unsuffixed octal o hexadecimal: 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 se puede representar su valor.

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 un tipo entero extendido, si el tipo entero extendido puede representar su valor. Si se firman todos los tipos en la lista para la constante, se firmará el tipo entero extendido. [...]

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 entero literal depende de su forma, valor y sufijo. Si es decimal y no tiene sufijo, tiene el primero de estos tipos en que se puede representar su valor: int , long int ; si el valor no se puede representar como un long int , el comportamiento no está definido. Si es octal o hexadecimal y no tiene sufijo, tiene el primero de estos tipos en que se puede representar su valor: int , unsigned int , long int , unsigned long int . [...]

El comportamiento de C ++ 11 es idéntico a C99, ver C ++ 11 §2.14.2 / 3.

Para asegurarse de que el código se comporta de manera consistente cuando se compila como C89, C99, C ++ 03 y C ++ 11, la solución simple es hacer que la constante 4008636143 no sea firmada al sufijo con u como 4008636143u .