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

Question

J'ai été la navigation sur certains de code C++, et 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 32 bits sont des entiers non signés)

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

Pendant que le script a confirmé mon hypothèse (les deux opérations sont égales), je n'ai toujours pas confiance en elle, parce que 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 Lisp-y titre. N'hésitez pas à modifier.

Answer 1

Ils sont les mêmes. Voici une preuve:

D'abord noter l'identité de l' (A + B) mod C = (A mod C + B mod C) mod C

Nous allons reformuler le problème en considérant a & 255 comme pour l' a % 256. C'est vrai que a n'est pas signé.

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

C'est le même que (a % 256 + b % 256 % 256) % 256 (j'ai appliqué l'identité indiqué ci-dessus: a noter qu' mod et % sont équivalents pour les types non signés.)

Cela simplifie d' (a % 256 + b % 256) % 256 qui devient (a + b) % 256 (réapplication de l'identité). Vous pouvez ensuite mettre le bit à bit opérateur de retour pour donner

(a + b) & 255

terminer la preuve.

Answer 2

En position d'addition, de soustraction et de multiplication de chiffres significatifs de l'entrée n'affectent pas moins de chiffres significatifs du résultat. Cela s'applique à l'arithmétique binaire comme beaucoup comme il le fait pour l'arithmétique décimale.

Cependant il faut être prudent lors de la prise des règles de l'arithmétique binaire et de les appliquer à C (je crois C++ a les mêmes règles que C sur ce genre de choses mais je ne suis pas sûr à 100%) car C arithmétique a quelques arcanes des règles qui peuvent nous faire trébucher. Unsigned arithmétique dans C suit binaire simple enveloppante règles, mais signé de dépassement de capacité arithmétique est un comportement indéterminé. Pire, dans certaines circonstances, C sera automatiquement "promouvoir" un type non signé (signé) int.

Comportement indéfini en C peut être particulièrement insiduous. Un muet compilateur (ou d'un compilateur à un faible niveau d'optimisation) est susceptible de faire quoi vous attendre selon votre compréhension de l'arithmétique binaire alors qu'une optimisation du compilateur peut casser votre code d'étrange façon.

---

Donc, pour en revenir à la formule de la question de la equivilence dépend de l'opérande types.

Si ils sont des entiers non signés dont la taille est supérieure ou égale à la taille de l' int puis le dépassement de comportement de l'opérateur d'addition est bien défini comme binaire simple enveloppante. Si ou pas nous masquer la haute 24 bits d'une opérande avant l'opération d'addition n'a pas d'impact sur les bits de poids faible du résultat.

Si ils sont des entiers non signés dont la taille est inférieure à int alors qu'ils seront promus (signé) int. Le débordement des entiers signés est un comportement indéterminé, mais au moins sur chaque plate-forme, j'ai rencontré la différence de taille entre les différents types d'entiers est suffisamment grand pour un simple ajout de deux promu les valeurs ne sera pas provoquer un débordement. Donc encore une fois, nous pouvons revenir à la simple arithmétique binaire argument pour considérer les déclarations équivalent.

Si elles sont signées entiers dont la taille est inférieure à int puis de nouveau débordement ne peut pas se produire et sur les deux-compléter les implémentations que nous pouvons compter sur le standard de l'arithmétique binaire argument pour dire qu'ils sont équivalent. Sur signe-amplitude ou de compléter les implémentations ils ne seraient pas équivalent.

Otoh, que si a et b ont été signés entiers dont la taille était supérieure ou égale à la taille d'un int alors même sur le complément à deux implémentations il y a des cas où l'on serait bien définis, tandis que l'autre serait un comportement indéterminé.

Answer 3

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

Unsigned a peut être réécrit en m * 0x100 + b certains unsigned m,b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Il résulte de ces deux définitions que l' a & 255 == b == a % 256.

En outre, nous avons besoin de:

• la distribution de la propriété: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• la définition de la non signé de plus, 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

Donc oui, c'est vrai. Pour les non signé de 32 bits entiers.

---

Quels sont les autres types d'entiers?

• Pour la version 64 bits des entiers non signés, tous les ci-dessus s'applique tout aussi bien, juste substituant 2^64 pour 2^32.
• 8 et 16 bits entiers non signés, plus implique la promotion d' int. Cette int sera certainement ni de débordement ou négatifs dans l'une de ces opérations, de sorte qu'ils restent valides.
• Pour signé entiers, si a+b ou a+(b&255) de dépassement, c'est un comportement indéfini. Si l'égalité ne peut pas tenir - il y a des cas où l' (a+b)&255 est un comportement indéfini, mais (a+(b&255))&255 ne l'est pas.

Answer 4

Oui, (a + b) & 255 est fine.

Rappelez-vous plus à l'école? Vous ajoutez des numéros de chiffre par chiffre, et ajouter un report de la valeur à la prochaine colonne de chiffres. Il n'y a aucun moyen pour un plus tard (plus importante) de la colonne de chiffres à l'influence déjà traité de la colonne. De ce fait, il ne fait pas une différence si vous zéro-les chiffres que dans le résultat, ou aussi la première dans un argument.

---

Le ci-dessus n'est pas toujours vrai, la norme C++ permet une mise en œuvre qui permettrait de briser ce.

Une telle Deathstation 9000 :-) faudrait utiliser un 33 bits int, si l'OP signifiait unsigned short avec "non signé de 32 bits entiers". Si unsigned int a été signifié, le DS9K auriez à utiliser une version 32 bits de int, et un 32 bits unsigned int avec un peu de rembourrage. (Les entiers non signés doivent avoir la même taille que leurs signé homologues, en vertu du §3.9.1/3, et le remplissage des bits sont autorisés dans le §3.9.1/1.) D'autres combinaisons de tailles et de rembourrage bits serait trop de travail.

Aussi loin que je peux dire, ce est la seule façon de le casser, parce que:

• La représentation entière doit utiliser un "purement binaire" schéma de codage (§3.9.1/7 et la note de bas de page), tous les bits sauf padding bits et le bit de signe, doivent contribuer à une valeur de 2ⁿ
• int promotion est autorisé que si l' int peut représenter toutes les valeurs du type de source (§4.5/1), de sorte int doit avoir au moins 32 bits contribuant à la valeur, plus un bit de signe.
• l' int ne peut pas avoir plus de valeur bits (sans compter le bit de signe) de 32, parce que d'autre un peut plus de ne pas déborder.

Answer 5

Vous avez déjà la puce réponse: non signé de l'arithmétique modulo arithmétique et, par conséquent, les résultats seront en attente, vous pouvez le prouver mathématiquement...

---

Une chose cool à 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 laps de temps raisonnable (ne pas essayer avec la version 64 bits).

Donc, dans votre cas, personnellement, j'aime juste le jeter à un ordinateur; il me prend moins de temps à me convaincre que le programme est correct qu'il n'en faut pour me convaincre que la preuve mathématique est correct et que je n'ai pas de superviser un détail dans le cahier des charges¹:

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

Cette énumère toutes les valeurs possibles de l' a et b dans le 32 bits de l'espace et vérifie si l'égalité tient ou pas. Si elle ne le fait pas, il imprime les cas qui n'ont pas de travail, que vous pouvez utiliser comme un test de cohérence.

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

En outre, étant donné que les règles arithmétiques sont des bits de largeur agnostique (ci-dessus int de largeur de bit), cette égalité sera pour tout type entier non signé de 32 bits ou plus, y compris 64 bits et 128 bits.

Remarque: Comment un compilateur énumère tous les 64 bits de motifs dans un délai raisonnable? Il ne peut pas. Les boucles ont été optimisés. Sinon nous serions tous morts avant l'exécution terminée.

---

Au départ, j'ai seulement joué pendant 16-bits entiers non signés; malheureusement, le C++ est un fou de la langue où les petits entiers (petites bitwidths qu' int) sont d'abord converties 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;
}

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

Eh bien, là vous allez :)

---

¹bien sûr, si un programme de jamais, par inadvertance, déclenche un Comportement Indéfini, il ne serait pas s'avérer beaucoup.