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

No it cannot. Unlike others answers mine would be mathematical proof.

XOR is shortcut for exclusive or or exclusive disjunction (⊕) and can be defined as:

A ⊕ B = (A ∪ B)\(A ∩ B)

Your thesis is that

∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)

So from first equation

x ∈ (A ∪ B)\(A ∩ B)

What can be expressed as

x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)

The second part can be expressed as:

x ∉ A ∧ x ∉ B

The first part can be expressed as:

x ∈ A ∨ x ∈ B

What collide with our assumption that x ∉ A ∧ x ∉ B so thesis is false for any set A and B.

Q.E.D.

Answer 2

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

Data-Type3 = Data-Type1 operator Data-Type2

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

We've Data-Type3 in case of Integers is the one out of Data-Type1 and Data-Type2 that has a bigger size, even in case of addition or multiplication.

SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2))

So if Data-Type1 = Data-Type2 then that's the return-type too.

Short + Short   = Short
Short + Integer = Integer
Short + Long    = Long

Integer + Short   = Integer
Integer + Integer = Integer
Integer + Long    = Long

Long + Short   = Long
Long + Integer = Long
Long + Long    = Long

What can happen is an overflow, which can occur when an operation have a carry. In 2's complement, it's when the carry into the high order column doesn't equal the carry out of the high order column. read more

But XOR operation cannot overflow, because XOR operation does not generate a carry, since XOR is a bit-wise operation like NOT.

Answer 3

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.

Answer 4

In a GENERAL CASE the described algorithm cannot really find a lonely integer in an array. What it really finds is XOR of all elements that occur odd number times there.

So, if there is just one 'lonely' element there, say an element 'a', and all the other elements occur EVEN number times in the array, then it works 'as required' -> it finds this lonely element 'a'.

Why?

The algorithm carries out XOR of all the elements in the array (a ^ b ^ c ^ d ^ ...)

The XOR operation has the following properties:

1) a ^ a = 0 (non-equivalence)

2) a ^ 0 = a (neutrality of 0)

3) a ^ b = b ^ a (commutative property)

4) (a ^ b) ^ c = a ^ (b ^ c) (associative property)

Let's assume, for instance, an array with elements: {a, b, c, a, c, b, a, c}

(element 'a' - 3 times, element 'b' - twice, element 'c' - 3 times)

Then, according to the above mentioned XOR properties, the algorithm result

R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)

can be rearranged as follows:

R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =

= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =

= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)

i.e.,

a) ...all elements that occur an EVEN number times result in zero

b) ...all elements that occur an ODD number times are XOR-ed and create the final result

XOR is a bit-wise operation, so it never can overflow, of course.