¿Es ((a + (b & 255)) & 255) lo mismo que ((a + b) & 255)?

Estaba navegando en un código C ++ y encontré algo como esto:

(a + (b & 255)) & 255

El doble Y me molestó, así que pensé en:

(a + b) & 255

( ay bson enteros sin signo de 32 bits)

Escribí rápidamente un script de prueba (JS) para confirmar mi teoría:

for (var i = 0; i < 100; i++) {
    var a = Math.ceil(Math.random() * 0xFFFF),
        b = Math.ceil(Math.random() * 0xFFFF);

    var expr1 = (a + (b & 255)) & 255,
        expr2 = (a + b) & 255;

    if (expr1 != expr2) {
        console.log("Numbers " + a + " and " + b + " mismatch!");
        break;
    }
}

Si bien el guión confirmó mi hipótesis (ambas operaciones son iguales), todavía no confío en él, porque 1) aleatorio y 2) no soy matemático, no tengo idea de lo que estoy haciendo .

Además, perdón por el título Lisp-y. Siéntete libre de editarlo.

Ellos son iguales. He aquí una prueba:

Primero nota la identidad (A + B) mod C = (A mod C + B mod C) mod C

Repitamos el problema considerándolo a & 255como sustituto a % 256. Esto es cierto ya aque no está firmado.

Asi (a + (b & 255)) & 255es(a + (b % 256)) % 256

Esto es lo mismo que (a % 256 + b % 256 % 256) % 256(He aplicado la identidad indicada anteriormente: tenga en cuenta que mody %son equivalentes para los tipos sin firmar).

Esto simplifica a lo (a % 256 + b % 256) % 256que se convierte (a + b) % 256(reaplicando la identidad). A continuación, puede volver a poner el operador bit a bit para dar

(a + b) & 255

completando la prueba.

En la suma posicional, la resta y la multiplicación de números sin signo para producir resultados sin signo, 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. También se aplica a la aritmética con signo "complemento a dos", pero no a la aritmética con signo de magnitud y signo.

Sin embargo, debemos 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 la aritmética de C tiene algunas reglas arcanas que pueden hacernos tropezar. arriba. La aritmética sin signo en C sigue reglas simples binarias envolventes, pero el desbordamiento aritmético con signo es un comportamiento indefinido. Peor aún, en algunas circunstancias, C "promoverá" automáticamente un tipo sin firmar a (firmado) int.

El comportamiento indefinido en C puede ser especialmente insidioso. Es probable que un compilador tonto (o un compilador con un nivel de optimización bajo) haga lo que usted espera según su comprensión de la aritmética binaria, mientras que un compilador optimizador puede romper su código de formas extrañas.

Volviendo a la fórmula de la pregunta, la equivalencia depende de los tipos de operandos.

Si son enteros sin signo cuyo tamaño es mayor o igual que el tamaño de, intentonces el comportamiento de desbordamiento del operador de suma está bien definido como envoltura binaria simple. El hecho de que enmascaremos 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, se promoverán a (con signo) int. El desbordamiento de enteros firmados es un comportamiento indefinido, pero al menos en todas las plataformas en las 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. Entonces, nuevamente podemos recurrir al argumento aritmético simplemente binario para considerar las declaraciones equivalentes.

Si son enteros con signo cuyo tamaño es menor que int, entonces nuevamente no puede ocurrir el desbordamiento y en implementaciones de complemento a dos podemos confiar en el argumento aritmético binario estándar para decir que son equivalentes. En implementaciones de magnitud de signo o complemento de unidades, no serían equivalentes.

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

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

Sin firmar ase puede reescribir como m * 0x100 + balgunos sin signo m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. De ambas definiciones se deduce 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 firmar, 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

Entonces sí, es cierto. Para enteros sin signo de 32 bits.

¿Qué pasa con otros tipos de enteros?

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

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

¿Recuerdas la adición en la escuela? Agrega números dígito a dígito y agrega un valor de acarreo a la siguiente columna de dígitos. No hay forma de que una columna de dígitos posterior (más significativa) influya en una columna ya procesada. Debido a esto, no hay 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 rompería esto.

Tal Deathstation 9000 : - ) tendría que usar un 33 bits int, si el OP significara unsigned short"enteros sin firmar de 32 bits". Si unsigned intfuera necesario, el DS9K tendría que usar 32 bits inty 32 bits.unsigned int 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 están permitidos en §3.9.1 / 1). Otras combinaciones de tamaños y bits de relleno también funcionarían.

Por lo que puedo decir, esta es la única forma de romperlo, porque:

• La representación entera debe utilizar 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 aportar un valor de 2 ⁿ
• La promoción int solo se permite si intpuede representar todos los valores del tipo de fuente (§4.5 / 1), por lo queint debe tener al menos 32 bits que contribuyan al valor, más un bit de signo.
• el intno puede tener más bits de valor (sin contar el bit de signo) que 32, porque de lo contrario una suma no puede desbordarse.

Ya tienes la respuesta inteligente: la aritmética sin firmar es aritmética de módulo y, por lo tanto, los resultados se mantendrán, puedes probarlo matemáticamente ...

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

Entonces, en su caso, personalmente me gusta lanzarlo a una computadora; me toma menos tiempo convencerme de que el programa es correcto que el que se necesita para convencerme a mí mismo 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 todos los valores posibles de ay ben el espacio de 32 bits y verifica si la igualdad se cumple o no. Si no es así, imprime el caso que no funcionó, que puede usar como verificación de cordura.

Y, según Clang : la igualdad se mantiene .

Además, dado que las reglas aritméticas son independientes del ancho de bits (por encima intdel ancho de bits), esta igualdad se mantendrá para cualquier tipo de 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 período de tiempo razonable? No puede. Los bucles se optimizaron. De lo contrario, todos hubiéramos muerto antes de que terminara la ejecución.

Inicialmente solo lo probé para enteros sin signo de 16 bits; desafortunadamente, C ++ es un lenguaje loco donde los pequeños enteros (anchos de bits más pequeños queint ) 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;
}

Una vez mas, según Clang : la igualdad se mantiene .

Bueno, allá vas :)

¹ Por supuesto, si un programa desencadena un comportamiento indefinido sin darse cuenta, no resultaría mucho.

La respuesta rápida es: ambas expresiones son equivalentes

• dado que ay bson enteros de 32 bits sin signo, 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 al 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 existen plataformas conocidas donde estas expresiones difieran, pero el Estándar no lo garantiza, debido a las reglas de promoción integral.

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

• Por el contrario, si el tipo de ay bes menor que int, ambos se promueven inty el cálculo se realiza mediante aritmética con signo, donde el desbordamiento invoca un comportamiento indefinido.

  • Si inttiene 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 inttiene exactamente 32 bits de valor, el cálculo puede desbordarse para ambas expresiones, por ejemplo valores a=0xFFFFFFFFy b=1causaría un desbordamiento en ambas expresiones. Para evitar esto, necesitaría escribir ((a & 255) + (b & 255)) & 255.

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

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

Idéntico asumiendo que no hay desbordamiento . Ninguna versión es realmente inmune al desbordamiento, pero la versión doble y es más resistente. No conozco un sistema en el que un desbordamiento en este caso sea un problema, pero puedo ver al autor haciendo esto en caso de que haya uno.

Sí, puedes probarlo con aritmética, pero hay una respuesta más intuitiva.

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

Por lo tanto, cualquier cosa que haga con 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 ejercicio para el lector.

Pero para 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 del bconjunto en cero) y agregar esto ay luego tomar solo los últimos 8 bits de la configuración de resultado, todo más alto bits a cero.

La segunda línea dice sumar ay btomar los últimos 8 bits con todos los bits superiores a cero.

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

** últimos 8 bits = 8 LSB

También es interesante notar 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 intcero con todos los demás bits. Se a + bdesbordará, produciendo el resultado esperado.