operator - xor c++

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

Question

Estaba buscando 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

( b son enteros sin signo de 32 bits)

Rápidamente escribí 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 ello, porque 1) al random y 2) no soy matemático, no tengo idea de lo que estoy haciendo .

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

Answer 1

Ellos son lo mismo. Aquí hay una prueba:

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

Volvamos a plantear el problema considerando a & 255 como a % 256 . Esto es cierto ya que a no está firmado.

Entonces (a + (b & 255)) & 255 es (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 mod y % son equivalentes para tipos sin signo).

Esto se simplifica a (a % 256 + b % 256) % 256 que se convierte en (a + b) % 256 (volver a aplicar la identidad). Luego puede volver a colocar el operador bit a bit para dar

(a + b) & 255

completando la prueba.

Answer 2

En la suma posicional, la resta y la 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, 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 C tiene algunas reglas arcanas que pueden hacernos tropezar. arriba. La aritmética sin signo en C sigue reglas simples de ajuste binario, pero el desbordamiento aritmético con signo es un comportamiento indefinido. Peor aún, en algunas circunstancias, C "promocionará" automáticamente un tipo sin signo a int (firmado).

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

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

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

Si son enteros sin signo cuyo tamaño es menor que int entonces serán promovidos a int (con signo). El desbordamiento de enteros con signo es un comportamiento indefinido, pero al menos en cada plataforma que he encontrado, la diferencia de tamaño entre los diferentes tipos de enteros es lo suficientemente grande como para que una sola adición de dos valores promocionados no cause un 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, nuevamente no puede ocurrir un desbordamiento y en implementaciones de dos complementos podemos confiar en el argumento aritmético binario estándar para decir que son equitativos. En implementaciones de signo-magnitud o complementarias, no serían equitativas.

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

Answer 3

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

Answer 4

La respuesta rápida es: ambas expresiones son equivalentes

• Como 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 difieran, pero el Estándar 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 sin signo, módulo 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 se promueven a int y el cálculo se realiza utilizando aritmética con signo, 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 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 ) para exhibir tal comportamiento y aún cumplir con el Estándar C.

Answer 5

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

Sin signo a puede reescribirse como m * 0x100 + b algunos 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 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

Entonces 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 también se aplica, solo sustituyendo 2^64 por 2^32 .
• Para enteros sin signo de 8 y 16 bits, la suma implica la promoción a int . Este 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) desbordan, es un comportamiento indefinido. Por lo tanto, la igualdad no puede sostenerse: hay casos en los que (a+b)&255 es un comportamiento indefinido pero (a+(b&255))&255 no lo es.

Answer 6

Sí, (a + b) & 255 está 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 int 33 bits, si el OP significaba unsigned short con "enteros sin signo de 32 bits". Si se quiso decir unsigned int , el DS9K tendría que usar un int 32 bits y un unsigned int 32 bits con un bit de relleno. (Se requiere que los enteros sin signo tengan el mismo tamaño que sus homólogos con signo según §3.9.1 / 3, y los bits de relleno están permitidos en §3.9.1 / 1.) También funcionarían otras combinaciones de tamaños y bits de relleno.

Por lo que puedo decir, esta es la única forma 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 se permite si int puede representar todos los valores del tipo de fuente (§4.5 / 1), por lo que int debe tener al menos 32 bits que contribuyan al valor, más un bit de signo.
• 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.

Answer 7

Sí, puedes probarlo con la 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, lo que sea que haga a los bits más altos antes de la adición no cambiará el resultado, siempre que solo mantenga bits menos significativos que el bit más bajo modificado.

Answer 8

Ya tiene la respuesta inteligente: la aritmética sin signo es módulo aritmético y, por lo tanto, los resultados se mantendrán, puede probarlo matemáticamente ...

Sin embargo, una cosa genial sobre 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 tiempo razonable (no intente con 64 bits).

Entonces, en su caso, personalmente me gusta simplemente tirarlo a una computadora; Me lleva menos tiempo convencerme de que el programa es correcto de lo que me lleva 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 a y b en el espacio de 32 bits y verifica si la igualdad se mantiene o no. Si no lo hace, imprime el caso que no funcionó, que puede usar como un control de cordura.

Y, según Clang : la igualdad es válida .

Además, dado que las reglas aritméticas son independientes del ancho de bits (por encima del ancho de bits int ), 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 período de tiempo razonable? No puede. Los bucles fueron optimizados. 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 enteros pequeños (anchos de bits más pequeños que int ) se convierten primero en 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 es válida .

Bueno, allá vas :)

¹ Por supuesto, si un programa desencadena inadvertidamente un comportamiento indefinido, no probaría mucho.

Answer 9

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 que tome los últimos 8 bits de b ** (todos los bits superiores de b ponen a cero) y agregue esto a b luego tome solo los últimos 8 bits del resultado poniendo todos los bits más altos a cero.

La segunda línea dice que agregue b y tome los últimos 8 bits con todos los bits más altos cero.

Solo los últimos 8 bits son significativos en el resultado. Por lo tanto, solo los últimos 8 bits son significativos en las entradas.

** últimos 8 bits = 8 LSB

También es interesante observar 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.