En C++, ¿por qué true && true || false && false== true?

boolean-logic short-circuiting (12)

Me gustaría saber si alguien sabe la forma en que un compilador interpretaría el siguiente código:

#include <iostream> using namespace std; int main() { cout << (true && true || false && false) << endl; // true }

¿Es esto cierto porque && tiene una precedencia más alta que || o porque || es un operador de cortocircuito (en otras palabras, ¿un operador de cortocircuito ignora todas las expresiones subsiguientes, o simplemente la siguiente expresión)?

"Si se produce un cortocircuito en el operador || y se cortocircuita la ejecución de la segunda expresión &&, eso significa que el operador || se ejecutó ANTES del segundo operador &&. Esto implica una ejecución de izquierda a derecha para && y || ( no && precedencia).

No exactamente.

(xx && yy || zz && qq)

Sería evaluado así:

Compruebe el primer operador.
Evaluar xx && yy
Compruebe el siguiente operador.
Si el siguiente operador es || y la primera parte de la declaración es verdadera, omita el resto.
De lo contrario, compruebe el siguiente operador después de || , y evaluarlo: zz && qq
Finalmente, evaluar || .

A mi entender, C ++ está diseñado para que lea las cosas antes de que comience a evaluar. Después de todo, en nuestro ejemplo, no sabe que tenemos un segundo control de && después de || hasta que lo lea, lo que significa que tiene que leer en el || antes de que llegue al segundo && . Como tal, si la primera parte se evalúa como verdadera, no hará la parte después de la || , pero si la primera parte se evalúa como falsa, entonces hará la primera parte, lea el || , encuentre y evalúe la segunda parte, y use el resultado de la segunda parte para determinar el resultado final.

(true && true || false && false) se evalúa con && teniendo mayor prioridad.

TRUE && TRUE = True FALSE && FALSE = False True || False = True

Actualizar:

1&&1||infiniteLoop()&&infiniteLoop()

¿Por qué esto produce verdadero en C ++?

Como antes, separémoslo. && tiene mayor prioridad que || y las declaraciones booleanas cortocircuito en C ++.

1 && 1 = True.

Cuando un valor bool se convierte en un valor entero, entonces

false -> 0 true -> 1

La expresión evalúa esta declaración (verdadera) && (verdadera), que provoca un cortocircuito en la ||, lo que impide que se ejecuten los bucles infinitos. Hay mucho más compilador de Juju en marcha, así que esta es una visión simplista de la situación que es adecuada para este ejemplo.

En un entorno sin cortocircuito, esa expresión se colgaría para siempre porque ambos lados del OR serían "evaluados" y el lado derecho colgaría.

Si está confundido acerca de la prioridad, así es como se evaluarían las cosas en su publicación original si || tenía mayor precedencia que &&:

1st.) True || False = True 2nd.) True && 1st = True 3rd.) 2nd && false = false Expression = False;

No puedo recordar si va de derecha a izquierda o de izquierda a derecha, pero en cualquier caso el resultado sería el mismo. En tu segundo post, si || Tuvo mayor precedencia:

1st.) 1||InfLoop(); Hang forever, but assuming it didn''t 2nd.) 1 && 1st; 3rd.) 2nd && InfLoop(); Hang Forever

tl; dr: sigue siendo una prioridad la evaluación de && ''s primero, pero el compilador cortocircuita también el OR. En esencia, el compilador agrupa el orden de las operaciones como esta (VISTA SIMPLÍSTICA, baja las horquillas :-P)

1st.) Is 1&&1 True? 2nd.) Evaluate if the Left side of the operation is true, if so, skip the second test and return True, Otherwise return the value of the second test(this is the OR) 3rd.) Is Inf() && Inf() True? (this would hang forever since you have an infinite loop)

Actualización # 2: "Sin embargo, este ejemplo prueba que && NO TIENE precedencia, ya que || se evalúa antes de la segunda &&. Esto muestra que && y || tienen la misma prioridad y se evalúan en el orden de izquierda a derecha".

"Si && tuviera prioridad, evaluaría el primer && (1), luego el segundo && (bucles infinitos) y colgaría el programa. Dado que esto no sucede, && no se evalúa antes de ||".

Vamos a cubrir estos en detalle.

Estamos hablando de dos cosas distintas aquí. La precedencia, que determina el orden de las operaciones, y el cortocircuito, que es un truco de compilación / idioma para guardar los ciclos del procesador.

Vamos a cubrir la precedencia primero. La precedencia es breve para "Orden de operaciones" En esencia, dada esta declaración: 1 + 2 * 3, ¿en qué orden se deben agrupar las operaciones para su evaluación?

Las matemáticas definen claramente el orden de las operaciones como dar mayor precedencia a la multiplicación que la suma.

1 + (2 * 3) = 1 + 2 * 3 2 * 3 is evaluated first, and then 1 is added to the result. * has higher precedence than +, thus that operation is evaluated first.

Ahora, pasemos a expresiones booleanas: (&& = AND, || = OR)

true AND false OR true

C ++ da Y una prioridad más alta que OR, por lo tanto

(true AND false) OR true true AND false is evaluated first, and then used as the left hand for the OR statement

Entonces, solo en precedencia, (verdadero && verdadero || falso && falso) será operado en este orden:

((true && true) || (false && false)) = (true && true || false && false) 1st Comparison.) true && true 2nd Comparison.) false && false 3rd Comparison.) Result of 1st comparison || Result of Second

Conmigo hasta ahora? Ahora entremos en cortocircuito: en C ++, las declaraciones booleanas son lo que se llama "cortocircuito". Esto significa que el compilador verá una declaración dada y elige la "mejor ruta" para la evaluación. Tomemos este ejemplo:

(true && true) || (false && false) There is no need to evaluate the (false && false) if (true && true) equals true, since only one side of the OR statement needs to be true. Thus, the compiler will Short Circuit the expression. Here''s the compiler''s Simplified logic: 1st.) Is (true && true) True? 2nd.) Evaluate if the Left side of the operation is true, if so, skip the second test and return True, Otherwise return the value of the second test(this is the OR) 3rd.) Is (false && false) True? Return this value

Como puede ver, si (true && true) se evalúa como VERDADERO, no es necesario gastar los ciclos de reloj evaluando si (falso && falso) es verdadero.

C ++ Siempre es corto, pero otros lenguajes proporcionan mecanismos para lo que se llaman operadores "Eager".

Tomemos por ejemplo el lenguaje de programación Ada. En Ada, "AND" y "OR" son operadores "ansiosos" ... obligan a todo a ser evaluado.

En Ada (verdadero Y verdadero) O (falso Y falso) evaluaría tanto (verdadero Y verdadero) como (falso Y falso) antes de evaluar el OR. Ada también te da la posibilidad de hacer un cortocircuito con AND THEN y OR ELSE, lo que te dará el mismo comportamiento que C ++.

Espero que responda plenamente a su pregunta. Si no, déjame saber :-)

Actualización 3: última actualización, y luego continuaré en el correo electrónico si todavía tiene problemas.

"Si se produce un cortocircuito en el operador || y se cortocircuita la ejecución de la segunda expresión &&, eso significa que el operador || se ejecutó ANTES del segundo operador &&. Esto implica una ejecución de izquierda a derecha para && y || ( no && precedencia).

Veamos entonces este ejemplo:

(false && infLoop()) || (true && true) = true (Put a breakpoint in InfLoop and it won''t get hit) false && infLoop() || true && true = true (Put a breakpoint in InfLoop and it won''t get hit) false || (false && true && infLoop()) || true = false (infLoop doesn''t get hit)

Si lo que decías era cierto, InfLoop sería golpeado en los dos primeros. También notará que InfLoop () tampoco recibe llamadas en el tercer ejemplo.

Ahora, veamos esto:

(false || true && infLoop() || true);

Infloop se llama! Si OR tuviera una precedencia más alta que &&, entonces el compilador evaluaría:

(false || true) && (infLoop() || true) = true; (false || true) =true (infLoop() || true = true (infLoop isn''t called)

¡Pero InfLoop se llama! Esta es la razón por:

(false || true && infLoop() || true); 1st Comparison.) true && InfLoop() (InfLoop gets called) 2nd Comparison.) False || 1st Comp (will never get here) 3rd Comparison.) 2nd Comp || true; (will never get here)

Precendece SOLO establece la agrupación de operaciones. En esto, && es mayor que ||.

true && false || true && true gets grouped as (true && false) || (true && true);

El compilador Entonces aparece y determina en qué orden debe ejecutarse la evaluación para darle la mejor oportunidad de guardar ciclos.

Consider: false && infLoop() || true && true Precedence Grouping goes like this: (false && infLoop()) || (true && true) The compiler then looks at it, and decides it will order the execution in this order: (true && true) THEN || THEN (false && InfLoop())

Es un hecho ... y no sé cómo demostrarlo. La precedencia está determinada por las reglas gramaticales del lenguaje. La optimización del compilador está determinada por cada compilador. Algunos son mejores que otros, pero Todos son libres de reordenar las comparaciones agrupadas según lo crea conveniente para darle la "mejor" oportunidad para la ejecución más rápida con la menor cantidad de comparaciones.

Como y / o / verdadero / falso es muy similar a * / + / 1/0 (son matemáticamente equivalentes-ish), lo siguiente también es cierto:

1 * 1 + 0 * 0 == 1

y bastante fácil de recordar ...

Entonces sí, tiene que ver con la precedencia y el cortocircuito. La precedencia de operaciones booleanas es bastante fácil si se asigna a sus operaciones enteras correspondientes.

Dos hechos explican el comportamiento de ambos ejemplos. Primero, la precedencia de && es mayor que || . En segundo lugar, ambos operadores lógicos utilizan la evaluación de cortocircuito.

La precedencia a menudo se confunde con el orden de evaluación, pero es independiente. Una expresión puede tener sus elementos individuales evaluados en cualquier orden, siempre que el resultado final sea correcto. En general, para algún operador, eso significa que el valor de la izquierda (LHS) se puede evaluar antes o después del valor de la derecha (RHS), siempre que ambos se evalúen antes de que se aplique el operador.

Los operadores lógicos tienen una propiedad especial: en ciertos casos, si un lado evalúa un valor específico, entonces el valor del operador se conoce independientemente del valor del otro lado. Para hacer que esta propiedad sea útil, el lenguaje C (y por extensión cada lenguaje similar a C) ha especificado los operadores lógicos para evaluar el LHS antes que el RHS, y además evaluar solo el RHS si su valor es necesario para conocer el resultado del operador.

Entonces, asumiendo las definiciones habituales de TRUE y FALSE , TRUE && TRUE || FALSE && FALSE TRUE && TRUE || FALSE && FALSE se evalúa a partir de la izquierda. La primera TRUE no fuerza el resultado de la primera && , por lo que se evalúa la segunda TRUE , y luego se evalúa la expresión TRUE && TRUE (a VERDADERA). Ahora, el || sabe que es LHS. Aún mejor, su LHS ha forzado el resultado de la || para ser conocido, por lo que se salta la evaluación de todo su RHS.

El mismo orden exacto de evaluación se aplica en el segundo caso. Desde el RHS de la || es irrelevante, no se evalúa y no se realiza ninguna llamada a infiniteLoop() .

Este comportamiento es por diseño, y es útil. Por ejemplo, puede escribir p && p->next sabiendo que la expresión nunca intentará eliminar la referencia a un puntero NULO.

Esta es una ilustración secuencial:

(true && true || false && false) = ((true && true) || (false && false)) // because && is higher precedence than ||, // like 1 + 2 * 3 = 7 (* higher than +) = ((true) || (false)) = true

Pero también tenga en cuenta que si es

(true || ( ... ))

entonces el lado derecho no se evalúa, por lo que no se llama a ninguna función, y la expresión simplemente devolverá true .

La respuesta simple es && toma precedencia más alta que ||. Además, el código no se ejecuta porque no es necesario que se conozca el resultado de la expresión booleana. Sí, es una optimización del compilador.

Respecto al último código de Andrew,

#include <iostream> using namespace std; bool infiniteLoop () { while (true); return false; } int main() { cout << (true && true || infiniteLoop() && infiniteLoop()) << endl; // true }

La evaluación de cortocircuito significa que las llamadas a infiniteLoop están garantizadas para no ejecutarse.

Sin embargo, es interesante de una manera perversa porque el borrador de C ++ 0x hace que el comportamiento infinito de bucle infinito que no hace nada. Esa nueva regla generalmente se considera muy indeseable y estúpida, incluso francamente peligrosa, pero de alguna manera se ha colado en el draft. Parcialmente a partir de consideraciones de escenarios de subprocesos, donde el autor de un artículo pensó que simplificaría las reglas para algo u otro bastante irrelevante.

Entonces, con un compilador que está en la "vanguardia" de la conformidad con C ++ 0x, el programa podría terminar, con algún resultado, ¡incluso si se ejecuta una llamada a infiniteLoop ! Por supuesto, con tal compilador también podría producir ese temido fenómeno, demonios nasales ...

Felizmente, como se mencionó, la evaluación de cortocircuito significa que se garantiza que las llamadas no se ejecutarán.

Salud y salud,

con respecto a su edición: infiniteLoop () no se evaluará porque es cierto || (lo que sea) siempre es cierto. Use true | (lo que sea) si algo debe ser ejecutado.

sobre el true && true || infiniteLoop() && infiniteLoop() Ejemplo de true && true || infiniteLoop() && infiniteLoop() , ninguna de las llamadas de bucle infinito se está evaluando debido a las dos características combinadas: && tiene prioridad sobre ||, y || Cortocircuitos cuando el lado izquierdo es verdadero.

si && y || Teniendo la misma precedencia, la evaluación tendría que ser así:

((( true && true ) || infiniteLoop ) && infiniteLoop ) (( true || infiniteLoop ) && infiniteLoop ) => first call to infiniteLoop is short-circuited (true && infiniteLoop) => second call to infiniteLoop would have to be evaluated

pero debido a la precedencia de &&, la evaluación en realidad va

(( true && true ) || ( infiniteLoop && infiniteLoop )) ( true || ( infiniteLoop && infiniteLoop )) => the entire ( infiniteLoop && infiniteLoop ) expression is short circuited ( true )

Caladain tiene exactamente la respuesta correcta, pero quería responder a uno de sus comentarios sobre su respuesta:

Si cortocircuita el || el operador se produce y cortocircuita la ejecución de la segunda expresión &&, que significa el || El operador fue ejecutado ANTES del segundo operador de &&. Esto implica una ejecución de izquierda a derecha para && y || (No && precedencia).

Creo que parte del problema que tienes es que la precedencia no significa lo que crees que significa. Es cierto que && tiene mayor prioridad que || , y esto explica exactamente el comportamiento que estás viendo. Considere el caso con operadores aritméticos ordinarios: supongamos que tenemos a * b + c * (d + e) . Lo que nos dice la precedencia es cómo insertar paréntesis: primero alrededor de * , luego alrededor de + . Esto nos da (a * b) + (c * (d + e)) ; en su caso, tenemos (1 && 1) || (infiniteLoop() && infiniteLoop()) (1 && 1) || (infiniteLoop() && infiniteLoop()) . Entonces, imagina que las expresiones se convierten en árboles . Para hacer esto, transforma cada operador en un nodo con sus dos argumentos como hijos:

La evaluación de este árbol es donde interviene el cortocircuito. En el árbol aritmético, puede imaginar un primer estilo de ejecución de abajo hacia arriba: primero evalúe DE = d + e , luego AB = a * b CDE = c * DE , y el resultado final es AB + CDE . Pero tenga en cuenta que también podría haber evaluado primero AB , luego DE , CDE y el resultado final; No puedes notar la diferencia. Sin embargo, desde || y && son cortocircuitos, tienen que usar esta primera evaluación de la izquierda. Así, para evaluar el || , primero evaluamos 1 && 1 . Como esto es cierto, || cortocircuita e ignora su rama derecha, aunque, si la hubiera evaluado, habría tenido que evaluar primero el infiniteLoop() && infiniteLoop() .

Si le ayuda, puede pensar en cada nodo del árbol como una llamada de función, que produce la siguiente representación plus(times(a,b), times(c,plus(d,e))) en el primer caso, y or(and(1,1), and(infiniteLoop(),infiniteLoop()) en el segundo caso. Cortocircuito significa que tiene que evaluar completamente cada argumento de la función de la mano izquierda para or o and ; si es true (para or ) o false (para and ), luego ignora el argumento de la mano derecha.

Su comentario presupone que primero evaluamos todo con mayor prioridad, luego todo con mayor prioridad, y así sucesivamente, lo que corresponde a una ejecución de abajo hacia arriba del árbol. En cambio, lo que sucede es que la precedencia nos dice cómo construir el árbol. Las reglas para la ejecución del árbol son irrelevantes en el caso aritmético simple; Sin embargo, el cortocircuito es precisamente una especificación exacta de cómo evaluar el árbol.

Edit 1: En uno de tus otros comentarios, dijiste

Su ejemplo aritmético requiere que las dos multiplicaciones se evalúen antes de la suma final, ¿no es eso lo que define la precedencia?

Sí, esto es lo que define la precedencia, excepto que no es del todo cierto. Ciertamente, es exactamente cierto en C , pero considera cómo evaluarías la expresión (no C!) 0 * 5 ^ 7 en tu cabeza, donde 5 ^ 7 = 5 ⁷ y ^ tiene una precedencia más alta que * . De acuerdo con la regla de abajo hacia arriba de abajo hacia arriba, debemos evaluar 0 y 5 ^ 7 antes de poder encontrar el resultado. Pero no te molestes en evaluar 5 ^ 7 ; solo dirías "bueno, ya que 0 * x = 0 para todo x , este debe ser 0 ", y omite toda la rama de la derecha. En otras palabras, no he evaluado ambos lados completamente antes de evaluar la multiplicación final; He hecho un cortocircuito. Del mismo modo, ya que false && _ == false y true || _ == true true || _ == true para cualquier _ , puede que no necesitemos tocar el lado derecho; esto es lo que significa que un operador esté en cortocircuito. C no hace un cortocircuito en la multiplicación (aunque un lenguaje podría hacer esto), pero hace un cortocircuito en && y || .

Del mismo modo que el cortocircuito 0 * 5 ^ 7 no cambia las reglas habituales de precedencia de PEMDAS, el cortocircuito de los operadores lógicos no cambia el hecho de que && tiene mayor precedencia que || . Es simplemente un atajo. Como tenemos que elegir primero el lado del operador para evaluar, C promete evaluar primero el lado izquierdo de los operadores lógicos; Una vez hecho esto, hay una manera obvia (y útil) de evitar evaluar el lado derecho para ciertos valores, y C se compromete a hacerlo.

Su regla, que evalúa la expresión de abajo hacia arriba de abajo hacia arriba, también está bien definida, y un idioma puede elegir hacer esto. Sin embargo, tiene la desventaja de no permitir el cortocircuito, que es un comportamiento útil. Pero si todas las expresiones de su árbol están bien definidas (sin bucles) y puras (sin modificar las variables, imprimiendo, etc.), entonces no puede notar la diferencia. Es solo en estos casos extraños, que las definiciones matemáticas de "y" y "o" no cubren, que el cortocircuito es incluso visible.

Además, tenga en cuenta que no hay nada fundamental en el hecho de que el cortocircuito funciona al priorizar la expresión más a la izquierda. Uno podría definir un lenguaje Ɔ, donde ⅋⅋ representa and e // representa || , pero donde 0 ⅋⅋ infiniteLoop() y 1 // infiniteLoop() irían en bucle, e infiniteLoop() ⅋⅋ 0 e infiniteLoop() // 1 serían falsos y verdaderos, respectivamente. Esto solo corresponde a elegir evaluar el lado derecho primero en lugar del lado izquierdo, y luego simplificar de la misma manera.

En pocas palabras: lo que la precedencia nos dice es cómo construir el árbol de análisis. Las únicas órdenes sensatas para evaluar el árbol de análisis son aquellas que se comportan como si lo evaluáramos de abajo hacia arriba (como usted quiere hacer) en valores puros bien definidos . Para valores no definidos o impuros, se debe elegir algún orden lineal. ¹ Una vez que se elige un orden lineal, ciertos valores para un lado de un operador pueden determinar de forma única el resultado de la expresión completa ( por ejemplo , 0 * _ == _ * 0 == 0 , false && _ == _ && false == false , o true || _ == _ || true == true ). Debido a esto, es posible que pueda escapar sin completar la evaluación de lo que venga después en el orden lineal; C se compromete a hacer esto para los operadores lógicos && y || evaluándolos de izquierda a derecha, y no hacerlo para otra cosa. Sin embargo, gracias a la precedencia, sabemos que es true || true && false true || true && false es true y no false : porque

true || true && false → true || (true && false) → true || false → true

en lugar de

true || true && false ↛ (true || true) && false → true && false → false

1: En realidad, también podríamos evaluar teóricamente los dos lados de un operador en paralelo, pero eso no es importante en este momento, y ciertamente no tendría sentido para C. Esto da lugar a una semántica más flexible, pero que tiene problemas con el lado. Efectos (¿cuándo ocurren?).

&& tiene una precedencia más alta .

&& tiene una prioridad más alta que || .