两个整数的 XOR 可以越界吗？
Can XOR of two integers go out of bounds?
我一直在研究在数组中查找孤立整数的算法，这里是实现：
int arr[] = {10, 20, 30, 5, 20, 10, 30};
int LonelyInteger = 0;
for(int i=0; i< 7; i++)
{
LonelyInteger = LonelyInteger ^ arr[i];
}
结果是5。
我的问题是 - 据推测整数（由 XOR 操作生成）由于此操作太大：
LonelyInteger ^ arr[i]
这会导致一个潜在的大整数，在这种情况下，数据类型不能表示 int。我的问题是：
- 难道
XOR会生成这么大的整数值，无法存储在int类型中吗？
- 如果这不可能发生，那么有证据吗？
XOR 永远不会越界，因为它组合位并且不会在之前未设置位的地方创建新位。
结果5正确。查看您的值的二进制表示和 XOR 结果
10 00001010
20 00010100
30 00011110
5 00000101
20 00010100
10 00001010
30 00011110
--------------
00000101 => 5
计算许多 XORed 值的结果的一个简单帮助是：结果将有一个位集，其中奇数位组合在一起，偶数位没有位集。
If it is not possible that this can happen then is there a proof for this?
XOR 等价于没有进位的加法。当您添加不带进位的位时，不会发生溢出，因此 int 值不会超出范围。
Is it even possible that XOR will generate such a large integer value that cannot be stored in the int type?
如果操作数是int，则否
If it is not possible that this can happen then is there a proof for this?
好吧，从定义上看这是微不足道的。这算不上严格的数学证明，但您可以认为，如果其中一个操作数的位置为 1，则 XOR 输出中的某个位仅为 1。由于操作数中超出范围的位不能为 1，因此不存在值为 1 的输出位超出范围。
（此 post 适用于 C，不适用于 C++）
由于设置了无效的填充位，按位运算符不能导致陷阱表示，参见 C11 6.2.6.2/1 脚注：
...no arithmetic operation on valid values can generate a trap
representation...
（“算术运算”的意思is unclear 但是索引链接到6.5.11 是异或的定义）
但是，在 C 中，它们会导致生成 负零。在 2 的补码中没有负零。但是假设你在一个有 1 补码的系统上，那么你可以通过 ^ 生成负零，这可能会导致陷阱表示。 6.2.6.2/3 明确表示这是可能的：
If the implementation supports negative zeros, they shall be generated only by:
— the &, |, ^, ~, <<, and >> operators with operands that produce such a value;
最后 6.2.6.2/2 暗示（无论如何我都很确定）不可能有任何值位组合来表示超过 INT_MAX
的整数
总而言之，^ 在两个 int 上的可能结果是：
- 另一个有效的
int 值（对于相同值的其他版本可能具有不同但非陷阱的填充位）
- 负零，可能会也可能不会导致陷阱
结果永远不会是 "too large"，因为它的表示需要比 int 提供的更多的位，因为该操作被定义为组合其操作数的位值，而不产生任何新位.也许一个更好的问题可能是，结果是否可以是 int?
的有效值表示以外的东西？
对于无符号整数，没有。所有位模式以及所有按位运算的结果都是有效的值表示。
对于有符号整数，它取决于实现定义的负值表示形式。您可能遇到的每个实现都使用 2 的补码，其中每个位模式都是有效的；同样，任何按位运算的结果都将是有效的表示形式。
但是，该标准还允许其他表示形式，其中可能存在一个或多个无效位模式。在这种情况下，具有两个有效操作数的按位运算可能会产生该模式，从而产生无效结果。
假设
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;
这是在限制中。 :)
XOR、AND、OR、NOT 和任何其他按位运算符产生 按位 结果，结果中的位由输入中完全相同位置的位组合而成。所以 n 位输入产生 n 位而没有任何更高位，那么它怎么会越界呢？
在一般情况中，所描述的算法无法真正找到数组中的孤立整数。
它真正找到的是在那里出现奇数次的所有元素的 XOR。
所以，如果那里只有一个 'lonely' 元素，比如说一个元素 'a'，并且所有其他元素在数组中出现偶数次，那么它就可以 'as required' -> 它找到了这个孤独的元素 'a'.
为什么？
算法对数组(a ^ b ^ c ^ d ^ ...)
中的所有元素进行XOR
XOR 操作具有以下属性：
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)
让我们假设，例如，一个包含元素的数组：{a, b, c, a, c, b, a, c}
(元素'a' - 3次，元素'b' - 两次，元素'c' - 3次)
然后，根据上面提到的XOR性质，算法结果
R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)
可以重新排列如下：
R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =
= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =
= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)
即
a) ...出现偶数次的所有元素结果为零
b) ...对所有出现奇数次的元素进行异或运算并创建最终结果
XOR 是一个 位 操作，所以它永远不会溢出，当然。
严格来说，您不能对两个整数进行异或运算。您可以对两个整数大小的位袋进行 XOR，并且您可以在其他时候将这些位袋视为整数。您甚至可以在 all 其他时间将它们视为整数。
但是在执行异或运算的那一刻，您将它们视为与整数或偶数完全不同的东西，本身：它们只是两个位序列，比较相应的位。溢出的概念不适用于此，因此如果您随后决定将结果视为整数，它也不会溢出。
不，不能。与其他人的答案不同，我的答案是数学证明。
XOR 是 exclusive or or exclusive disjunction (⊕) 的快捷方式，可以定义为:
A ⊕ B = (A ∪ B)\(A ∩ B)
你的提议是
∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)
所以从第一个等式
x ∈ (A ∪ B)\(A ∩ B)
什么可以表示为
x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)
第二部分可以表示为：
x ∉ A ∧ x ∉ B
第一部分可以表示为：
x ∈ A ∨ x ∈ B
什么与我们的假设相冲突 x ∉ A ∧ x ∉ B 所以命题对于任何集合 A 和 B 都是错误的。
Q.E.D.
Is it even possible that XOR will generate such a large integer value
that cannot be stored in the int type?
Data-Type3 = Data-Type1 operator Data-Type2
If it is not possible that this can happen then is there a proof for
this?
我们 Data-Type3 如果整数是 Data-Type1 和 Data-Type2 中具有更大大小的整数，即使在加法或乘法的情况下也是如此。
SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2))
所以如果 Data-Type1 = Data-Type2 那么这也是 return 类型。
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
可能发生的是溢出，当操作有进位时可能发生。在 2 的补码中，高位列的进位不等于高位列的进位。 read more
但是XOR运算不能溢出，因为XOR运算不会产生进位，因为XOR是按位运算像NOT .
我一直在研究在数组中查找孤立整数的算法，这里是实现：
int arr[] = {10, 20, 30, 5, 20, 10, 30};
int LonelyInteger = 0;
for(int i=0; i< 7; i++)
{
LonelyInteger = LonelyInteger ^ arr[i];
}
结果是5。
我的问题是 - 据推测整数（由 XOR 操作生成）由于此操作太大：
LonelyInteger ^ arr[i]
这会导致一个潜在的大整数，在这种情况下，数据类型不能表示 int。我的问题是：
- 难道
XOR会生成这么大的整数值，无法存储在int类型中吗？ - 如果这不可能发生，那么有证据吗？
XOR 永远不会越界，因为它组合位并且不会在之前未设置位的地方创建新位。
结果5正确。查看您的值的二进制表示和 XOR 结果
10 00001010
20 00010100
30 00011110
5 00000101
20 00010100
10 00001010
30 00011110
--------------
00000101 => 5
计算许多 XORed 值的结果的一个简单帮助是：结果将有一个位集，其中奇数位组合在一起，偶数位没有位集。
If it is not possible that this can happen then is there a proof for this?
XOR 等价于没有进位的加法。当您添加不带进位的位时，不会发生溢出，因此 int 值不会超出范围。
Is it even possible that XOR will generate such a large integer value that cannot be stored in the int type?
如果操作数是int，则否
If it is not possible that this can happen then is there a proof for this?
好吧，从定义上看这是微不足道的。这算不上严格的数学证明，但您可以认为，如果其中一个操作数的位置为 1，则 XOR 输出中的某个位仅为 1。由于操作数中超出范围的位不能为 1，因此不存在值为 1 的输出位超出范围。
（此 post 适用于 C，不适用于 C++）
由于设置了无效的填充位，按位运算符不能导致陷阱表示，参见 C11 6.2.6.2/1 脚注：
...no arithmetic operation on valid values can generate a trap representation...
（“算术运算”的意思is unclear 但是索引链接到6.5.11 是异或的定义）
但是，在 C 中，它们会导致生成 负零。在 2 的补码中没有负零。但是假设你在一个有 1 补码的系统上，那么你可以通过 ^ 生成负零，这可能会导致陷阱表示。 6.2.6.2/3 明确表示这是可能的：
If the implementation supports negative zeros, they shall be generated only by:
— the &, |, ^, ~, <<, and >> operators with operands that produce such a value;
最后 6.2.6.2/2 暗示（无论如何我都很确定）不可能有任何值位组合来表示超过 INT_MAX
总而言之，^ 在两个 int 上的可能结果是：
- 另一个有效的
int值（对于相同值的其他版本可能具有不同但非陷阱的填充位） - 负零，可能会也可能不会导致陷阱
结果永远不会是 "too large"，因为它的表示需要比 int 提供的更多的位，因为该操作被定义为组合其操作数的位值，而不产生任何新位.也许一个更好的问题可能是，结果是否可以是 int?
对于无符号整数，没有。所有位模式以及所有按位运算的结果都是有效的值表示。
对于有符号整数，它取决于实现定义的负值表示形式。您可能遇到的每个实现都使用 2 的补码，其中每个位模式都是有效的；同样，任何按位运算的结果都将是有效的表示形式。
但是，该标准还允许其他表示形式，其中可能存在一个或多个无效位模式。在这种情况下，具有两个有效操作数的按位运算可能会产生该模式，从而产生无效结果。
假设
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;
这是在限制中。 :)
XOR、AND、OR、NOT 和任何其他按位运算符产生 按位 结果，结果中的位由输入中完全相同位置的位组合而成。所以 n 位输入产生 n 位而没有任何更高位，那么它怎么会越界呢？
在一般情况中，所描述的算法无法真正找到数组中的孤立整数。
它真正找到的是在那里出现奇数次的所有元素的 XOR。
所以，如果那里只有一个 'lonely' 元素，比如说一个元素 'a'，并且所有其他元素在数组中出现偶数次，那么它就可以 'as required' -> 它找到了这个孤独的元素 'a'.
为什么？
算法对数组(a ^ b ^ c ^ d ^ ...)
XOR
XOR 操作具有以下属性：
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)
让我们假设，例如，一个包含元素的数组：{a, b, c, a, c, b, a, c}
(元素'a' - 3次，元素'b' - 两次，元素'c' - 3次)
然后，根据上面提到的XOR性质，算法结果
R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)
可以重新排列如下：
R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =
= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =
= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)
即
a) ...出现偶数次的所有元素结果为零
b) ...对所有出现奇数次的元素进行异或运算并创建最终结果
XOR 是一个 位 操作，所以它永远不会溢出，当然。
严格来说，您不能对两个整数进行异或运算。您可以对两个整数大小的位袋进行 XOR，并且您可以在其他时候将这些位袋视为整数。您甚至可以在 all 其他时间将它们视为整数。
但是在执行异或运算的那一刻，您将它们视为与整数或偶数完全不同的东西，本身：它们只是两个位序列，比较相应的位。溢出的概念不适用于此，因此如果您随后决定将结果视为整数，它也不会溢出。
不，不能。与其他人的答案不同，我的答案是数学证明。
XOR 是 exclusive or or exclusive disjunction (⊕) 的快捷方式，可以定义为:
A ⊕ B = (A ∪ B)\(A ∩ B)
你的提议是
∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)
所以从第一个等式
x ∈ (A ∪ B)\(A ∩ B)
什么可以表示为
x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)
第二部分可以表示为：
x ∉ A ∧ x ∉ B
第一部分可以表示为：
x ∈ A ∨ x ∈ B
什么与我们的假设相冲突 x ∉ A ∧ x ∉ B 所以命题对于任何集合 A 和 B 都是错误的。
Q.E.D.
Is it even possible that XOR will generate such a large integer value that cannot be stored in the int type?
Data-Type3 = Data-Type1 operator Data-Type2
If it is not possible that this can happen then is there a proof for this?
我们 Data-Type3 如果整数是 Data-Type1 和 Data-Type2 中具有更大大小的整数，即使在加法或乘法的情况下也是如此。
SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2))
所以如果 Data-Type1 = Data-Type2 那么这也是 return 类型。
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
可能发生的是溢出，当操作有进位时可能发生。在 2 的补码中，高位列的进位不等于高位列的进位。 read more
但是XOR运算不能溢出，因为XOR运算不会产生进位，因为XOR是按位运算像NOT .