Bitweises XOR von rationalen Zahlen

19

Einführung

Jede rationale Zahl zwischen 0 und 1 kann als eine eventuell periodische Folge von Bits dargestellt werden. Zum Beispiel ist die binäre Darstellung von 11/40

0.010 0011 0011 0011 ...

wo der 0011Teil auf unbestimmte Zeit wiederholt. Eine Möglichkeit, diese Darstellung zu finden, ist die folgende. Beginnen Sie mit r = 11/40 , verdoppeln Sie es dann wiederholt und nehmen Sie den Bruchteil auf, wobei Sie aufzeichnen, wenn er über 1 liegt. Wenn sich der Wert von r wiederholt, wissen Sie, dass Sie in eine Schleife eingetreten sind.

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.

Um von der Binärzeichenfolge zurück zu 11/40 zu gelangen, können Sie die Formel verwenden

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

wo prefixist der Anfangsteil 010, suffixder sich wiederholenden Teil 0011, und intwandelt eine binäre Zeichenfolge ganze Zahl ist .

Wenn zwei solche Darstellungen gegeben sind, können wir die bitweise XOR-Operation für sie ausführen. Die resultierende Sequenz wird ebenfalls periodisch sein, sodass sie eine rationale Zahl darstellt.

Für einige rationale Zahlen gibt es zwei binäre Darstellungen.

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

Die Wahl zwischen ihnen kann das Ergebnis des bitweisen XOR beeinflussen. In diesen Fällen verwenden wir die frühere Darstellung, die unendlich viele Nullen hat.

Die Aufgabe

Ihre Eingaben sind zwei rationale Zahlen im halboffenen Intervall [0,1). Ihre Ausgabe soll das Ergebnis der bitweisen XOR-Operation sein, die auf die Eingaben angewendet wird, ausgedrückt als rationale Zahl. Beachten Sie, dass der Ausgang 1 sein kann, obwohl keiner der Eingänge 1 ist.

Die genauen Formate von Eingangs- und Ausgangs sind flexibel, aber jede rationale Zahl sollte von zwei ganzen Zahlen, Zähler und Nenner dargestellt werden (mit Ausnahme von 0 und 1, die als dargestellt werden kann , 0und , 1wenn gewünscht). Sie können davon ausgehen, dass die Eingaben in niedrigsten Ausdrücken ausgedrückt werden. Die Ausgabe muss in niedrigsten Ausdrücken ausgedrückt werden. Ein eingebauter Typ mit rationalen Zahlen ist ein akzeptables Format, sofern diese Einschränkungen erfüllt sind. Sie können alle durch Ihre Sprache auferlegten Grenzen für Ganzzahlen ignorieren, aber Ihr Algorithmus sollte theoretisch für alle rationalen Zahlen funktionieren.

Die niedrigste Byteanzahl gewinnt. Es gelten die Standardregeln für .

Beispiel

Betrachten Sie die Eingänge 11/40 und 3/7. Wir schreiben ihre Darstellungen übereinander und begrenzen die sich wiederholenden Teile durch Pfeifen |. Dann extrahieren wir sich wiederholende Teile gleicher Länge und wenden bitweise XOR auf sie und die Teile vor ihnen an.

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 ...

Die resultierende rationale Zahl ist 89/520.

Testfälle

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
Zgarb
quelle
Was ist der maximale Zeitraum, den wir unterstützen müssen?
Neil
@Neil Woran denkst du, dass es so ein Maximum gibt?
Orlp
3
Hinweis: Einige Zahlen haben zwei binäre Erweiterungen, nämlich die Zahlen, bei denen der spätere Zeitraum die Länge eins hat. In der obigen Problemdefinition ist implizit enthalten, dass wir die Darstellung auswählen müssen, die000...in diesen Fällenendet(was wir auch erhalten, wenn wir den Algorithmus mit verwendenr). Zum Beispiel in dem Fall5/8, 1/3,23/24dass wir die Erweiterung0.101000...fürwählen5/8. Wenn wir stattdessen0.10011111...aswählen5/8, wird das Ergebnis nach XOR19/24, das ist also falsch. In Verbindung mit Wikipedia: 0.999 ...
Jeppe Stig Nielsen
3
@JeppeStigNielsen Verdammt ... Das bedeutet, dass im Gegensatz zu regulären XOR (a ^ b) ^ b == anicht gilt. Eg (19/24 ^ 1/3) ^ 1/3 != 19/24.
Dadurch
1
Siehe auch Wie sehen bitweise Operatoren in 3D aus? auf Mathematik .
Ilmari Karonen

Antworten:

3

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

Nimmt Eingaben als Python 3- fractions.FractionTyp und gibt sie ebenfalls aus.

Unterhaltsame Tatsache (Sie können dies leicht mit Hilfe von Generierungsfunktionen zeigen): Wenn Sie (a<.5)^(b<.5)nach ((a>=.5)and(b>=.5))oben wechseln , erhalten Sie das binäre UND zwischen zwei rationalen Zahlen. Nennen Sie das nd(a, b). Dann haben wir a + b - 2*nd(a, b) = x(a, b)!

orlp
quelle
In der Tat mein Fehler. Entschuldigung! (Beachten Sie, dass ein Link zu tio in der Antwort großartig wäre)
Mr. Xcoder
1

JavaScript, 141 Byte

(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))

Funktioniert nicht für den letzten Testfall (ganzzahliger Überlauf). Geben Sie 4 Zahlen für ein p/q xor r/s, geben Sie ein Array mit zwei Zahlen aus. Für den Testfall 0, 0sollten Sie eingeben 0, 1, 0, 1.

Wie:

(Alle hier beschriebenen Zahlen sind in binärer Form.)

  1. finde die kleinste Zahl b, die b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
  2. Lassen Sie x = p * b / q, y = r * b / q; Konvertieren p / q, r / szu x / bund y / b;
  3. Lassen o = 10 ^ (p - q) - 1; Split x, yzu [x % o, x / o], [y % o, y / o]; Holen Sie sich xor für jeden Teil [x % o xor y % o, x / o xor y / o]und verbinden Sie sich wieder mit (x % o xor y % o) + (x / o xor y / o) * o; Spende es als a;
  4. Wenn a = 0, lautet die Antwort 0(oder 0 / 1); Sonst lass u = gcd(a, b); Die Antwort ist (a/u)und (b/u).

tsh
quelle