Bitor XOR dari bilangan rasional

19

pengantar

Setiap bilangan rasional antara 0 dan 1 dapat direpresentasikan sebagai urutan bit yang akhirnya periodik. Sebagai contoh, representasi biner 11/40 adalah

0.010 0011 0011 0011 ...

di mana 0011bagian berulang tanpa batas. Salah satu cara untuk menemukan representasi ini adalah sebagai berikut. Mulailah dengan r = 11/40 , lalu berulang kali gandakan dan ambil bagian fraksional, catat ketika berada di atas 1. Ketika nilai r berulang, Anda tahu Anda telah memasukkan satu lingkaran.

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.

Untuk mendapatkan dari string biner kembali ke 11/40, Anda bisa menggunakan rumus

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

di mana prefixbagian awal 010, suffixadalah bagian berulang 0011, dan intmengubah string biner ke integer.

Diberikan dua representasi seperti itu, kita dapat melakukan operasi XOR bitwise pada mereka. Urutan yang dihasilkan juga akan berkala, sehingga mewakili bilangan rasional.

Untuk beberapa bilangan rasional, ada dua representasi biner.

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

Pilihan di antara mereka dapat mempengaruhi hasil XOR bitwise. Dalam kasus ini, kami menggunakan representasi sebelumnya, yang memiliki 0s tak terhingga banyaknya.

Tugas

Input Anda adalah dua angka rasional dalam interval setengah terbuka [0,1). Output Anda akan menjadi hasil operasi XOR bitwise yang diterapkan pada input, dinyatakan sebagai angka rasional. Perhatikan bahwa outputnya bisa 1, meskipun tidak ada inputnya.

Format input dan output yang tepat fleksibel, tetapi setiap bilangan rasional harus diwakili oleh dua bilangan bulat, pembilang dan penyebut (dengan pengecualian 0 dan 1, yang dapat direpresentasikan sebagai 0dan 1jika diinginkan). Anda dapat mengasumsikan bahwa input dinyatakan dalam istilah terendah. Output harus dinyatakan dalam istilah terendah. Tipe bilangan rasional bawaan adalah format yang dapat diterima, asalkan memenuhi batasan ini. Anda dapat mengabaikan batasan apa pun pada bilangan bulat yang dipaksakan oleh bahasa Anda, tetapi algoritme Anda harus secara teoritis bekerja untuk semua bilangan rasional.

Hitungan byte terendah menang. Aturan standar berlaku.

Contoh

Pertimbangkan input 11/40 dan 3/7. Kami menulis representasi mereka satu di atas yang lain, membatasi bagian yang berulang dengan pipa |. Kemudian kami mengekstrak bagian berulang dengan panjang yang sama, dan menerapkan bitor XOR padanya dan bagian sebelumnya.

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

Angka rasional yang dihasilkan adalah 89/520.

Uji kasus

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
sumber
Berapa periode maksimum yang kami butuhkan untuk mendukung?
Neil
@ Neil Apa yang membuat Anda berpikir bahwa maksimum seperti itu ada?
orlp
3
Catatan: Beberapa angka memiliki dua ekspansi biner, yaitu angka-angka di mana periode akhirnya memiliki panjang satu. Tersirat dalam definisi masalah di atas bahwa kita harus memilih representasi yang berakhir dalam000...kasus ini (yang juga kita dapatkan jika menggunakan algoritme denganr). Misalnya, dalam hal ini5/8, 1/3kita dapatkan23/24karena kita memilih ekspansi0.101000...untuk5/8. Jika kita memilih0.10011111...sebagai5/8, hasil setelah XOR menjadi19/24, jadi ini salah. Terkait dengan Wikipedia: 0,999 ...
Jeppe Stig Nielsen
3
@JeppeStigNielsen Sial ... Ini berarti bahwa tidak seperti XOR biasa (a ^ b) ^ b == atidak berlaku. Misalnya (19/24 ^ 1/3) ^ 1/3 != 19/24. Itu membuat saya kehilangan sedikit kegembiraan tentang hal ini :(
orlp
1
Lihat juga Seperti apa tampilan operator bitwise di 3d? tentang Matematika .
Ilmari Karonen

Jawaban:

3

Python 3, 193 164 byte

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

Mengambil input sebagai fractions.Fractiontipe Python 3 , dan mengeluarkannya juga.

Fakta menyenangkan (Anda dapat dengan mudah menunjukkan ini menggunakan fungsi-fungsi pembangkit), jika Anda mengubah (a<.5)^(b<.5)ke ((a>=.5)and(b>=.5))atas Anda mendapatkan biner DAN antara dua bilangan rasional. Sebut ini nd(a, b). Lalu kita miliki a + b - 2*nd(a, b) = x(a, b)!

orlp
sumber
Memang kesalahan saya. Permintaan maaf! (perhatikan bahwa tautan ke tio termasuk dalam jawaban akan sangat bagus)
Tn. 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))

Tidak akan berfungsi untuk test case terakhir (integer overflow). Input 4 angka untuk p/q xor r/s, output array dengan dua angka. Untuk testcase 0, 0, Anda harus memasukkan 0, 1, 0, 1.

Bagaimana:

(Semua angka yang dijelaskan di sini adalah dalam bentuk biner.)

  1. temukan angka terkecil b, yang b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
  2. Mari x = p * b / q, y = r * b / q; Konversi p / q, r / ske x / bdan y / b;
  3. Biarkan o = 10 ^ (p - q) - 1; perpecahan x, yuntuk [x % o, x / o], [y % o, y / o]; dapatkan xor untuk setiap bagian [x % o xor y % o, x / o xor y / o], dan gabung kembali ke (x % o xor y % o) + (x / o xor y / o) * o; Donasi sebagai a;
  4. Jika a = 0, jawabannya adalah 0(atau 0 / 1); Kalau tidak, biarkan u = gcd(a, b); jawabannya adalah (a/u)dan (b/u).

tsh
sumber