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

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.

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

Well, it's trivial from the definition. This is hardly a mathematically rigorous proof, but you could consider that a bit in the output of XOR will only be 1 if one of the operands has 1 in that position. Since an out of range bit cannot be 1 in the operands, there is not output bit with value 1 that is out of range.

Answer 2

XOR, AND, OR, NOT and any other bitwise operators produce bitwise results, with the bits in the result combined from the bits at exactly the same position in the inputs. So n-bit inputs produce n-bit without any higher bit, so how can it goes off bounds?

Answer 3

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.

Answer 4

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.

Answer 5

Suppose

int xor  = x^y;
Max value of int is x = 999999999;
Max value of Xor will come if y=0;
and Max Xor is 999999999;

which is in limit. :)

Answer 6

(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