Tahukah Anda bahwa sejumlah kecil dapat meminjam bit dari jumlah yang lebih besar? Ini sebuah contoh. Katakanlah dua angka 5 dan 14. Pertama, tuliskan dalam biner:
5 14
000101 001110
Pertama kita mengambil terkecil di agak jauh dari jumlah yang lebih besar, dan kami memberikannya kepada yang terkecil off sedikit di nomor lain. Begitu
This bit turns off
|
v
000101 001110
^
|
This bit turns on
Sekarang kita punya
000111 001100
dan nomor kami adalah 7 dan 12. Angka pertama masih lebih kecil, jadi kami melanjutkan.
000111 001100
001111 001000
Sekarang kita punya 15 dan 8, jadi kita bisa berhenti. Kami akan menyebut rangkaian operasi ini "peminjaman bit" dua angka. Mari kita lakukan contoh lain. 20 dan 61.
20 61
010100 111101
010101 111100
010111 111000
111111 100000
63 32
Jadi hasil akhir kami adalah 32, 63. Mari kita lakukan satu lagi. 31, dan 12. 31 sudah lebih besar dari 12, jadi tidak ada yang bisa dilakukan! Pinjam bit 31 dan 12 memberi 31 dan 12, tanpa perubahan.
Tantangan
Tantangan Anda adalah menulis sebuah program atau fungsi yang mengambil dua angka dan meminjamnya sedikit. Dua angka akan selalu bilangan bulat positif. Input dan output Anda dapat dalam format apa pun yang masuk akal.
Tes IO:
Input: 2, 3
Output: 3, 2
Input: 3, 2
Output: 3, 2
Input: 8, 23
Output: 31, 0
Input: 42, 81
Output: 63, 0
Input: 38, 41
Output: 47, 32
Input: 16, 73
Output: 23, 0
Input: 17, 17
Output: 17, 17
Celah standar berlaku, dan jawaban tersingkat dalam byte menang!
Python, 42 byte
Terima kasih kepada @ jimmy23013 untuk bermain golf 4 byte! Terima kasih kepada @LeakyNun untuk bermain golf 2 byte!
Uji di Ideone .
sumber
Mathematica, 46 byte
Metode yang sama seperti yang digunakan dalam solusi saya di J.
Terima kasih kepada @ Martin untuk menghemat 1 byte dan mengingatkan saya pada aplikasi infix
~
.Pemakaian
Input terdiri dari dua argumen integer dan output adalah daftar dengan nilai bit-borrowed.
sumber
#//.{x_,y_}/;x<y:>{BitOr[x,x+1],BitAnd[y,y-1]}&
(mungkin Anda punya ide bagaimana mempersingkatnya)/.
dan ketentuan/;
. Wish Mathematica dapat beralih antara boolean dan bitwise dengan memeriksa tipe argumen ke&&
dan semacamnya.Pyth,
292725222120191816 byteSuite uji.
sumber
05AB1E,
1615 byteCobalah online
sumber
Labyrinth ,
3734 byteCobalah online!
Penjelasan
Primer Labirin Cepat:
Program ini menggunakan algoritma yang sama dengan jawaban lainnya: kami ganti
(a, b)
dengan(a | a+1, b & b-1)
selamaa < b
. Saya akan menambahkan penjelasan lengkap setelah saya mencoba bermain golf lagi.IP dimulai di sudut kiri atas, ke kanan.
?
membaca bilangan bulata
. Maka"
adalah no-op, tetapi perlu untuk mencegah IP dari turun segera. Ini juga jalan buntu, sehingga IP berbalik dan mengeksekusi?
lagi untuk membacab
.}
lalu pindahb
dari main ke aux , jadi sekarang kita punya:The
|
kemudian tidak apa-apa, karena dibutuhkan bitwise ORa
dan0
. Karena kita tahua
selalu positif, IP berbelok ke timur (karena tidak bisa berbelok ke barat). Ini memulai lingkaran utama program. Kita mulai dengan bagian linier pendek untuk membandingkana
danb
:IP sekarang di persimpangan lain. Pertama, mari kita perhatikan kasus di mana hasilnya positif. Itu berarti
b > a
dan kita perlu melakukan satu iterasi lagi. Iterasi itu juga sepenuhnya linier. Perhatikan bahwa tumpukan saat ini:Dan kemudian kita kembali ke awal dari loop (karena
a
lagi positif, IP berbalik ke timur lagi).Jika suatu saat
b-a
tidak lagi positif, IP akan mengambil satu dari dua jalur lainnya. Perhatikan bahwa dalam kedua kasus kami menjemputa
dengan{
, lalu tekan sudut di mana IP mengikuti tikungan dan kemudian mencetaka
dengan!
. Sekarang bagian atas tumpukan lagib-a
yang berarti bahwa dalam kedua kasus IP akan berakhir bergerak ke timur. Yang tersisa adalah bit linear pendek sekarang:sumber
Java 7, 73 byte
Kasus yang tidak disatukan & uji:
Coba di sini.
Keluaran:
Aturan tantangan lama [
126125123 byte]:CATATAN: Aturan tantangan lama menggunakan dua bilangan bulat-array sebagai input, bukan dua bilangan bulat yang longgar.
sumber
while
lingkaran Anda seperti inifor(;x<y;x|=x+1,y&=y-1);
-_-
Saya berharap saya telah menulisnya dengan lebih baik dari awal. Untungnya itu bukan perubahan yang tidak masuk akal atau drastis. Juga, ya saya tidak mengomentari setiap jawaban, tetapi saya memberi tahu setiap pengguna. Saya tidak ingin memberi tahu pengguna yang sama beberapa kali. Saya tidak mengomentari posting Dennis, tetapi itu karena dia adalah salah satu pengguna yang mendorong saya untuk mengubahnya pada awalnya.JavaScript (ES6), 33 byte
Port jawaban sederhana oleh @miles.
sumber
f=
awalnya: PJulia, 27 byte
Cobalah online!
Bagaimana itu bekerja
Kami mendefinisikan operator biner
<|
untuk tujuan kami. Ini tidak terdefinisi dalam versi terbaru Julia, tetapi masih diakui sebagai operator oleh parser. Sementara\
(tidak secara eksplisit didefinisikan untuk bilangan bulat) adalah salah satu byte lebih pendek, diutamakan yang tinggi akan membutuhkan menggantikanx|-~x<|y&~-y
dengan(x|-~x)\(y&~-y)
, sehingga meningkatkan jumlah byte.<|
memeriksa apakah argumen pertamanya benar-benar kurang dari argumen kedua. Jika demikian, itu secara rekursif menyebut dirinya dengan argumen x | - ~ x = x | (x + 1) dan y & ~ -y = y & (y - 1) .Karena menambahkan 1 ke x matikan semua bit set trailing dan bit unset terendah, x | (x +1) mengaktifkan bit unset terendah (dan tidak ada bit lain). Demikian juga, karena mengurangi 1 dari y matikan semua trailing bit yang tidak disetel dan bit set terendah, y & (y +1) matikan bit set terendah.
Akhirnya, ketika ketidaksetaraan x <y tidak lagi berlaku,
<|
kembalikan pasangan [x, y] .sumber
MATLAB,
6766 bytelingkaran:
rekursif (67 byte):
Pendekatan yang sama untuk mengubah bit seperti banyak jawaban lainnya.
sumber
Clojure, 63 byte
Metode yang sama seperti yang digunakan dalam solusi saya di J.
Pemakaian
sumber