Can XOR of two integers go out of bounds?
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 0000101020 0001010030 00011110 5 0000010120 0001010010 0000101030 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.
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.
(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 traprepresentation...
(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 int
s 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