Membagi, membalik, dan menggabungkan kembali bilangan bulat

16

Latar Belakang

Sudah terkenal dalam matematika bahwa bilangan bulat dapat dimasukkan ke dalam korespondensi satu-ke-satu dengan pasangan bilangan bulat. Ada banyak cara yang memungkinkan untuk melakukan ini, dan dalam tantangan ini, Anda akan menerapkan salah satunya dan operasi terbalik.

Tugas

Masukan Anda adalah bilangan bulat positif n > 0. Hal ini diketahui bahwa terdapat bilangan bulat non-negatif yang unik a, b ≥ 0sehingga . Output Anda adalah "versi terbalik" , bilangan bulat positif .n == 2a * (2*b + 1)n2b * (2*a + 1)

Anda dapat mengasumsikan bahwa input dan output sesuai dengan tipe data integer unsigned standar bahasa Anda.

Aturan dan penilaian

Anda dapat menulis program lengkap atau fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji kasus

Ini diberikan dalam format in <-> out, karena fungsi yang akan diterapkan adalah kebalikannya sendiri: jika Anda memberi umpan balik ke hasilnya, Anda harus mendapatkan input asli.

1 <-> 1
2 <-> 3
4 <-> 5
6 <-> 6
7 <-> 8
9 <-> 16
10 <-> 12
11 <-> 32
13 <-> 64
14 <-> 24
15 <-> 128
17 <-> 256
18 <-> 48
19 <-> 512
20 <-> 20
28 <-> 40
30 <-> 384
56 <-> 56
88 <-> 224
89 <-> 17592186044416

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa. Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda bisa menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir dalam tajuk:

## Perl, 43 + 2 (-p flag) = 45 bytes

Anda juga dapat membuat tautan nama bahasa yang kemudian akan muncul di cuplikan papan peringkat:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Tampilkan cuplikan kode

code-golf number number-theory Zgarb
sumber
1
Lucu, masalah ini diposting di golf anarki minggu lalu
feersum
@feersum Oh, saya tidak sadar. Kebetulan sekali.
Zgarb
2
Wajib xkcd.com/153
corsiKa

Jawaban:

11

Jelly , 17 16 15 byte

BUi1µ2*³:2*×Ḥ’$

Cobalah online!

Bagaimana itu bekerja

BUi1µ2*³:2*×Ḥ’$    Main link. Input: n

B                  Convert n to base 2.
 U                 Reverse the array of binary digits.
  i1               Get the first index (1-based) of 1.
                   This yields a + 1.
    µ              Begin a new, monadic chain. Argument: a + 1
     2*            Compute 2 ** (a+1).
       ³:          Divide n (input) by 2 ** (a+1).
                   : performs integer division, so this yields b.
         2*        Compute 2 ** b.
              $    Combine the two preceding atoms.
            Ḥ      Double; yield 2a + 2.
             ’     Decrement to yield 2a + 1.
           ×       Fork; multiply the results to the left and to the right.
Dennis
sumber
Tunggu, apakah Anda menerapkan operator di Jelly agar sesuai dengan masalah? Dalam hal ini LOL
Alexander Torstling
Saya tidak. Satu- satunya komitmen pada Jelly setelah tantangan ini diposting adalah pembaruan dokumentasi, dan semua operator yang digunakan dalam jawaban ini telah diimplementasikan setidaknya selama sebulan. Jangan ragu untuk memverifikasi
Dennis
Jangan khawatir, saya tidak terbiasa dengan aturan atau apa pun, saya hanya berpikir itu keren bahwa golf telah datang kepada orang yang menciptakan bahasa mereka sendiri!
Alexander Torstling
2
Dan ada banyak dari mereka. Lihat Bahasa pemrograman apa yang telah dibuat oleh pengguna PPCG? .
Dennis
10

Pyth, 16 15 byte

*hyJ/PQ2^2.>QhJ

Terima kasih 1 byte untuk Dennis

Suite uji

Penjelasan:

*hyJ/PQ2^2.>QhJ
                    Implicit: Q = eval(input())
     PQ             Take the prime factorization of Q.
    /  2            Count how many 2s appear. This is a.
   J                Save it to J.
  y                 Double.
 h                  +1.
          .>QhJ     Shift Q right by J + 1, giving b.
        ^2          Compute 2 ** b.
*                   Multiply the above together, and print implicitly.
isaacg
sumber
7

MATL , 22 byte

Yft2=XK~)pq2/2w^Ks2*Q*

Cobalah online!

Penjelasan

Yf      % factor
t       % duplicate
2=      % compare to 2 (yields a logical array)
XK      % save a copy of that to variable K
~)      % keep only values != 2 in the factors array
p       % multiply that factors
q2/     % product - 1 / 2
2w^     % 2^x

K       % load variable K (the logical array)
s       % sum (yields the number of 2s)
2*Q     % count * 2 + 1

*       % multiply both values
Rainer P.
sumber
Sangat bagus! Anda dapat menggunakan Quntuk 1+(ini telah diperkenalkan baru-baru ini) dan quntuk 1-. Itu juga menghemat ruang (yang bisa Anda simpan dengan cara lain H). Lihat di sini
Luis Mendo
@LuisMendo Terima kasih. Tidak tahu fitur itu.
Rainer P.
5
Pemukulan Luis yang dilakukan dengan baik menggunakan MATL!
Stewie Griffin
6

Python 2, 39 byte

lambda n:2*len(bin(n&-n))-5<<n/2/(n&-n)

n & -nmemberikan kekuatan terbesar 2 yang membelah n. Ini bekerja karena dalam aritmatika dua-pelengkap -n == ~n + 1,. Jika nmemiliki k tertinggal angka nol, mengambil pelengkap akan menyebabkan ia memiliki k yang tertinggal. Kemudian menambahkan 1 akan mengubah semua trailing menjadi nol, dan mengubah bit 2 ^ k dari 0 menjadi 1. Jadi -ndiakhiri dengan 1 diikuti oleh k 0 (sama seperti n), sambil memiliki bit yang berlawanan dari nsemua tempat yang lebih tinggi.

feersum
sumber
dapat Anda jelaskan bagaimana caranya n&-n kerjanya? saya melihat apa yang dilakukan trik ini tetapi tidak seberapa :(
Erwan
n&-n mengembalikan kekuatan tertinggi 2 yang divdes n .
Neil
@Erwan saya jelaskan n & -n .
feersum
Saya mendapatkan program yang sesuai pada golf Anarchy n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100 , tetapi dua karakter di belakang solusi terbaik.
xnor
@ xnor Petunjuk: solusi 59-byte (well, setidaknya saya sendiri) tidak berfungsi untuk semua nilai n.
feersum
6

MATL , 25 26 byte

:qt2w^w!2*Q*G=2#f2*q2bq^*

Ini menggunakan rilis saat ini (10.2.1) dari bahasa / kompiler.

Cobalah online!

Penjelasan

Cukup mudah, berdasarkan kekuatan kasar. Mencoba semua kombinasi a dan b , memilih yang sesuai dan melakukan perhitungan yang diperlukan.

:q          % implicit input "n". Generate row vector [0,1,...,n-1], say "x"
t2w^        % duplicate and compute 2^x element-wise
w!2*Q       % swap, transpose to column vector, compute 2*x+1
*           % compute all combinations of products. Gives 2D array
G=2#f       % find indices where that array equals n
2*q2bq^*    % apply operation to flipped values
Luis Mendo
sumber
1
Hah! :-P Dipukuli dalam bahasa Anda sendiri ... pertama kali?
Stewie Griffin
@StewieGriffin Yap! Tonggak sejarah yang bagus :-)
Luis Mendo
5

Julia, 41 byte

n->2^(n>>(a=get(factor(n),2,0)+1))*(2a-1)

Ini adalah fungsi anonim yang menerima integer dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel.

Kami mendefinisikan asebagai 1 + eksponen 2 dalam faktorisasi utama n. Sejak factorkembali sebuah Dict, kita dapat menggunakan getdengan nilai default 0 dalam kasus faktorisasi prima tidak mengandung 2. Kami kanan sedikit pergeseran noleh a, dan mengambil 2 untuk kekuatan ini. Kami mengalikannya dengan 2a-1untuk mendapatkan hasilnya.

Alex A.
sumber
4

Perl 5, 40 byte

38 byte plus 2 untuk -p

$i++,$_/=2until$_%2;$_=2*$i+1<<$_/2-.5

-pmembaca STDIN ke dalam variabel $_.

$i++,$_/=2until$_%2kenaikan $i(yang dimulai dari 0) dan separuh $_sampai $_bukan nol mod 2. Setelah itu, $_adalah faktor ganjil dari angka asli, dan $imerupakan eksponen 2.

$_=2*$i+1<<$_/2-.5- Sisi kanan =hanya rumus untuk angka yang dicari: {1 lebih dari dua kali eksponen 2} kali {2 pangkat dari {setengah faktor ganjil dikurangi setengah}}. Tetapi "waktu {2 pangkat dari ...}" dinobatkan sebagai "digeser ke kiri oleh ...". Dan sisi kanan yang ditugaskan$_ .

Dan -pcetakan $_.

msh210
sumber
2

C, 49 byte

a;f(n){for(a=0;n%2-1;a++)n/=2;return 2*a+1<<n/2;}
Level River St
sumber
2

JavaScript ES6, 36 33 byte

n=>63-2*Math.clz32(b=n&-n)<<n/b/2

Pemahaman saya adalah bahwa Math.clz32ini akan menjadi lebih pendek dari mengutak-atik toString(2).length.

Sunting: Disimpan 3 byte berkat @ user81655.

Neil
sumber
Bagus. Anda juga dapat menyimpan beberapa byte dengan mengatur n&-nke variabel:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655
@ user81655 Terima kasih; Saya hanya berharap saya bisa menggunakan n&=-n, tetapi saya perlu nlagi ...
Neil
1

PARI / GP , 38 byte

f(n)=k=valuation(n,2);(2*k+1)<<(n>>k\2)

Perhatikan itu >>dan \memiliki prioritas yang sama dan dihitung dari kiri ke kanan, sehingga bagian terakhir bisa n>>k\2lebih daripada (n>>k)\2. Versi ungolfed akan membuat kleksikal dengan my:

f(n)=
{
  my(k=valuation(n,2));
  (2*k+1) << ((n>>k)\2);
}
Charles
sumber