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

92

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.

Martín
fuente
4
¿Qué idioma es ese guión? ¿ Math.random()Devuelve un entero o un doble en [0,1)? No creo que tu guión (lo mejor que puedo decir) refleja en absoluto el problema que planteaste.
Brick
7
¿Qué es el código c / c ++? Son idiomas diferentes.
Weather Vane
14
No puede reproducir el comportamiento que está intentando probar en JS. Es por eso que todos son solo tú en la elección del idioma. JS no está fuertemente tipado y la respuesta depende críticamente del tipo de variables en C / C ++. El JS es una completa tontería dada la pregunta que ha hecho.
Brick
4
@WeatherVane Eso es esencialmente un pseudocódigo, usando los nombres de las funciones de Javascript. Su pregunta es sobre el comportamiento de &y +sobre enteros sin signo en C y C ++.
Barmar
11
Tenga en cuenta que "escribí un programa de prueba y obtuve la respuesta que esperaba para todas las entradas posibles" no es en realidad una garantía de que algo se comporte como espera. El comportamiento indefinido puede ser así de desagradable; solo dando resultados inesperados después de que haya terminado de convencerse de que su código es correcto.

Respuestas:

78

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.

Betsabé
fuente
81
Es una prueba matemática, ignorando la posibilidad de desbordamiento. Considere A=0xFFFFFFFF, B=1, C=3. La primera identidad no se sostiene. (El desbordamiento no será un problema para la aritmética sin firmar, pero es algo un poco diferente.)
AlexD
4
En realidad, (a + (b & 255)) & 255es lo mismo que (a + (b % 256)) % N % 256, donde Nes uno mayor que el valor máximo sin signo. (la última fórmula está destinada a interpretarse como aritmética de enteros matemáticos)
17
Pruebas matemáticas como ésta no son apropiadas para probar el comportamiento de números enteros en arquitecturas de computadora.
Jack Aidley
25
@JackAidley: Son apropiados cuando se hacen correctamente (lo cual no lo es, debido a que no se considera el desbordamiento).
3
@Shaz: Eso es cierto para el script de prueba, pero no es parte de la pregunta.
21

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.

enchufar
fuente
20

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.
Barry
fuente
17

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 n
  • 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.
alain
fuente
2
Hay muchas otras operaciones además de la adición donde la basura en los bits altos no afecta el resultado en los bits bajos que le interesan. Vea estas preguntas y respuestas sobre el complemento de 2 , que usa asm x86 como caso de uso, pero también se aplica a enteros binarios sin signo en cualquier situación.
Peter Cordes
2
Si bien, por supuesto, todos tienen derecho a votar negativamente de forma anónima, siempre aprecio un comentario como una oportunidad para aprender.
alain
2
Esta es, con mucho, la respuesta / argumento más fácil de entender, en mi opinión. El acarreo / préstamo en suma / resta se propaga solo de bits bajos a bits altos (de derecha a izquierda) en binario, al igual que en decimal. IDK por qué alguien rechazaría esto.
Peter Cordes
1
@Bathsheba: No se requiere que CHAR_BIT sea 8. Pero los tipos sin signo en C y C ++ deben comportarse como enteros binarios en base2 normales de cierto ancho de bits. Creo que eso requiere que UINT_MAX sea 2^N-1. (Es posible que N ni siquiera sea necesario para ser un múltiplo de CHAR_BIT, lo olvido, pero estoy bastante seguro de que el estándar requiere que el Wraparound ocurra módulo algo de potencia de 2.) Creo que la única forma en que puede obtener rarezas es mediante la promoción a un Tipo firmado que sea lo suficientemente ancho para sostener ao bpero no lo suficientemente ancho para sostener a+ben todos los casos.
Peter Cordes
2
@Bathsheba: sí, afortunadamente C-as-portable-assembly-language realmente funciona principalmente para tipos sin firmar. Ni siquiera una implementación de C intencionalmente hostil puede romper esto. Solo se trata de tipos firmados donde las cosas son horribles para los bit-hacks verdaderamente portátiles en C, y una Deathstation 9000 realmente puede romper tu código.
Peter Cordes
14

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 1 :

#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 :)


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

Matthieu M.
fuente
1
usted dice que es fácil de hacer con valores de 32 bits, pero en realidad usa 16 bits ...: D
Willi Mentzel
1
@WilliMentzel: Es un comentario interesante. Inicialmente quería decir que si funciona con 16 bits, funcionará igual con 32 bits, 64 bits y 128 bits porque el Estándar no tiene un comportamiento específico para diferentes anchos de bits ... sin embargo, recordé que en realidad sí para anchos de bits más pequeños que el de int: los números enteros pequeños se convierten primero en int(una regla extraña). Así que tengo que hacer la demostración con 32 bits (y luego se extiende a 64 bits, 128 bits, ...).
Matthieu M.
2
Dado que no puede evaluar todos los (4294967296 - 1) * (4294967296 - 1) resultados posibles, ¿reduce de alguna manera? En mi opinión, MAX debería ser (4294967296 - 1) si vas por ese camino, pero nunca terminará en nuestra vida como dijiste ... así que, después de todo, no podemos mostrar la igualdad en un experimento, al menos no en uno como tú. describir.
Willi Mentzel
1
Probar esto en la implementación del complemento de uno 2 no prueba que sea portátil para firmar la magnitud o el complemento de uno con anchos de tipo Deathstation 9000. por ejemplo, un tipo estrecho sin firmar podría ascender a 17 bits intque puede representar todo lo posible uint16_t, pero donde a+bpuede desbordarse. Eso es solo un problema para los tipos sin firmar más estrechos que int; C requiere que los unsignedtipos sean enteros binarios, por lo que el envolvente ocurre módulo una potencia de 2
Peter Cordes
1
Estuvo de acuerdo en que C es demasiado portátil para su propio bien. Sería realmente bueno si estandarizaran en complemento a 2, aritmética a la derecha para con signo y una forma de hacer aritmética con signo con semántica envolvente en lugar de semántica de comportamiento indefinido, para aquellos casos en los que desee envolver. Entonces, C podría volver a ser útil como un ensamblador portátil, en lugar de un campo minado gracias a los compiladores de optimización modernos que hacen que sea inseguro dejar cualquier comportamiento indefinido (al menos para su plataforma de destino. El comportamiento indefinido solo en implementaciones de Deathstation 9000 está bien, ya que señalar).
Peter Cordes
4

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 32 , 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 1 .


1 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.

chqrlie
fuente
3
Su segunda subbullet requiere (1) aes menor que int(2) inttiene 32 bits de valor (3) a=0xFFFFFFFF. No todos pueden ser verdad.
Barry
1
@Barry: El único caso que parece cumplir con los requisitos es el de 33 bits int, donde hay 32 bits de valor y un bit de signo.
Ben Voigt
2

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.

Loren Pechtel
fuente
1
El OP especificado: (ayb son enteros sin signo de 32 bits) . A menos que inttenga 33 bits de ancho, 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.
chqrlie
2

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.

Francesco Dondi
fuente
0

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.

usuario3728501
fuente
No, no lo haría. Char math ocurre ya que int y char podrían estar firmados.
Antti Haapala