Bitwise XOR of rational numbers

Question

Introduction

Every rational number between 0 and 1 can be represented as an eventually periodic sequence of bits. For example, the binary representation of 11/40 is

0.010 0011 0011 0011 ...

where the 0011 part repeats indefinitely. One way of finding this representation is the following. Start with r = 11/40, then repeatedly double it and take the fractional part, recording when it goes above 1. When the value of r repeats, you know you have entered a loop.

1. r = 11/40
2. 2*r = 11/20 < 1   ->  next bit is 0, r = 11/20
3. 2*r = 11/10 >= 1  ->  next bit is 1, r = 2*r - 1 = 1/10
4. 2*r = 1/5 < 1     ->  next bit is 0, r = 1/5
5. 2*r = 2/5 < 1     ->  next bit is 0, r = 2/5
6. 2*r = 4/5 < 1     ->  next bit is 0, r = 4/5
7. 2*r = 8/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 3/5
8. 2*r = 6/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 1/5, same as in 4.
   The loop 5. -> 6. -> 7. -> 8. now repeats.

To get from the binary string back to 11/40, you can use the formula

(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)

where prefix is the initial part 010, suffix is the repeating part 0011, and int converts a binary string to integer.

Given two such representations, we can perform the bitwise XOR operation on them. The resulting sequence will also be periodic, so it represents a rational number.

For some rational numbers, there are two binary representations.

1/4 = 0.010000000...
    = 0.001111111...

The choice between them can affect the result of the bitwise XOR. In these cases, we use the former representation, which has infinitely many 0s.

The task

Your inputs are two rational numbers in the half-open interval [0,1). Your output shall be the result of the bitwise XOR operation applied to the inputs, expressed as a rational number. Note that the output can be 1, even though neither of the inputs are.

The exact formats of input and output are flexible, but each rational number should be represented by two integers, the numerator and denominator (with the exception of 0 and 1, which can be represented as 0 and 1 if desired). You can assume that the inputs are expressed in lowest terms. The output must be expressed in lowest terms. A built-in rational number type is an acceptable format, as long as it satisfies these restrictions. You can ignore any bounds on integers imposed by your language, but your algorithm should theoretically work for all rational numbers.

The lowest byte count wins. Standard code-golf rules apply.

Example

Consider the inputs 11/40 and 3/7. We write their representations one above the other, delimiting the repeating parts by pipes |. Then we extract repeating parts of equal lengths, and apply bitwise XOR to them and the parts before them.

11/40 = 0. 0 1 0|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 ...
3/7   = 0.|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|...
     -> 0. 0 0 1|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 ...

The resulting rational number is 89/520.

Test cases

0 0 -> 0
1/2 1/2 -> 0
1/2 1/4 -> 3/4
1/3 2/3 -> 1
1/2 3/4 -> 1/4
5/8 1/3 -> 23/24
1/3 1/5 -> 2/5
15/16 3/19 -> 257/304
15/16 257/304 -> 3/19
3/7 11/40 -> 89/520
5/32 17/24 -> 59/96
16/29 16/39 -> 621001733121535520/696556744961512799

Answer 1

Python 3, 193 164 bytes

def x(a,b,z=0):
 l=[]
 while(a,b)not in l:l+=[(a,b)];z=2*z|(a<.5)^(b<.5);a=a*2%1;b=b*2%1
 p=l.index((a,b));P=len(l)-p
 return((z>>P)+z%2**P*a**0/~-2**(P or 1))/2**p

Takes input as Python 3's fractions.Fraction type, and outputs it as well.

Fun fact (you can easily show this using generating functions), if you change (a<.5)^(b<.5) to ((a>=.5)and(b>=.5)) above you get the binary AND between two rational numbers. Call this nd(a, b). Then we have a + b - 2*nd(a, b) = x(a, b)!

Answer 2

JavaScript, 141 bytes

(p,q,r,s)=>(h=(v,u)=>v%u?h(u,v%u):[a/u,b/u])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))

Wont work for last test case (integer overflow). Input 4 numbers for p/q xor r/s, output an array with two numbers. For testcase 0, 0, you should input 0, 1, 0, 1.

How:

(All numbers described here is in binary form.)

1. find the smallest number b, which b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
2. Let x = p * b / q, y = r * b / q; Convert p / q, r / s to x / b and y / b;
3. Let o = 10 ^ (p - q) - 1; split x, y to [x % o, x / o], [y % o, y / o]; get xor for each part [x % o xor y % o, x / o xor y / o], and join back to (x % o xor y % o) + (x / o xor y / o) * o; Donate it as a;
4. If a = 0, the answer is 0 (or 0 / 1); Otherwise let u = gcd(a, b); the answer is (a/u) and (b/u).

f=

(p,q,r,s)=>(h=(v,u)=>u%v?h(u%v,v):[a/v,b/v])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))

<div oninput="[v5.value,v6.value]=['?','?'];[v5.value,v6.value]=f(+v1.value,+v2.value,+v3.value,+v4.value)">
<input id=v1 />/<input id=v2 /> xor <input id=v3 />/<input id=v4 /> = <output id=v5></output> / <output id=v6></output>
<style>input{width:40px}</style>
</div>