可两个整数异或出界？ [英] 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;我7;;我++）
{
    LonelyInteger = LonelyInteger ^改编[I]
}
 

该eesult是 5 。

我的问题是 - 所谓的整数（由 XOR 操作如何产生的）是太大由于此操作：

  

LonelyInteger ^改编[I]

也就是说，这导致一个潜在的大整数，不能再由数据类型psented $ P $说 INT 在这种情况下。我的问题是：

1. 它甚至有可能是 XOR 会产生这样的不能存储在 INT 键入一个较大的整数值？
2. 如果这是不可能的，这可能会发生那么有没有证明这一点？

解决方案

XOR 将永远不会出界，因为它结合了位，并没有创造新的位，其中没有位之前被设置。

结果 5 是正确的。看看你的价值和 XOR 结果

的二进制再presentation

  10 00001010
20 00010100
30 00011110
 5 00000101
20 00010100
10 00001010
30 00011110
--------------
      00000101 =＆GT;五
 

这是简单的帮助下，计算多 XOR ED值的结果是：结果将有一个位置位，其中位为奇数的组合，无位设置偶数位的。

  

如果这是不可能的，这可能会发生那么有没有证明这一点？

XOR 相当于又多不进行各个位。当你没有进加位，无溢出可能发生，因此 INT 价值不能出界。

I had been studying the algorithm for finding lonely integers in an array, and here is the implementation:

int arr[] = {10, 20, 30 ,5, 20, 10,30 };
int LonelyInteger = 0;
for(int i=0; i< 7; i++)
{
    LonelyInteger = LonelyInteger ^ arr[i];
}

The eesult is 5.

My question is - supposedly the integers (getting generated by the XOR operation) are too large due to this operation:

LonelyInteger ^ arr[i]

That is, this leads to a potentially large integer which cannot be represented by the datatype say int in this case. My questions are:

1. Is it even possible that XOR will generate such a large integer value that cannot be stored in the int type?
2. If it is not possible that this can happen then is there a proof for this?

解决方案

XOR will never go out of bounds because it combines bits and doesn't create new bits where no bits were set before.

The result 5 is correct. Look at the binary representation of your value and the XOR result

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

An easy help for calculating a result of many XORed values is: The result will have a bit set where an odd number of bits are combined, no bit set for even number of bits.

If it is not possible that this can happen then is there a proof for this?

XOR is equivalent to addition without carry on the individual bits. When you add bits without carry, no overflow can happen and so the int value can't go out of bounds.

这篇关于可两个整数异或出界？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！