Pregunta C ++ se bloquea en un bucle 'for' con una expresión negativa


El siguiente código bloquea C ++ con un error de tiempo de ejecución:

#include <string>

using namespace std;

int main() {
    string s = "aa";
    for (int i = 0; i < s.length() - 3; i++) {

    }
}

Si bien este código no falla:

#include <string>

using namespace std;

int main() {
    string s = "aa";
    int len = s.length() - 3;
    for (int i = 0; i < len; i++) {

    }
}

Simplemente no tengo ni idea de cómo explicarlo. ¿Cuál podría ser el motivo de este comportamiento?


55
2017-07-01 06:59


origen


Respuestas:


s.length() es un tipo entero sin signo. Cuando resta 3, lo hace negativo. Por un unsigned, significa muy grande.

Una solución temporal (válida siempre que la cadena sea larga hasta INT_MAX) sería hacer esto:

#include <string>

using namespace std;

int main() {

    string s = "aa";

    for (int i = 0; i < static_cast<int> (s.length() ) - 3; i++) {

    }
}

Lo cual nunca entraría en el ciclo.

Un detalle muy importante es que probablemente haya recibido una advertencia de "comparación de valores firmados y no firmados". El problema es que si ignoras esas advertencias, ingresas al campo muy peligroso de implícito  "conversión de enteros"(*), que tiene un comportamiento definido, pero es difícil de seguir: lo mejor es nunca ignorar las advertencias del compilador.


(*) También te puede interesar saber sobre "promoción de enteros".


85
2017-07-01 07:05



Ante todo: por qué ¿se cuelga? Pasemos por su programa como lo haría un depurador.

Nota: Asumiré que su cuerpo de bucle no está vacío, pero accede a la cadena. Si este no es el caso, la causa del bloqueo es comportamiento indefinido a través del desbordamiento de enteros. Vea la respuesta de Richard Hansens para eso.

std::string s = "aa";//assign the two-character string "aa" to variable s of type std::string
for ( int i = 0; // create a variable i of type int with initial value 0 
i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK!
{...} // execute loop body
i++ // do the incrementing part of the loop, i now holds value 1!
i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK!
{...} // execute loop body
i++ // do the incrementing part of the loop, i now holds value 2!
i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK!
{...} // execute loop body
i++ // do the incrementing part of the loop, i now holds value 3!
.
.

Es de esperar que el cheque i < s.length() - 3 fallar de inmediato, ya que la duración de s es dos (solo le dimos una longitud al principio y nunca lo cambiamos) y 2 - 3 es -1, 0 < -1 Es falso. Sin embargo, obtenemos un "OK" aquí.

Esto es porque s.length() no es 2. Sus 2u. std::string::length() tiene tipo de retorno size_t que es un entero sin signo. Volviendo al estado de bucle, primero obtenemos el valor de s.length(), asi que 2u, ahora resta 3. 3 es un entero literal e interpretado por el compilador como tipo int. Entonces el compilador tiene que calcular 2u - 3, dos valores de diferentes tipos. Las operaciones en tipos primitivos solo funcionan para los mismos tipos, por lo que uno tiene que convertirse en el otro. Hay algunas reglas estrictas, en este caso, unsigned "gana", entonces 3 get's convertido a 3u. En enteros sin signo, 2u - 3u no puede ser -1u como tal, un número no existe (bueno, ¡porque tiene un signo, por supuesto!). En cambio, calcula cada operación modulo 2^(n_bits), dónde n_bits es el número de bits en este tipo (generalmente 8, 16, 32 o 64). Entonces, en lugar de -1 obtenemos 4294967295u (suponiendo 32 bits).

Así que ahora el compilador está hecho con s.length() - 3 (por supuesto, es mucho más rápido que yo ;-)), ahora vamos a la comparación: i < s.length() - 3. Poniendo en los valores: 0 < 4294967295u. De nuevo, diferentes tipos, 0 se convierte 0u, la comparación 0u < 4294967295u es obviamente cierto, la condición de bucle está comprobada positivamente, ahora podemos ejecutar el cuerpo del bucle.

Después de incrementar, lo único que cambia en lo anterior es el valor de i. El valor de i se volverá a convertir en una int sin firmar, ya que la comparación lo necesita.

Entonces tenemos

(0u < 4294967295u) == true, let's do the loop body!
(1u < 4294967295u) == true, let's do the loop body!
(2u < 4294967295u) == true, let's do the loop body!

Aquí está el problema: ¿qué haces en el cuerpo del bucle? Presumiblemente usted acceso el i^th carácter de su cadena, ¿no? Aunque no era tu intención, no solo accediste al zeroth primero, sino también al segundo. El segundo no existe (como su cadena solo tiene dos caracteres, el zeroth y el primero), accede a la memoria que no debería, el programa hace lo que quiere (comportamiento indefinido). Tenga en cuenta que no es necesario que el programa se bloquee inmediatamente. Puede parecer que funciona bien durante otra media hora, por lo que estos errores son difíciles de detectar. Pero siempre es peligroso acceder a la memoria más allá de los límites, aquí es de donde provienen la mayoría de los accidentes.

En resumen, obtienes un valor diferente de s.length() - 3 a partir de eso, como se esperaría, esto da como resultado una verificación de condición de bucle positiva, que conduce a la ejecución repetitiva del cuerpo del bucle, que en sí mismo accede a la memoria, no debería hacerlo.

Ahora veamos cómo evitar eso, es decir, cómo decirle al compilador lo que realmente quiso decir en su condición de bucle.


Las longitudes de las cadenas y los tamaños de los contenedores son intrínsecamente no firmado por lo que debe usar un entero sin signo para los bucles.

Ya que unsigned int es bastante largo y, por lo tanto, no es deseable escribir una y otra vez en bucles, solo use size_t. Este es el tipo que usa cada contenedor en el STL para almacenar longitud o tamaño. Es posible que necesite incluir cstddef para afirmar la independencia de la plataforma.

#include <cstddef>
#include <string>

using namespace std;

int main() {

    string s = "aa";

    for ( size_t i = 0; i + 3 < s.length(); i++) {
    //    ^^^^^^         ^^^^
    }
}

Ya que a < b - 3 es matemáticamente equivalente a a + 3 < b, podemos intercambiarlos. Sin embargo, a + 3 < b previene b - 3 ser un gran valor Recordar que s.length() devuelve un entero sin signo y los enteros sin signo realizan el módulo de operaciones 2^(bits) donde bits es la cantidad de bits en el tipo (generalmente 8, 16, 32 o 64). Por lo tanto con s.length() == 2, s.length() - 3 == -1 == 2^(bits) - 1.


Alternativamente, si quieres usar i < s.length() - 3 para preferencia personal, debe agregar una condición:

for ( size_t i = 0; (s.length() > 3) && (i < s.length() - 3); ++i )
//    ^             ^                    ^- your actual condition
//    ^             ^- check if the string is long enough
//    ^- still prefer unsigned types!

28
2017-07-01 08:31



En realidad, en la primera versión bucle durante mucho tiempo, a medida que compara i a una no firmado  número entero que contiene un número muy grande. El tamaño de una cuerda es (en efecto) el mismo que size_t que es un entero sin signo. Cuando restas el 3 de ese valor se desborda y pasa a ser un gran valor.

En la segunda versión del código, asigna este valor sin firmar a una variable con signo, y así obtiene el valor correcto.

Y no es realmente la condición o el valor que causa el bloqueo, es más probable que indexe la cadena fuera de límites, un caso de comportamiento indefinido.


12
2017-07-01 07:04



Asumiendo que omitiste un código importante en el for lazo

La mayoría de las personas aquí parecen incapaces de reproducir el bloqueo, incluido yo mismo, y parece que las otras respuestas aquí se basan en la suposición de que omitiste algún código importante en el cuerpo del for loop, y que el código faltante es lo que está causando su bloqueo.

Si estás usando i para acceder a la memoria (supuestamente caracteres en la cadena) en el cuerpo del for en bucle, y dejaste ese código fuera de tu pregunta en un intento de proporcionar un ejemplo mínimo, entonces el bloqueo se explica fácilmente por el hecho de que s.length() - 3tiene el valor SIZE_MAX debido a la aritmética modular en tipos enteros sin signo. SIZE_MAX es un número muy grande, entonces i seguirá creciendo hasta que se use para acceder a una dirección que desencadena una segfault.

Sin embargo, su código podría colapsar teóricamente tal como está, incluso si el cuerpo del for el bucle está vacío. No conozco ninguna implementación que se bloquee, pero tal vez su compilador y CPU son exóticos.

La siguiente explicación no supone que omitió el código en su pregunta. Da fe de que el código que publicaste en tu pregunta falla como está; que no es un sustituto abreviado de otro código que se cuelga.

Por qué su primer programa se bloquea

Tu primer programa se bloquea porque esa es su reacción al comportamiento indefinido en tu código. (Cuando intento ejecutar tu código, termina sin fallar porque esa es la reacción de mi implementación al comportamiento indefinido).

El comportamiento indefinido proviene del desbordamiento de un int. El estándar C ++ 11 dice (en [expr] cláusula 5 párrafo 4):

Si durante la evaluación de una expresión, el resultado no está matemáticamente definido o no está en el rango de valores representables para su tipo, el comportamiento no está definido.

En tu programa de ejemplo, s.length() devuelve un size_t con valor 2. Restar 3 de eso produciría 1 negativo, excepto size_t es un tipo entero sin signo. El estándar C ++ 11 dice (en [basic.fundamental] cláusula 3.9.1 párrafo 4):

Enteros sin signo, declarados unsigned, obedecerá las leyes del módulo aritmético 2norte dónde norte es el número de bits en la representación del valor de ese tamaño particular de número entero.46

46) Esto implica que la aritmética sin signo no se desborda porque un resultado que no puede ser representado por el tipo de entero sin signo resultante es módulo reducido el número que es uno mayor que el valor más grande que puede representarse por el tipo de entero sin signo resultante.

Esto significa que el resultado de s.length() - 3 es un size_t con valor SIZE_MAX. Este es un número muy grande, más grande que INT_MAX (el mayor valor representable por int)

Porque s.length() - 3 es tan grande, la ejecución gira en el ciclo hasta i llega a INT_MAX. En la siguiente iteración, cuando intenta incrementar i, el resultado sería INT_MAX + 1 pero eso no está en el rango de valores representables para int. Por lo tanto, el comportamiento no está definido. En tu caso, el comportamiento es bloquearse.

En mi sistema, el comportamiento de mi implementación cuando i se incrementa pasado INT_MAX es envolver (establecer i a INT_MIN) y sigue adelante. Una vez i alcanza -1, las conversiones aritméticas usuales (C ++ [expr] cláusula 5 párrafo 9) causa i A igual SIZE_MAX por lo que el ciclo termina.

Cualquiera de las reacciones es apropiada. Ese es el problema con el comportamiento indefinido: podría funcionar como usted pretende, podría colapsar, podría formatear su disco duro, o podría cancelar Firefly. Nunca sabes.

Cómo evita su segundo programa el bloqueo

Al igual que con el primer programa, s.length() - 3 es un size_t escribe con valor SIZE_MAX. Sin embargo, esta vez el valor está siendo asignado a un int. El estándar C ++ 11 dice (en [conv.integral] cláusula 4.7 párrafo 3):

Si el tipo de destino está firmado, el valor no se modifica si se puede representar en el tipo de destino (y el ancho del campo de bits); de lo contrario, el valor está definido por la implementación.

El valor SIZE_MAX es demasiado grande para ser representable por un int, asi que len obtiene un valor definido por la implementación (probablemente -1, pero tal vez no). La condición i < len eventualmente será cierto independientemente del valor asignado a len, por lo que su programa terminará sin encontrar ningún comportamiento indefinido.


5
2017-07-02 23:03



El tipo de s.length () es size_t con un valor de 2, por lo tanto, s.length () - 3 también es un tipo sin signo size_t y tiene un valor de SIZE_MAX que es la implementación definida (que es 18446744073709551615 si su tamaño es de 64 bits). Tiene al menos un tipo de 32 bits (puede ser de 64 bits en plataformas de 64 bits) y este alto número significa un ciclo indefinido. Para evitar este problema, simplemente puedes lanzar s.length() a int:

for (int i = 0; i < (int)s.length() - 3; i++)
{
          //..some code causing crash
}

En el segundo caso len es -1 porque es un signed integer y no entra al circuito

Cuando se trata de colisionar, este bucle "infinito" no es la causa directa del bloqueo. Si comparte el código dentro del ciclo, puede obtener una explicación más detallada.


3
2017-07-01 07:03



Como s.length () es cantidad de tipo sin signo, al hacer s.length () - 3, se vuelve negativo y los valores negativos se almacenan como valores positivos grandes (debido a especificaciones de conversión sin firmar) y el ciclo se vuelve infinito y, por lo tanto, falla .

Para hacer que funcione, debe encasillar el s.length () como:

static_cast <int> (s.length ())


1
2017-07-01 12:00



El problema que está teniendo surge de la siguiente declaración:

i < s.length() - 3

El resultado de s.length () es del no firmado size_t tipo. Si imaginas la representación binaria de dos:

0 ... 010

Y a continuación, sustituye tres de esto, efectivamente está sacando 1 tres veces, es decir:

0 ... 001

0 ... 000

Pero luego tienes un problema, eliminando el tercer dígito que tiene subdesbordamiento, ya que intenta obtener otro dígito de la izquierda:

1 ... 111

Esto es lo que sucede sin importar si tiene un no firmado o firmado tipo, sin embargo, la diferencia es la firmado tipo utiliza el bit más significativo (o MSB) para representar si el número es negativo o no. Cuando ocurre el desbordamiento, simplemente representa un negativo para el firmado tipo.

Por otro lado, size_t es no firmado. Cuando se desborda, ahora representará el número más grande que posiblemente pueda representar. Por lo tanto, el ciclo es prácticamente infinito (Dependiendo de su computadora, ya que esto afecta al máximo de size_t).

Para solucionar este problema, puede manipular el código que tiene de diferentes maneras:

int main() {
    string s = "aa";
    for (size_t i = 3; i < s.length(); i++) {

    }
}

o

int main() {
    string s = "aa";
    for (size_t i = 0; i + 3 < s.length(); i++) {

    }
}

o incluso:

int main() {
    string s = "aa";
    for(size_t i = s.length(); i > 3; --i) {

    }
}

Lo importante a tener en cuenta es que la sustitución se ha omitido y, en su lugar, la adición se ha utilizado en otras partes con las mismas evaluaciones lógicas. Tanto el primero como el último cambian el valor de ique está disponible dentro de la for loop mientras que el segundo lo mantendrá igual.

Estuve tentado de proporcionar esto como un ejemplo de código:

int main() {
    string s = "aa";
    for(size_t i = s.length(); --i > 2;) {

    }
}

Después de pensarlo un poco, me di cuenta de que era una mala idea. ¡El ejercicio de los lectores es averiguar por qué!


1
2017-07-01 13:22



La razón es la misma que int a = 1000000000; long long b = a * 100000000; daría error Cuando los compiladores multiplican estos números, lo evalúan como enteros, ya que a y literal 1000000000 son enteros, y dado que 10 ^ 18 es mucho más grande que el límite superior de int, dará error. En su caso, tenemos s.length () - 3, ya que s.length () no tiene signo int, no puede ser negativo, y como s.length () - 3 se evalúa como unsigned int, y su valor es -1, da error aquí también.


0
2018-03-22 20:48



Preguntas populares