c++ - págs - Si quiero redondear un entero sin signo al entero par más pequeño o igual, ¿puedo dividir por 2 y luego multiplicar por 2?

hotel p 1990 estadística elemental 7ma ed méxico cecsa

Question

Por ejemplo :

f(8)=8
f(9)=8

¿Puedo hacer x = x/2*2; ? ¿Existe el riesgo de que el compilador optimice esa expresión?

Answer 1

C y C ++ generalmente usan la regla "como si" en la optimización. El resultado del cálculo debe ser como si el compilador no optimizara su código.

En este caso, 9/2*2=8 . El compilador puede usar cualquier método para lograr el resultado 8. Esto incluye máscaras de bits, cambios de bits o cualquier pirateo específico de la CPU que produzca los mismos resultados (x86 tiene bastantes trucos que se basan en el hecho de que no diferencia entre punteros y enteros, a diferencia de C y C ++).

Answer 2

Como especificó que los enteros no están firmados, puede hacerlo con una máscara simple:

x & (~1u)

Lo que establecerá el LSB en cero, produciendo así el número par inmediato que no es mayor que x . Es decir, si x tiene un tipo que no es más ancho que un unsigned int .

Por supuesto, puede forzar que el 1 sea ​​del mismo tipo que una x más ancha, así:

x & ~((x & 1u) | 1u)

Pero en este punto, realmente debería considerar este enfoque como un ejercicio de ofuscación, y aceptar la respuesta de Betsabé.

Por supuesto, me olvidé de la biblioteca estándar. Si incluye stdint.h (o cstdint , como debería en el código C ++). Puede dejar que la implementación se encargue de los detalles:

uintmax_t const lsb = 1;
x & ~lsb;

o

x & ~UINTMAX_C(1)

Answer 3

El compilador puede realizar las optimizaciones que desee siempre que no introduzca ningún efecto secundario en el programa. En su caso, no puede cancelar los ''2'', ya que la expresión tendrá un valor diferente para los números impares.

x / 2 * 2 se evalúa estrictamente como (x / 2) * 2 , y x / 2 se realiza en aritmética de enteros si x es un tipo integral.

Esto, de hecho, es una técnica de redondeo idiomática.

Answer 4

Puede escribir x / 2 * 2 y el compilador producirá un código muy eficiente para borrar el bit menos significativo si x tiene un tipo sin signo.

Por el contrario, podrías escribir:

x = x & ~1;

O probablemente menos legible:

x = x & -2;

O incluso

x = (x >> 1) << 1;

O esto también:

x = x - (x & 1);

O este último, sugerido por supercat, que funciona para valores positivos de todos los tipos enteros y representaciones:

x = (x | 1) ^ 1;

Todas las propuestas anteriores funcionan correctamente para todos los tipos enteros sin signo en las arquitecturas de complemento a 2. Si el compilador producirá un código óptimo es una cuestión de configuración y calidad de implementación.

Sin embargo, tenga en cuenta que x & (~1u) no funciona si el tipo de x es mayor que unsigned int . Esta es una trampa contra intuitiva. Si insiste en usar una constante sin signo, debe escribir x & ~(uintmax_t)1 ya que incluso x & ~1ULL fallaría si x tiene un tipo más grande que unsigned long long . Para empeorar las cosas, muchas plataformas ahora tienen tipos enteros más grandes que uintmax_t , como __uint128_t .

Aquí hay un pequeño punto de referencia:

typedef unsigned int T;

T test1(T x) {
    return x / 2 * 2;
}

T test2(T x) {
    return x & ~1;
}

T test3(T x) {
    return x & -2;
}

T test4(T x) {
    return (x >> 1) << 1;
}

T test5(T x) {
    return x - (x & 1);
}

T test6(T x) {  // suggested by supercat
    return (x | 1) ^ 1;
}

T test7(T x) {  // suggested by Mehrdad
    return ~(~x | 1);
}

T test1u(T x) {
    return x & ~1u;
}

Según lo sugerido por Ruslan, las pruebas en el Explorador de compiladores de Godbolt muestran que, para todas las alternativas anteriores, gcc -O1 produce el mismo código exacto para unsigned int , pero cambiar el tipo T a unsigned long long muestra un código diferente para test1u .

Answer 5

Si sus valores son de cualquier tipo sin signo como usted dice, lo más fácil es

x & -2;

Las maravillas de la aritmética sin signo hacen que -2 se convierta al tipo de x , y tiene un patrón de bits que tiene todos, pero para el bit menos significativo que es 0 .

Al contrario de algunas de las otras soluciones propuestas, esto debería funcionar con cualquier tipo de entero sin signo que sea al menos tan ancho como unsigned . (Y de todos modos, no debes hacer aritmética con tipos más estrechos).

Bonificación adicional, como lo señala supercat, esto solo utiliza la conversión de un tipo con signo a un tipo sin signo. Esto está bien definido por el estándar como módulo aritmético. Por lo tanto, el resultado es siempre UTYPE_MAX-1 para UTYPE el tipo sin signo de x . En particular, es independiente de la representación de signos de la plataforma para los tipos firmados.

Answer 6

Una opción que me sorprende que no se haya mencionado hasta ahora es utilizar el operador de módulo. Yo diría que esto representa su intención al menos tan bien como su fragmento original, y tal vez incluso mejor.

x = x - x % 2

Como han dicho otros, el optimizador del compilador se ocupará de cualquier expresión razonable de manera equivalente, así que preocúpate por lo que está más claro en lugar de lo que crees que es más rápido. Todas las respuestas de ajuste de bits son interesantes, pero definitivamente no debe usar ninguna de ellas en lugar de operadores aritméticos (suponiendo que la motivación sea aritmética en lugar de ajustes de bits).

Answer 7

solo use lo siguiente:

template<class T>
inline T f(T v)
{
    return v & (~static_cast<T>(1));
}

No tenga miedo de que esta sea la función, el compilador finalmente debe optimizar esto en solo v & (~ 1) con el tipo apropiado de 1.