Exp*_*ice 52 c c++ bit-manipulation integer-overflow bitwise-xor
我一直在研究在数组中查找孤独整数的算法,这里是实现:
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类型中的如此大的整数值？sch*_*der 120
XOR 永远不会超出界限,因为它结合了位并且不创建之前没有设置位的新位.
结果5是正确的.查看您的值和XOR结果的二进制表示
10 00001010
20 00010100
30 00011110
5 00000101
20 00010100
10 00001010
30 00011110
--------------
00000101 => 5
计算许多XORed值的结果的一个简单帮助是:结果将有一个位设置,其中奇数位组合,没有位设置偶数位.
如果不可能发生这种情况,那么有证据吗？
XOR相当于不加个别位的加法.在没有进位的情况下添加位时,不会发生溢出,因此该int值不会超出范围.
Mik*_*our 37
int由于操作被定义为组合其操作数的位值而不产生任何新位,因此在其表示需要比提供的位更多的位的意义上,结果永远不会"太大" .也许一个更好的问题可能是,结果是否可以是除了有效值表示之外的其他东西int？
对于无符号整数,没有.所有位模式以及因此所有按位操作的结果都是有效的值表示.
对于有符号整数,它取决于实现定义的负值表示.您可能遇到的每个实现都使用2的补码,其中每个位模式都是有效的; 所以,任何按位运算的结果都是有效的表示.
但是,该标准还允许其他表示,其中可能存在一个或多个无效位模式.在这种情况下,有两个有效操作数的按位运算可能产生该模式,从而产生无效结果.
M.M*_*M.M 26
(这篇文章适用于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
总而言之,^两个方面int的可能结果是:
int(可能具有不同但非陷阱的填充位到相同值的其他版本)The*_*est 20
严格来说,你不能XOR两个整数.你可以对两个整数大小的包进行异或,你可以在其他时间将这些包作为整数处理.您甚至可以在其他所有时间将它们视为整数.
但是当你执行XOR操作时,你将它们视为与整数甚至数字完全不同的东西本身:它们只是两个位序列,其中相应的位被比较.溢出的概念不适用于此,因此如果您决定将结果视为整数,则它也不会溢出.
eer*_*ika 11
是否有可能XOR会生成一个无法存储在int类型中的大整数值？
如果操作数是int,那么没有.
如果不可能发生这种情况,那么有证据吗？
嗯,从定义来看,它是微不足道的.这几乎不是数学上严格的证明,但你可以认为,如果其中一个操作数在该位置有1,那么XOR输出中的一点只会是1.由于操作数中超出范围的位不能为1,因此没有值为1的输出位超出范围.
phu*_*clv 10
XOR,AND,OR,NOT和任何其他按位运算符产生按位结果,结果中的位由输入中完全相同位置的位组合而成.所以n位输入产生n位而没有任何更高的位,那么它怎么能脱离界限呢？
Hau*_*eth 10
不,它不能.不像其他人的答案,我的数学证明.
XOR是快捷方式异或或异或(?),并且可以被定义为:
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.
QED
在一般情况下,所描述的算法实际上不能在数组中找到孤立的整数.它真正发现的是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)
即
a)... 所有出现偶数次的元素都会导致零
b)... 所有出现ODD次数的元素都被异或,并创建最终结果
XOR当然,它是一个按位操作,所以它永远不会溢出.