Es ((a + (b & 255)) & 255) al igual que ((a + b) y 255)?

En la suma posicional, resta y multiplicación los dígitos más significativos de la entrada no afectan a los dígitos menos significativos del resultado. Esto se aplica tanto a la aritmética binaria como a la aritmética decimal.

Sin embargo, tenemos que tener cuidado al tomar reglas de la aritmética binaria y aplicarlas a C (creo que C++ tiene las mismas reglas que C en estas cosas, pero no estoy 100% seguro) porque C aritmética tiene algunas reglas arcanas que nos pueden hacer tropezar. Aritmética sin signo en C sigue reglas envolventes binarias simples, pero el desbordamiento aritmético firmado es un comportamiento indefinido. Peor en algunas circunstancias, C automáticamente "promocionará" un tipo sin signo a (signed) int.

Un comportamiento Indefinido en C puede ser especialmente insiduous. Un compilador tonto (o un compilador en un nivel de optimización bajo) es probable que haga lo que espera basado en su comprensión de la aritmética binaria, mientras que un compilador de optimización puede romper su código de maneras extrañas.

Así que volviendo para la fórmula en la pregunta la equivilencia depende de los tipos de operando.

Si son enteros sin signo cuyo tamaño es mayor o igual al tamaño de int entonces el comportamiento de desbordamiento del operador de suma está bien definido como envolvente binaria simple. Si enmascaramos o no los 24 bits altos de un operando antes de la operación de adición no tiene ningún impacto en los bits bajos del resultado.

Si son enteros sin signo cuyo tamaño es menor que int, entonces será ascendido a (firmado) int. El desbordamiento de enteros firmados es un comportamiento indefinido, pero al menos en todas las plataformas que he encontrado, la diferencia de tamaño entre diferentes tipos de enteros es lo suficientemente grande como para que una sola adición de dos valores promocionados no cause desbordamiento. Así que de nuevo podemos volver al argumento aritmético simplemente binario para considerar las declaraciones equivalentes.

Si son enteros con signo cuyo tamaño es menor que int entonces de nuevo desbordamiento no puede suceder y en doses-complemento implementaciones podemos confiar en el argumento aritmético binario estándar para decir que son equivilent. En signo-magnitud o complementar las implementaciones que no sería equivalente.

OTOH si a y b eran enteros con signo cuyo tamaño era mayor o igual al tamaño de int, entonces incluso en implementaciones de complemento de dos hay casos en los que una instrucción estaría bien definida mientras que la otra sería un comportamiento indefinido.

Lema: a & 255 == a % 256 para a sin signo.

Sin signo a se puede reescribir como m * 0x100 + b algunos sin signo m,b, 0 <= b < 0xff, 0 <= m <= 0xffffff. De ambas definiciones se desprende que a & 255 == b == a % 256.

Además, necesitamos:

• la propiedad distributiva: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• la definición de suma sin signo, matemáticamente: (a + b) ==> (a + b) % (2 ^ 32)

Así:

(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255      // def'n of addition
                      = ((a + (b % 256)) % (2^32)) % 256      // lemma
                      = (a + (b % 256)) % 256                 // because 256 divides (2^32)
                      = ((a % 256) + (b % 256 % 256)) % 256   // Distributive
                      = ((a % 256) + (b % 256)) % 256         // a mod n mod n = a mod n
                      = (a + b) % 256                         // Distributive again
                      = (a + b) & 255                         // lemma

Así que sí, es verdad. Para enteros sin signo de 32 bits.

¿Qué pasa con otros tipos enteros?

• Para enteros sin signo de 64 bits, todo lo anterior se aplica igual de bien, simplemente sustituyendo 2^64 por 2^32.
• Para enteros sin signo de 8 y 16 bits, la suma implica la promoción a int. Esto int definitivamente no se desbordará ni será negativo en ninguna de estas operaciones, por lo que todas siguen siendo válidas.
• Para enteros con signo, si a+b o a+(b&255) se desbordan, es un comportamiento indefinido. Así que la igualdad no puede sostenerse - hay casos donde (a+b)&255 es comportamiento indefinido pero (a+(b&255))&255 no lo es.

Sí (a + b) & 255 está bien.

¿Recuerdas la adición en la escuela? Agrega números dígito por dígito y agrega un valor de acarreo a la siguiente columna de dígitos. No hay forma de que una columna posterior (más significativa) de dígitos influya en una columna ya procesada. Debido a esto, no hace ninguna diferencia si pone a cero los dígitos solo en el resultado, o también primero en un argumento.

Lo anterior no siempre es cierto, el estándar C++ permite una implementación que se rompería este.

Tal estación de la Muerte 9000 :-) tendría que usar un int de 33 bits, si el OP significaba unsigned short con "enteros sin signo de 32 bits". Si se quería decir unsigned int, el DS9K tendría que usar un int de 32 bits, y un unsigned int de 32 bits con un bit de relleno. (Se requiere que los enteros sin signo tengan el mismo tamaño que sus contrapartes con signo según §3.9.1/3, y los bits de relleno se permiten en §3.9.1/1.) Otras combinaciones de tamaños y bits de relleno también funcionarían.

As lo que puedo decir, esta es la única manera de romperlo, porque:

• La representación entera debe usar un esquema de codificación "puramente binario" (§3.9.1 / 7 y la nota al pie), todos los bits excepto los bits de relleno y el bit de signo deben contribuir con un valor de 2 ⁿ
• la promoción int solo está permitida si int puede representar todos los valores del tipo fuente (§4.5/1), por lo que int debe tener al menos 32 bits que contribuyan al valor, más un bit de signo.
• el int no puede tener más bits de valor (sin contar el bit de signo) que 32, porque de lo contrario una adición no puede desbordarse.

Ya tienes la respuesta inteligente: aritmética sin signo es aritmética modulo y por lo tanto los resultados se mantendrán, puedes demostrarlo matemáticamente...

Una cosa interesante acerca de las computadoras, sin embargo, es que las computadoras son rápidas. De hecho, son tan rápidos que enumerar todas las combinaciones válidas de 32 bits es posible en una cantidad razonable de tiempo (no intente con 64 bits).

Así que, en su caso, personalmente me gusta simplemente tirarlo a una computadora; me lleva menos tiempo convencer yo mismo que el programa es correcto de lo que se necesita para convencerme de que la prueba matemática es correcta y que no supervisé un detalle en la especificación¹:

#include <iostream>
#include <limits>

int main() {
    std::uint64_t const MAX = std::uint64_t(1) << 32;
    for (std::uint64_t i = 0; i < MAX; ++i) {
        for (std::uint64_t j = 0; j < MAX; ++j) {
            std::uint32_t const a = static_cast<std::uint32_t>(i);
            std::uint32_t const b = static_cast<std::uint32_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Esto enumera a través de todos los valores posibles de a y b en el espacio de 32 bits y comprueba si la igualdad se mantiene o no. Si no lo hace, imprime el caso que no funcionó, que se puede utilizar como una comprobación de la cordura.

Y, según Clang: Igualdad sostiene.

Además, dado que las reglas aritméticas son agnósticas de ancho de bits (por encima de int ancho de bits), esta igualdad se mantendrá para cualquier tipo entero sin signo de 32 bits o más, incluidos 64 bits y 128 bits.

Nota: ¿Cómo puede un compilador enumerar todos los patrones de 64 bits en un marco de tiempo razonable? No puede. Los bucles fueron optimizados. De lo contrario todos habríamos muerto antes de que terminara la ejecución.

Inicialmente solo lo probé para 16 bits sin firmar enteros; desafortunadamente C++ es un lenguaje loco donde enteros pequeños (anchos de bits más pequeños que int) se convierten primero a int.

#include <iostream>

int main() {
    unsigned const MAX = 65536;
    for (unsigned i = 0; i < MAX; ++i) {
        for (unsigned j = 0; j < MAX; ++j) {
            std::uint16_t const a = static_cast<std::uint16_t>(i);
            std::uint16_t const b = static_cast<std::uint16_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: "
                      << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Y una vez más, según Clang: La igualdad se mantiene .

Bueno, ahí lo tienes:)

¹Por supuesto, si un programa alguna vez inadvertidamente desencadena un Comportamiento Indefinido, no probaría mucho.

La respuesta rápida es: ambas expresiones son equivalentes

• dado que a y b son enteros sin signo de 32 bits, el resultado es el mismo incluso en caso de desbordamiento. la aritmética sin signo garantiza esto: un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

La respuesta larga es: no hay plataformas conocidas donde estas expresiones diferirían, pero la Norma no lo garantiza, debido a las reglas de promoción integral.

• Si el tipo de a y b (enteros de 32 bits sin signo) tiene un rango más alto que int, el cálculo se realiza como unsigned, modulo 2³², y produce el mismo resultado definido para ambas expresiones para todos los valores de a y b.

• Por el Contrario, Si el tipo de a y b es menor que int, ambos son promovido a int y el cálculo se realiza utilizando aritmética firmada, donde el desbordamiento invoca un comportamiento indefinido.

  • Si int tiene al menos 33 bits de valor, ninguna de las expresiones anteriores puede desbordarse, por lo que el resultado está perfectamente definido y tiene el mismo valor para ambas expresiones.

  • Si int tiene exactamente 32 bits de valor, el cálculo puede desbordarse para ambas expresiones, por ejemplo los valores a=0xFFFFFFFF y b=1 causarían una desbordamiento en ambas expresiones. Para evitar esto, tendría que escribir ((a & 255) + (b & 255)) & 255.

• La buena noticia es que no existen tales plataformas¹.

¹ Más precisamente, no existe tal plataforma real, pero uno podría configurar unDS9K para exhibir tal comportamiento y aún cumplir con el Estándar C.

Idéntico suponiendo que no hay desbordamiento. Ninguna de las dos versiones es realmente inmune al desbordamiento, pero el doble y la versión es más resistente a él. No soy consciente de un sistema donde un desbordamiento en este caso es un problema, pero puedo ver al autor haciendo esto en caso de que haya uno.

Sí se puede demostrar con aritmética, pero hay una respuesta más intuitiva.

Al agregar, cada bit solo influye en aquellos más significativos que sí mismo; nunca en aquellos menos significativos.

Por lo tanto, lo que haga a los bits más altos antes de la adición no cambiará el resultado, siempre y cuando solo mantenga los bits menos significativos que el bit más bajo modificado.

La prueba es trivial y se deja como un ejercicio para el lector

Pero para realmente legitimar esto como una respuesta, su primera línea de código dice tomar los últimos 8 bits de b** (todos los bits más altos de b se ponen a cero) y agregar esto a a y luego tomar solo los últimos 8 bits del resultado estableciendo todos los bits más altos a cero.

La segunda línea dice agregar a y b y tomar los últimos 8 bits con todos los bits más altos cero.

Solo los últimos 8 bits son significativos en resultado. Por lo tanto, solo los últimos 8 bits son significativos en la(s) entrada (es).

** últimos 8 bits = 8 LSB

También es interesante señalar que la salida sería equivalente a

char a = something;
char b = something;
return (unsigned int)(a + b);

Como anteriormente, solo los 8 LSB son significativos, pero el resultado es un unsigned int con todos los demás bits cero. El a + b se desbordará, produciendo el resultado esperado.