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 result is 5
.
My question is - supposedly the integers (getting generated by the XOR
operation) are too large due to this operation:
LonelyInteger ^ arr[i]
Which leads to a potentially large integer which cannot be represented by the datatype say int
in this case. My questions are:
XOR
will generate such a large integer value that cannot be stored in the int
type?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 XOR
ed 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.