Est-ce que ((a + (b & 255)) & 255) est identique à ((a + b) & 255)?

Je parcourais du code C ++ et j’ai trouvé quelque chose comme ceci:

(a + (b & 255)) & 255 

Le double ET m’a ennuyé, alors j’ai pensé à:

 (a + b) & 255 

( a et b sont des entiers non signés de 32 bits)

J’ai rapidement écrit un script de test (JS) pour confirmer ma théorie:

 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; } } 

Bien que le script confirme mon hypothèse (les deux opérations sont égales), je n’en ai toujours pas confiance, car 1) au hasard et 2) je ne suis pas mathématicien, je n’ai aucune idée de ce que je fais .

Aussi, désolé pour le titre Lisp-y. N’hésitez pas à le modifier.

Ce sont les mêmes. Voici une preuve:

Notez d’abord l’identité (A + B) mod C = (A mod C + B mod C) mod C

Reprenons le problème en considérant a & 255 comme a % 256 . Ceci est vrai car a est non signé.

Donc (a + (b & 255)) & 255 est (a + (b % 256)) % 256

C’est la même chose que (a % 256 + b % 256 % 256) % 256 (j’ai appliqué l’identité indiquée ci-dessus: notez que mod et % sont équivalents pour les types non signés.)

Cela simplifie à (a % 256 + b % 256) % 256 qui devient (a + b) % 256 (réapplication de l’identité). Vous pouvez ensuite remettre l’opérateur binary pour donner

(a + b) & 255

remplir la preuve.

Dans l’addition positionnelle, la soustraction et la multiplication, des chiffres plus significatifs de l’entrée n’affectent pas les chiffres moins significatifs du résultat. Cela s’applique à l’arithmétique binary autant qu’à l’arithmétique décimale.

Cependant, nous devons faire attention lorsque nous prenons des règles à partir de l’arithmétique binary et que nous les appliquons à C (je pense que C ++ a les mêmes règles que C sur ce genre de choses, mais je ne suis pas sûr à 100%) en haut L’arithmétique non signée dans C suit de simples règles enveloppantes binarys, mais le dépassement arithmétique signé est un comportement indéfini. Pire dans certaines circonstances, C “promouvra automatiquement” un type non signé en (signé) int.

Un comportement indéfini en C peut être particulièrement insidieux. Un compilateur stupide (ou un compilateur à un niveau d’optimisation faible) est susceptible de faire ce que vous attendez en fonction de votre compréhension de l’arithmétique binary tandis qu’un optimiseur de compilateur peut casser votre code de manière étrange.


Donc, revenir à la formule dans la question, l’équivilence dépend des types d’opérandes.

Si ce sont des entiers non signés dont la taille est supérieure ou égale à la taille de int le comportement de débordement de l’opérateur d’addition est bien défini comme un simple enveloppement binary. Que nous masquions ou non les 24 bits supérieurs d’un opérande avant l’opération d’ajout n’a aucun impact sur les bits faibles du résultat.

Si ce sont des entiers non signés dont la taille est inférieure à int ils seront promus en (signé) int . Le débordement d’entiers signés est un comportement indéfini, mais au moins sur chaque plate-forme, la différence de taille entre différents types d’entiers est suffisamment importante pour qu’une addition unique de deux valeurs promues ne provoque pas de débordement. Donc, encore une fois, nous pouvons revenir à l’arithmétique simplement binary pour considérer les instructions comme équivalentes.

Si ce sont des entiers signés dont la taille est inférieure à int, le débordement ne peut pas se produire et sur les implémentations à deux complément, nous pouvons nous appuyer sur l’argument arithmétique binary standard pour dire qu’ils sont équivalents. Sur l’amplitude des signes ou les mises en œuvre complémentaires, elles ne seraient pas équivalentes.

OTOH si a et b étaient des entiers signés dont la taille était supérieure ou égale à la taille de int, même sur deux implémentations du complément, il y a des cas où une instruction serait bien définie tandis que l’autre serait un comportement indéfini.

Lemme: a & 255 == a % 256 pour unsigned a .

Non signé a peut être réécrit comme m * 0x100 + b peu non signé m , b , 0 <= b < 0xff , 0 <= m <= 0xffffff . Il résulte des deux définitions que a & 255 == b == a % 256 .

De plus, nous avons besoin de:

  • la propriété dissortingbutive: (a + b) mod n = [(a mod n) + (b mod n)] mod n
  • la définition de l'addition non signée, mathématiquement: (a + b) ==> (a + b) % (2 ^ 32)

Ainsi:

 (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 // Dissortingbutive = ((a % 256) + (b % 256)) % 256 // a mod n mod n = a mod n = (a + b) % 256 // Dissortingbutive again = (a + b) & 255 // lemma 

Alors oui, c'est vrai. Pour les entiers non signés 32 bits.


Qu'en est-il des autres types d'entiers?

  • Pour les entiers non signés 64 bits, tout ce qui précède s’applique aussi bien, en substituant simplement 2^64 à 2^32 .
  • Pour les entiers non signés de 8 et 16 bits, l'addition implique une promotion sur int . Cet int ne va certainement pas déborder ou être négatif dans aucune de ces opérations, elles restnt donc toutes valides.
  • Pour les entiers signés , si a+b ou a+(b&255) débordent, il s'agit d'un comportement indéfini. Donc, l'égalité ne peut pas tenir - il y a des cas où (a+b)&255 est un comportement indéfini mais (a+(b&255))&255 ne l'est pas.

Oui, (a + b) & 255 c’est bien.

Rappelez-vous l’addition à l’école? Vous ajoutez des nombres chiffre par chiffre et ajoutez une valeur de report à la prochaine colonne de chiffres. Une colonne de chiffres ultérieure (plus importante) n’a aucun moyen d’influencer une colonne déjà traitée. De ce fait, cela ne fait aucune différence si vous mettez à zéro les chiffres uniquement dans le résultat, ou aussi en premier dans un argument.


Ce qui précède n’est pas toujours vrai, le standard C ++ permet une implémentation qui romprait cela.

Un tel Deathstation 9000 : – ) devrait utiliser un int 33 bits, si l’OP signifiait un unsigned short avec des “entiers non signés de 32 bits”. Si unsigned int était utilisé, le DS9K devrait utiliser un int 32 bits et un unsigned int 32 bits avec un bit de remplissage. (Les entiers non signés doivent avoir la même taille que leurs homologues signés conformément au §3.9.1 / 3, et les bits de remplissage sont autorisés au §3.9.1 / 1.) D’autres combinaisons de tailles et de bits de remplissage fonctionneraient également.

Pour autant que je sache, c’est le seul moyen de le casser, car:

  • La représentation entière doit utiliser un schéma de codage “purement binary” (§3.9.1 / 7 et la note de bas de page), tous les bits sauf les bits de remplissage et le bit de signe doivent consortingbuer à la valeur 2 n
  • int promotion n’est autorisée que si int peut représenter toutes les valeurs du type source (§4.5 / 1), donc int doit avoir au moins 32 bits consortingbuant à la valeur, plus un bit de signe.
  • l’ int ne peut pas avoir plus de bits de valeur (sans compter le bit de signe) que 32, car sinon un ajout ne peut pas déborder.

Vous avez déjà la réponse intelligente: l’arithmétique non signée est une arithmétique modulo et par conséquent les résultats seront conservés, vous pouvez le prouver mathématiquement …


Une chose intéressante à propos des ordinateurs, cependant, est que les ordinateurs sont rapides. En effet, ils sont si rapides que l’énumération de toutes les combinaisons valides de 32 bits est possible dans un délai raisonnable (n’essayez pas avec 64 bits).

Donc, dans votre cas, je préfère personnellement le lancer sur un ordinateur; il me faut moins de temps pour me convaincre que le programme est correct qu’il n’en faut pour se convaincre que la preuve mathématique est correcte et que je n’ai pas supervisé un détail dans la spécification 1 :

 #include  #include  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(i); std::uint32_t const b = static_cast(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; } 

Cela énumère toutes les valeurs possibles de a et b dans l'espace de 32 bits et vérifie si l'égalité est valide ou non. Si ce n'est pas le cas, il imprime le cas qui n'a pas fonctionné, que vous pouvez utiliser comme un test d'intégrité.

Et, selon Clang : L' égalité tient .

De plus, étant donné que les règles arithmétiques sont indépendantes de la largeur de bit (au-dessus de la largeur du bit), cette égalité sera valable pour tout type entier non signé de 32 bits ou plus, y compris 64 bits et 128 bits.

Remarque: Comment un compilateur peut-il énumérer tous les modèles 64 bits dans un délai raisonnable? Ça ne peut pas. Les boucles ont été optimisées. Sinon, nous serions tous morts avant la fin de l’exécution.


Je l'ai d'abord prouvé pour les entiers non signés de 16 bits; Malheureusement, C ++ est un langage insensé où de petits entiers (de plus petites largeurs de bits que l' int ) sont d'abord convertis en int .

 #include  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(i); std::uint16_t const b = static_cast(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; } 

Et encore une fois, selon Clang : L' égalité tient .

Eh bien, voilà 🙂


1 Bien sûr, si un programme déclenche un comportement indéfini par inadvertance, cela ne sera pas très utile.

La réponse rapide est: les deux expressions sont équivalentes

  • Puisque a et b sont des entiers non signés de 32 bits, le résultat est le même, même en cas de dépassement de capacité. l’arithmétique non signée garantit ceci: un résultat qui ne peut pas être représenté par le type entier non signé résultant est réduit modulo par le nombre supérieur à celui qui peut être représenté par le type résultant.

La longue réponse est la suivante: il n’existe pas de plate-forme connue où ces expressions seraient différentes, mais la norme ne le garantit pas, en raison des règles de promotion intégrale.

  • Si le type de a et b (entiers 32 bits non signés) a un rang supérieur à int , le calcul est effectué comme non signé, modulo 2 32 et donne le même résultat défini pour les deux expressions pour toutes les valeurs de a et b .

  • Inversement, si le type de a et b est plus petit que int , les deux sont promus dans int et le calcul est effectué en utilisant l’arithmétique signée, où le débordement appelle un comportement indéfini.

    • Si int a au moins 33 bits de valeur, aucune des expressions ci-dessus ne peut déborder, donc le résultat est parfaitement défini et a la même valeur pour les deux expressions.

    • Si int a exactement 32 bits de valeur, le calcul peut déborder pour les deux expressions, par exemple les valeurs a=0xFFFFFFFF et b=1 provoqueraient un débordement dans les deux expressions. Pour éviter cela, vous devez écrire ((a & 255) + (b & 255)) & 255 .

  • La bonne nouvelle est qu’il n’y a pas de telles plateformes 1 .


1 Plus précisément, aucune plate-forme réelle de ce type n’existe, mais il est possible de configurer un DS9K pour qu’il présente un tel comportement tout en restant conforme à la norme C.

Identique en supposant aucun débordement . Aucune des deux versions n’est vraiment à l’abri des débordements, mais le double et la version lui sont plus résistants. Je ne suis pas au courant d’un système où un débordement dans ce cas est un problème, mais je peux voir l’auteur le faire au cas où il y en aurait un.

Oui, vous pouvez le prouver avec l’arithmétique, mais il y a une réponse plus intuitive.

Lors de l’ajout, chaque bit n’influence que les plus importants que lui-même; jamais ceux moins importants.

Par conséquent, tout ce que vous faites sur les bits supérieurs avant l’ajout ne changera pas le résultat, tant que vous ne conserverez que des bits moins importants que le bit modifié le plus bas.

La preuve est sortingviale et laissée comme un exercice pour le lecteur

Mais pour légitimer cela comme une réponse, votre première ligne de code dit prendre les 8 derniers bits de b ** (tous les bits supérieurs de b mis à zéro) et append ceci à a et prendre seulement les 8 derniers bits du résultat. mettre tous les bits supérieurs à zéro.

La deuxième ligne indique a et b et prend les 8 derniers bits avec tous les bits supérieurs zéro.

Seuls les 8 derniers bits sont significatifs dans le résultat. Par conséquent, seuls les 8 derniers bits sont significatifs dans la ou les entrées.

** 8 derniers bits = 8 LSB

Il est également intéressant de noter que le résultat serait équivalent à

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

Comme ci-dessus, seuls les 8 bits LSB sont significatifs, mais le résultat est un unsigned int avec tous les autres bits nuls. Le a + b va déborder, produisant le résultat attendu.