55

我一直在研究在数组中查找孤独整数的算法，这里是实现：

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这会导致一个潜在的大整数，在这种情况下不能用数据类型表示。我的问题是：

  1. 是否有可能XOR会生成如此大的整数值而无法存储在int类型中？
  2. 如果这不可能发生，那么是否有证据证明这一点？
4

10 回答 10

121

XOR永远不会越界，因为它结合了位并且不会在之前没有设置位的地方创建新位。

结果5是正确的。查看您的值的二进制表示形式和XOR结果

10    00001010
20    00010100
30    00011110
 5    00000101
20    00010100
10    00001010
30    00011110
--------------
      00000101 => 5

计算许多XORed 值的结果的一个简单帮助是：结果将设置一个位，其中奇数位组合，偶数位不设置位。

如果这不可能发生，那么是否有证据证明这一点？

XOR相当于不进行单个位的加法。当您添加不带进位的位时，不会发生溢出，因此int值不会超出范围。

于 2015-02-04T11:44:32.587 回答
38

结果永远不会“太大”，因为它的表示需要比int提供的更多位，因为操作被定义为组合其操作数的位值，而不产生任何新位。也许一个更好的问题可能是，结果是否可以不是 a 的有效值表示int？

对于无符号整数，没有。所有位模式，以及所有按位运算的结果，都是有效的值表示。

对于有符号整数，它取决于实现定义的负值表示。您可能遇到的每个实现都使用 2 的补码，其中每个位模式都是有效的；同样，任何按位运算的结果都是有效的表示。

但是，该标准还允许其他表示，其中可能存在一个或多个无效位模式。在这种情况下，具有两个有效操作数的按位运算可能会产生该模式，从而产生无效的结果。

于 2015-02-04T12:03:49.490 回答
28

（这篇文章适用于 C，而不是 C++）

由于设置了无效的填充位，按位运算符不会导致陷阱表示，请参阅 C11 6.2.6.2/1 脚注：

...没有对有效值的算术运算可以生成陷阱表示...

（“算术运算”的含义不清楚，但索引链接到 6.5.11，这是 XOR 的定义）。

但是，在 C 中，它们会导致生成负零。在 2 的补码中没有负零。但是假设您在一个带有 1 补码的系统上，那么您可以通过生成负零^，这可能会导致陷阱表示。6.2.6.2/3 明确表示这是可能的：

如果实现支持负零，它们只能通过以下方式生成：

— &、|、^、~、<< 和 >> 运算符，其操作数产生这样的值；

最后 6.2.6.2/2 暗示（我很确定）不可能有任何值位组合来表示一个整数超过INT_MAX

总结一下，^on two ints 的可能结果是：

  • 另一个有效值int（可能与相同值的其他版本具有不同但非捕获的填充位）
  • 负零，可能会也可能不会导致陷阱
于 2015-02-04T11:55:57.383 回答
21

严格来说，你不能 XOR two integers。您可以对两个整数大小的位包进行异或运算，并且您可以在其他时间将这些位包视为整数。您甚至可以在所有其他时间将它们视为整数。

但是在您执行 XOR 操作的那一刻，您将它们视为与整数或偶数本身完全不同的东西：它们只是两个位序列，对应的位在其中进行比较。溢出的概念不适用于此，因此如果您决定将结果视为整数，它也不会溢出。

于 2015-02-05T01:38:43.897 回答
11

有没有可能异或会产生这么大的整数值，无法存储在 int 类型中？

如果操作数是int，那么不是。

如果这不可能发生，那么是否有证据证明这一点？

嗯，从定义上看是微不足道的。这几乎不是数学上严格的证明，但您可以认为，如果其中一个操作数在该位置为 1，则 XOR 的输出中的位将仅为 1。由于操作数中的超出范围位不能为 1，因此没有值为 1 的输出位超出范围。

于 2015-02-04T11:47:18.233 回答
11

XOR、AND、OR、NOT 和任何其他按位运算符产生按位结果，结果中的位由输入中完全相同位置的位组合而成。所以 n 位输入产生 n 位而没有任何更高位，那么它怎么会越界呢？

于 2015-02-04T12:57:03.487 回答
10
于 2015-02-05T20:34:14.010 回答
7

在一般情况下，所描述的算法实际上无法在数组中找到孤独的整数。它真正找到的是XOR在那里出现奇数次的所有元素。

因此，如果那里只有一个“孤独”元素，比如一个元素'a'，并且所有其他元素在数组中出现偶数次，那么它会“按要求”工作 -> 它会找到这个孤独的元素'a'。

为什么？

该算法执行XOR数组中的所有元素(a ^ b ^ c ^ d ^ ...)

该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)

IE，

a) ...所有出现偶数次的元素都为零

b) ...所有出现奇数次的元素都经过异或运算并创建最终结果

XOR是按位操作，所以它当然永远不会溢出。

于 2015-02-04T17:57:58.090 回答
3

认为

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;

这是有限的。:)

于 2015-02-04T12:05:38.060 回答
2

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?

We've Data-Type3 in case of Integers is the one out of Data-Type1 and Data-Type2 that has a bigger size, even in case of addition or multiplication.

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

So if Data-Type1 = Data-Type2 then that's the return-type too.

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

What can happen is an overflow, which can occur when an operation have a carry. In 2's complement, it's when the carry into the high order column doesn't equal the carry out of the high order column. read more

But XOR operation cannot overflow, because XOR operation does not generate a carry, since XOR is a bit-wise operation like NOT.

于 2015-02-11T08:08:28.040 回答