((A + (b & 255)) & 255) est-il identique à ((a + b) & 255)?

92

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.

Martin
la source
4
Quelle langue est ce script? Renvoie-t-il Math.random()un entier ou un double sur [0,1)? Je ne pense pas que votre scénario (le mieux que je puisse dire) reflète le problème que vous avez posé.
Brick
7
Qu'est-ce que le code c / c ++? Ce sont des langages différents.
Weather Vane
14
Vous ne pouvez pas reproduire le comportement que vous essayez de tester dans JS. C'est pourquoi tout le monde n'est que vous sur le choix de la langue. JS n'est pas fortement typé et la réponse dépend essentiellement du type des variables en C / C ++. Le JS est un non-sens complet étant donné la question que vous avez posée.
Brick
4
@WeatherVane C'est un pseudo-code essentiel, utilisant les noms de fonction Javascript. Sa question porte sur le comportement de &et +sur les entiers non signés en C et C ++.
Barmar
11
Gardez à l'esprit que «j'ai écrit un programme de test et j'ai obtenu la réponse que j'attendais pour toutes les entrées possibles» n'est pas en fait une garantie que quelque chose se comporte comme vous le souhaitez. Un comportement indéfini peut être désagréable comme ça; ne donnant des résultats inattendus qu'après avoir fini de vous convaincre que votre code est correct.

Réponses:

78

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.

Bathsheba
la source
81
C'est une preuve mathématique, ignorant la possibilité de débordement. Considérez A=0xFFFFFFFF, B=1, C=3. La première identité ne tient pas. (Le débordement ne sera pas un problème pour l'arithmétique non signée, mais c'est un peu différent.)
AlexD
4
En fait, (a + (b & 255)) & 255est identique à (a + (b % 256)) % N % 256, où Nest un plus grand que la valeur non signée maximale. (cette dernière formule est censée être interprétée comme l'arithmétique des nombres entiers mathématiques)
17
De telles preuves mathématiques ne sont pas appropriées pour prouver le comportement d'entiers sur les architectures informatiques.
Jack Aidley
25
@JackAidley: Ils sont appropriés lorsqu'ils sont faits correctement (ce qui n'est pas le cas, car on néglige de considérer le débordement).
3
@Shaz: C'est vrai pour le script de test, mais cela ne fait pas partie de la question posée.
21

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.

plugwash
la source
20

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.
Barry
la source
17

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 n
  • 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.
Alain
la source
2
Il existe de nombreuses autres opérations en plus de l'addition où les déchets dans les bits hauts n'affectent pas le résultat dans les bits faibles qui vous intéressent. Voir cette Q&R sur le complément de 2 , qui utilise x86 asm comme cas d'utilisation, mais s'applique également à entiers binaires non signés dans toutes les situations.
Peter Cordes
2
Bien que chacun ait le droit de voter de manière anonyme, j'apprécie toujours un commentaire comme une opportunité d'apprendre.
alain
2
C'est de loin la réponse / l'argument le plus facile à comprendre, OMI. Le report / emprunt en addition / soustraction se propage uniquement des bits faibles aux bits hauts (de droite à gauche) en binaire, le même qu'en décimal. IDK pourquoi quelqu'un voterait contre cela.
Peter Cordes
1
@Bathsheba: CHAR_BIT n'est pas obligatoirement égal à 8. Mais les types non signés en C et C ++ doivent se comporter comme des entiers binaires base2 normaux d'une certaine largeur de bits. Je pense que cela nécessite que UINT_MAX soit 2^N-1. (N peut même pas être obligé d'être un multiple de CHAR_BIT, j'oublie, mais je suis à peu près sûr que la norme exige que le wraparound se produise modulo une puissance de 2.) Je pense que la seule façon d'obtenir de l'étrangeté est via la promotion à un type signé suffisamment large pour contenir aou bpas assez large pour contenir a+bdans tous les cas.
Peter Cordes
2
@Bathsheba: oui, heureusement, C-as-portable-assembly-language fonctionne vraiment principalement pour les types non signés. Même une implémentation C volontairement hostile ne peut pas briser cela. Ce ne sont que des types signés où les choses sont horribles pour les bits-hacks vraiment portables en C, et un Deathstation 9000 peut vraiment casser votre code.
Peter Cordes
14

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

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


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

Matthieu M.
la source
1
vous dites que c'est facile à faire avec des valeurs 32 bits mais en fait utiliser 16 bits ...: D
Willi Mentzel
1
@WilliMentzel: C'est une remarque intéressante. Je voulais initialement dire que si cela fonctionne avec 16 bits, il fonctionnera de la même manière avec 32 bits, 64 bits et 128 bits car le Standard n'a pas de comportement spécifique pour différentes largeurs de bits ... mais je me suis souvenu qu'il le fait réellement pour des largeurs de bits inférieures à celle de int: les petits entiers sont d'abord convertis en int(une règle étrange). Donc je dois en fait faire la démonstration avec 32 bits (et après ça s'étend à 64 bits, 128 bits, ...).
Matthieu M.
2
Puisque vous ne pouvez pas évaluer tous les (4294967296 - 1) * (4294967296 - 1) résultats possibles, vous réduisez en quelque sorte? Je pense que MAX devrait être (4294967296 - 1) si vous allez dans cette direction, mais cela ne se terminera jamais de notre vivant comme vous l'avez dit ... donc, après tout, nous ne pouvons pas montrer l'égalité dans une expérience, du moins pas dans une expérience comme vous décris.
Willi Mentzel
1
Tester cela sur l'implémentation du complément de one 2 ne prouve pas qu'il est portable à la grandeur de signe ou au complément à un avec des largeurs de type Deathstation 9000. par exemple, un type non signé étroit pourrait passer à un 17 bits intqui peut représenter tous les possibles uint16_t, mais où a+bpeut déborder. Ce n'est un problème que pour les types non signés plus étroits que int; C exige que les unsignedtypes soient des entiers binaires, donc le wraparound se produit modulo une puissance de 2
Peter Cordes
1
D'accord sur le fait que C est trop portable pour son propre bien. Ce serait vraiment bien s'ils normalisaient le complément de 2, les décalages arithmétiques vers la droite pour les signés et un moyen de faire de l'arithmétique signée avec une sémantique d'emballage au lieu d'une sémantique à comportement indéfini, pour les cas où vous voulez un wrapping. Ensuite, C pourrait à nouveau être utile en tant qu'assembleur portable, au lieu d'un champ de mines grâce à des compilateurs d'optimisation modernes qui rendent dangereux de laisser un comportement non défini (au moins pour votre plate-forme cible. Un comportement non défini uniquement sur les implémentations de Deathstation 9000 est correct, car vous signaler).
Peter Cordes
4

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


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

chqrlie
la source
3
Votre 2ème sous-puce requiert (1) aest plus petit que int(2) inta 32 bits de valeur (3) a=0xFFFFFFFF. Tout cela ne peut pas être vrai.
Barry
1
@Barry: Le seul cas qui semble répondre aux exigences est 33 bits int, où il y a 32 bits de valeur et un bit de signe.
Ben Voigt
2

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.

Loren Pechtel
la source
1
L'OP spécifié: (a et b sont des entiers non signés de 32 bits) . À moins d'avoir une intlargeur de 33 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.
chqrlie
2

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

Francesco Dondi
la source
0

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.

user3728501
la source
Non, ce ne serait pas le cas. Le calcul des caractères se produit comme int et char peut être signé.
Antti Haapala