Can XOR of two integers go out of bounds?

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:

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

Solution 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.

Solution 2:

The result can never be "too large" in the sense of its representation requiring more bits than int provides, since the operation is defined to combine bit values of its operands, not produce any new bits. Perhaps a better question might be, can the result be something other than a valid value representation of an int?

For unsigned integers, no. All bit patterns, and hence the result of all bitwise operations, are valid value representations.

For signed integers, it depends on the implementation-defined representation of negative values. Every implementation you're likely to encounter uses 2's-complement, in which again every bit pattern is valid; so again, the result of any bitwise operation will be a valid representation.

However, the standard also allows other representations, in which there may be one or more invalid bit patterns. In that case, it's possible for a bitwise operation, with two valid operands, to produce that pattern, and hence produce an invalid result.

Solution 3:

(This post applies to C, not C++)

The bitwise operators cannot cause a trap representation due to setting invalid padding bits, see C11 6.2.6.2/1 footnote:

...no arithmetic operation on valid values can generate a trap representation...

(The meaning of "arithmetic operation" is unclear but the index links to 6.5.11 which is the definition of XOR).

However, in C they can cause a negative zero to be generated. In 2's complement there is no negative zero. But say you were on a system with 1's complement then you could generate negative zero via ^ and this might cause a trap representation. 6.2.6.2/3 explicitly says that this is possible:

If the implementation supports negative zeros, they shall be generated only by:

— the &, |, ^, ~, <<, and >> operators with operands that produce such a value;

Finally 6.2.6.2/2 implies (I'm pretty sure anyway) that it's not possible to have any combination of value bits that would represent an integer exceeding INT_MAX

To summarise, the possible results of ^ on two ints are:

Another valid int value (perhaps with different but non-trapping padding bits to other versions of the same value)
A negative zero, which may or may not cause a trap

Solution 4:

Strictly speaking, you can't XOR two integers. You can XOR two integer-sized bags of bits, and you can treat those bags of bits as integers at other times. You can even treat them as integers at all other times.

But at the moment you perform the XOR operation, you're treating them as something quite different from integers, or even numbers, per se: they're just two sequences of bits, where corresponding bits get compared. The concept of overflow doesn't apply to that, and so if you then decide to treat the result as an integer, it cannot overflow either.

Solution 5:

Is it even possible that XOR will generate such a large integer value that cannot be stored in the int type?

If the operands are int, then no.