Est-ce que XOR de deux entiers peut sortir des limites?

le résultat ne peut jamais être" trop grand "dans le sens de sa représentation nécessitant plus de bits que int fournit, puisque l'opération est définie pour combiner les valeurs de bits de ses opérandes, ne pas produire de nouveaux bits. Peut-être une meilleure question pourrait-elle être, le résultat peut-il être autre chose qu'une représentation valide de valeur d'un int ?

pour les entiers non signés, no. Tous les modèles de bits, et donc le résultat de toutes les opérations bitwise, sont des valeurs valides représentation.

pour les entiers signés, cela dépend de la représentation des valeurs négatives définie par l'implémentation. Chaque implémentation que vous êtes susceptible de rencontrer utilise le complément 2's -, dans lequel encore une fois chaque motif bit est valide; donc, encore une fois, le résultat de toute opération bitwise sera une représentation valide.

cependant, la norme permet également d'autres représentations, dans lesquelles il peut y avoir un ou plusieurs motifs de bits invalides. Dans ce cas, il est possible pour une opération bitwise, avec deux opérandes valides, pour produire Ce modèle, et donc produire un résultat invalide.

(Ce poste s'applique à C, pas du C++)

les opérateurs dans le sens des bits ne peuvent pas provoquer une représentation de trap en raison du réglage de bits de rembourrage invalides, voir C11 6.2.6.2/1 note de bas de page:

... aucune opération arithmétique sur des valeurs valides ne peut générer un piège représentation...

(le sens de" opération arithmétique " n'est pas clair mais l'index est lié au 6.5.11 qui est la définition de XOR).

Cependant, en C, ils peuvent générer un négatif zéro . Dans le complément 2 Il n'y a pas de zéro négatif. Mais supposons que vous étiez sur un système avec le complément 1 alors vous pourriez générer un zéro négatif via ^ et cela pourrait causer une représentation piège. 6.2.6.2 / 3 dit explicitement que c'est possible:

si l'implémentation supporte des zéros négatifs, ils ne seront générés que par:

- le &, |, ^, ~, <<, et >> les opérateurs, avec des opérandes qui produisent une valeur;

enfin 6.2.6.2 / 2 implique (je suis assez sûr de toute façon) qu'il n'est pas possible d'avoir n'importe quelle combinaison de bits de valeur qui représenterait un entier dépassant INT_MAX

pour résumer, les résultats possibles de ^ sur deux int s sont:

• Une autre valeur valide int (peut-être avec des embouts de rembourrage différents mais ne piégeant pas les autres versions de la même valeur)
• Un négatif, zéro, ce qui peut ou peut ne pas causer un piège

Strictement parlant, vous ne pouvez pas XOR de deux entiers . Vous pouvez XOR deux sacs entiers de bits, et vous pouvez traiter ces sacs de bits comme des entiers à d'autres moments. Vous pouvez même les traiter comme des entiers à tous d'autres fois.

mais au moment où vous effectuez L'opération XOR, vous les traitez comme quelque chose de tout à fait différent des entiers, ou même des nombres, per se : ce ne sont que deux séquences de bits, où les bits correspondants sont comparés. Le concept de débordement ne s'applique pas à cela, et donc si vous décidez alors de traiter le résultat comme un entier, il ne peut pas déborder non plus.

est-il même possible que XOR génère une si grande valeur entière qui ne peut pas être stockée dans le type int?

si les opérandes sont int , alors no.

Si il n'est pas possible que cela peut arriver, alors est-il une preuve?

Eh bien, c'est trivial de la définition. Ce n'est pas une preuve mathématiquement rigoureuse, mais vous pourriez considérer que un bit dans la sortie de XOR ne sera que 1 si l'un des opérandes a 1 dans cette position. Comme un bit hors de portée ne peut pas être 1 dans les opérandes, il n'y a pas de bit de sortie avec la valeur 1 qui est hors de portée.

Non il ne peut pas. Contrairement à d'autres, mes réponses seraient une preuve mathématique.

XOR est un raccourci pour exclusif ou ou disjonction exclusive ( ⊕ ) et peut être défini comme:

A ⊕ B = (A ∪ B)\(A ∩ B)

votre thèse est que

∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)

donc de la première équation

x ∈ (A ∪ B)\(A ∩ B)

ce qui peut être exprimé en

x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)

la deuxième partie peut être exprimée comme suit:

x ∉ A ∧ x ∉ B

la première partie peut être exprimée comme suit:

x ∈ A ∨ x ∈ B

ce qui entre en conflit avec notre hypothèse que x ∉ A ∧ x ∉ B so thèse est fausse pour tout ensemble A et B .

Q. E. D.

XOR, ET, OU, NON et tous les autres opérateurs au niveau du bit produire bit à bit des résultats, avec les bits du résultat combiné de l'bits exactement à la même position dans les entrées. Donc les entrées N-bit produisent n-bit sans un bit plus élevé, alors comment peut-il aller hors limites?

Dans un CAS GÉNÉRAL l'algorithme décrit, ne peut vraiment pas trouver un solitaire entier dans un tableau. Ce qu'il trouve vraiment est XOR de tous les éléments qui se produisent nombre impair fois.

donc, s'il n'y a qu'un seul élément" Solitaire", dites un élément 'a' , et que tous les autres éléments se produisent même en nombre de fois dans le tableau, alors il fonctionne "selon les besoins" - > il trouve cet élément Solitaire 'a' .

pourquoi?

l'algorithme effectue XOR de tous les éléments dans le tableau (a ^ b ^ c ^ d ^ ...)

l'opération XOR possède les propriétés suivantes:

1) a ^ a = 0 (non-equivalence)

2) a ^ 0 = a (neutrality of 0)

3) a ^ b = b ^ a (commutative property)

4) (a ^ b) ^ c = a ^ (b ^ c) (associative property)

supposons, par exemple, un tableau avec des éléments: {a, b, c, a, c, b, a, c}

(élément 'a' - 3 fois, élément 'b' - 2 fois, élément 'c' - 3 fois)

puis, selon les propriétés mentionnées ci-dessus XOR , le résultat de l'algorithme

R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)

peut être modifié comme suit:

R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =

= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =

= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)

c'est à dire,

a)... tous les éléments qui se produisent un nombre pair fois le résultat zéro

b)... tous les éléments qui se produisent un nombre impair fois sont XOR-ed et de créer le résultat final

XOR est un bit à bit opération, de sorte qu'il ne peut jamais déborder, bien sûr.

Supposons que

int xor  = x^y;
Max value of int is x = 999999999;
Max value of Xor will come if y=0;
and Max Xor is 999999999;

qui est en limite. :)

est-il même possible que XOR génère une si grande valeur entière qui ne peut pas être stocké dans le type int?

Data-Type3 = Data-Type1 operator Data-Type2

S'il n'est pas possible que cela puisse se produire, alors y a-t-il une preuve pour cette?

nous avons Data-Type3 en cas d'entiers est celui sur Data-Type1 et Data-Type2 qui a une plus grande taille, même en cas d'addition ou de multiplication.

SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2))

donc si Data-Type1 = Data-Type2 alors c'est le type de retour aussi.

Short + Short   = Short
Short + Integer = Integer
Short + Long    = Long

Integer + Short   = Integer
Integer + Integer = Integer
Integer + Long    = Long

Long + Short   = Long
Long + Integer = Long
Long + Long    = Long

ce qui peut arriver est un débordement, qui peut se produire quand une opération a un carry. Dans le complément 2, c'est quand le carry dans la colonne de haut ordre n'est pas égal au carry dans la colonne de haut ordre. lire la suite

Mais opération XOR ne peut pas déborder , parce que l'opération XOR ne génère pas un carry, depuis XOR est une opération bit-wise comme pas.