((A + (b & 255)) & 255) est-il 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

( aet bsont des entiers non signés 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 ait confirmé mon hypothèse (les deux opérations sont égales), je ne lui fais toujours pas confiance, car 1) aléatoire 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

Répétons le problème en considérant a & 255comme un substitut a % 256. Cela est vrai car an'est pas signé.

Ainsi (a + (b & 255)) & 255est(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 modet %sont équivalents pour les types non signés.)

Cela simplifie à (a % 256 + b % 256) % 256qui devient (a + b) % 256(réappliquer l'identité). Vous pouvez ensuite remettre l'opérateur bit à bit pour donner

(a + b) & 255

compléter la preuve.

Dans l'addition positionnelle, la soustraction et la multiplication de nombres non signés pour produire des résultats non signés, les chiffres plus significatifs de l'entrée n'affectent pas les chiffres moins significatifs du résultat. Cela s'applique autant à l'arithmétique binaire qu'à l'arithmétique décimale. Elle s'applique également à l'arithmétique signée «complément à deux», mais pas à l'arithmétique signée de grandeur de signe.

Cependant, nous devons être prudents lorsque nous prenons des règles de l'arithmétique binaire et les appliquons à C (je crois que C ++ a les mêmes règles que C sur ce sujet mais je ne suis pas sûr à 100%) car l'arithmétique C a des règles arcanes qui peuvent nous trébucher vers le haut. L'arithmétique non signée en C suit des règles simples de wraparound binaire, mais le débordement arithmétique signé est un comportement non défini. Pire dans certaines circonstances, C "promouvra" automatiquement un type non signé en int (signé).

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

Donc, pour revenir à la formule de la question, l'équivilence dépend des types d'opérandes.

S'il s'agit d'entiers non signés dont la taille est supérieure ou égale à la taille de, intle comportement de dépassement de capacité de l'opérateur d'addition est bien défini comme un simple bouclage binaire. Le fait que nous masquions ou non les 24 bits hauts d'un opérande avant l'opération d'addition n'a aucun impact sur les bits bas du résultat.

S'il s'agit d'entiers non signés dont la taille est inférieure à, intils seront promus (signés) int. Le débordement d'entiers signés est un comportement indéfini, mais au moins sur chaque plate-forme que j'ai rencontrée, la différence de taille entre les différents types d'entiers est suffisamment importante pour qu'une seule addition de deux valeurs promues ne provoque pas de débordement. Donc, encore une fois, nous pouvons revenir à l'arithmétique simplement binaire pour juger les déclarations équivalentes.

Si ce sont des entiers signés dont la taille est inférieure à int, alors le débordement ne peut pas se produire et sur les implémentations à complément de deux, nous pouvons nous fier à l'arithmétique binaire standard pour dire qu'ils sont équivilents. Sur la magnitude du signe ou les implémentations complémentaires, elles ne seraient pas équivoques.

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

Lemme: a & 255 == a % 256pour non signé a.

Unsigned apeut être réécrite comme m * 0x100 + bcertains non signés m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Il découle des deux définitions que a & 255 == b == a % 256.

De plus, nous avons besoin de:

• la propriété distributive: (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)

Donc:

(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

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, tous les cas ci - dessus 64 bits aussi bien, tout en substituant 2^64à 2^32.
• Pour les entiers non signés 8 et 16 bits, l'addition implique la promotion vers int. Cela intne débordera certainement ni ne sera négatif dans aucune de ces opérations, elles restent donc toutes valides.
• Pour les entiers signés , en cas de dépassement a+bou de a+(b&255)dépassement, c'est un comportement non défini. Donc, l'égalité ne peut pas tenir - il y a des cas où il (a+b)&255y a un comportement indéfini mais (a+(b&255))&255pas.

Oui, (a + b) & 255ça va.

Tu te souviens de l'addition à l'école? Vous ajoutez des nombres chiffre par chiffre et ajoutez une valeur de report à la colonne de chiffres suivante. Il n'y a aucun moyen pour une colonne de chiffres ultérieure (plus significative) d'influencer une colonne déjà traitée. Pour cette raison, cela ne fait aucune différence si vous mettez à zéro les chiffres uniquement dans le résultat, ou également en premier dans un argument.

Ce qui précède n'est pas toujours vrai, la norme C ++ autorise une implémentation qui briserait cela.

Un tel Deathstation 9000 : - ) devrait utiliser un 33 bits int, si l'OP signifiait unsigned shortavec des "entiers non signés 32 bits". Si cela unsigned intétait voulu, le DS9K devrait utiliser un 32 bits intet un 32 bits unsigned intavec un bit de remplissage. (Les entiers non signés doivent avoir la même taille que leurs homologues signés selon le §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 la seule façon de le casser, car:

• La représentation entière doit utiliser un schéma de codage "purement binaire" (§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 contribuer à une valeur de 2 ⁿ
• La promotion int n'est autorisée que si intpeut représenter toutes les valeurs du type source (§4.5 / 1), donc intdoit avoir au moins 32 bits contribuant à la valeur, plus un bit de signe.
• le intne 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 l'arithmétique modulo et donc les résultats tiendront, 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 qu'il est possible d'énumérer toutes les combinaisons valides de 32 bits dans un laps de temps raisonnable (n'essayez pas avec 64 bits).

Donc, dans votre cas, j'aime 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 me convaincre que la preuve mathématique est correcte et que je n'ai pas supervisé un détail dans la spécification ¹ :

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

Cela énumère toutes les valeurs possibles de aet bdans l'espace de 32 bits et vérifie si l'égalité est vraie ou non. Si ce n'est pas le cas, il imprime le cas qui n'a pas fonctionné, que vous pouvez utiliser comme contrôle de cohérence.

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

En outre, étant donné que les règles arithmétiques sont indépendantes de la largeur en bits (au int- dessus de la largeur en bits), 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.

Au départ, je ne l'ai prouvé que pour les entiers non signés 16 bits; Malheureusement, C ++ est un langage insensé dans lequel les petits entiers (plus petits bits que int) sont d'abord convertis 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;
}

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

Eh bien, voilà :)

¹ Bien sûr, si un programme déclenche par inadvertance un comportement indéfini, cela ne prouverait pas grand-chose.

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

• puisque aet bsont des entiers non signés 32 bits, le résultat est le même même en cas de débordement. 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 le nombre qui est supérieur à la plus grande valeur pouvant être représentée par le type résultant.

La réponse longue est: il n'y a pas de plates-formes connues 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 aet b(entiers 32 bits non signés) a un rang supérieur à int, le calcul est effectué comme non signé, modulo 2 ³² , et il donne le même résultat défini pour les deux expressions pour toutes les valeurs de aet b.

• Inversement, si le type de aet best plus petit que int, les deux sont promus vers intet le calcul est effectué à l'aide de l'arithmétique signée, où le débordement appelle un comportement non défini.

  • Si inta 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 inta exactement 32 bits de valeur, le calcul peut déborder pour les deux expressions, par exemple des valeurs a=0xFFFFFFFFet b=1provoquerait 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'existe pas de telles plates-formes ¹ .

¹ Plus précisément, aucune plate - forme réelle existe, mais on peut configurer un DS9K pour présenter un tel comportement et se conformer toujours à la norme C.

Identique en supposant aucun débordement . Aucune des deux versions n'est vraiment à l'abri du débordement, mais la version double et y est plus résistante. 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 faire cela au cas où il y en aurait un.

Oui, vous pouvez le prouver avec l'arithmétique, mais il existe une réponse plus intuitive.

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

Par conséquent, tout ce que vous faites aux bits les plus élevés avant l'ajout ne changera pas le résultat, tant que vous ne gardez que les bits moins significatifs que le bit le plus bas modifié.

La preuve est triviale et laissée comme exercice au lecteur

Mais pour légitimer cela comme une réponse, votre première ligne de code dit de prendre les 8 derniers bits de b** (tous les bits supérieurs de l' bensemble à zéro) et de les ajouter a, puis de ne prendre que les 8 derniers bits du paramètre de résultat, tous plus élevés bits à zéro.

La deuxième ligne dit ajouter aet bprendre 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 la sortie serait équivalente à

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

Comme ci-dessus, seuls les 8 LSB sont significatifs, mais le résultat est un unsigned intavec tous les autres bits à zéro. La a + bvolonté débordera, produisant le résultat attendu.