XOR properties in set of numbers
By John Thompson
Say I have n positive numbers A1,A2...An and Ak is minimum among them. And d is a number such that (A1-d) ⊕ (A2-d) ⊕ .......(An-1-d) ⊕ (An-d) = 0 where0<=d <= Ak.
I want to know how many d are there . I know I can iterate all possible value of d and take XOR of n number every time and find out but complexity in this case is O(Ak∗n) which is O(n2) in worst case.
Is their any property of XOR which can help us to find number of d in less complexity than this ?
Edit :
Eq: If n=4 and numbers are = 4 6 8 10 then d can be {0,3}as 4 ⊕ 6 ⊕ 8 ⊕ 10 =0and 1 ⊕ 3 ⊕ 5 ⊕ 7 =0
1 Answer
$\begingroup$You can figure out the possible values of d one bit at a time. Consider the equation mod 2:
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 2Try 0 and 1 for d, see if either works. Say d==1 is the only assignment that works. Then try the values 1 and 3 in the equation:
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 4and so on, taking all valid ds mod 2^i and trying both d and d+2^i mod 2^{i+1}. The reason why this works is that both subtraction and xor do not propagate any information from higher bits to lower bits, so if you find a solution to the mod 2 equation, it remains a solution no matter what the higher-order bits of d are set to.
The running time should be something like O(n * log Ak * #of solutions).
Example:
A = {9,12,23,30}
try d=0,1 mod 2. Both work.
try d=0,1,2,3 mod 4. All work.
try d=[0-7] mod 8. 1,3,5,7 work.
try d=[1,9,3,5,7] mod 16. 3,7 work. (no need to check if d>Ak)
now we've tried up to Ak, check the remaining solutions for the remaining
high-order bits. 3 and 7 work.Example:
A = {4,6,8,10}
try d=0,1 mod 2. Both work.
try d=0,1,2,3 mod 4. All work.
try d=0,4,1,2,3 mod 8. All work.
at this point you've tried all d up to Ak. Do a final check and 0,3,4 work.
