Can XOR of two integers go out of bounds?

Question

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:

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?

Answer 1

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.