Tujuan Anda adalah membuat fungsi atau program untuk membalikkan bit dalam rentang bilangan bulat yang diberi bilangan bulat n . Dengan kata lain, Anda ingin menemukan permutasi bit-reversal dari rentang 2 n item, diindeks nol. Ini juga merupakan urutan OEIS A030109 . Proses ini sering digunakan dalam komputasi Fast Fourier Transforms, seperti algoritma Cooley-Tukey di tempat untuk FFT. Ada juga tantangan untuk menghitung FFT untuk urutan di mana panjangnya adalah kekuatan 2.
Proses ini mengharuskan Anda untuk mengulangi rentang [0, 2 n -1] dan mengubah setiap nilai menjadi biner dan membalikkan bit dalam nilai tersebut. Anda akan memperlakukan setiap nilai sebagai n- digit angka dalam basis 2 yang berarti pembalikan hanya akan terjadi di antara n bit terakhir .
Misalnya, jika n = 3, kisaran bilangan bulat adalah [0, 1, 2, 3, 4, 5, 6, 7]
. Ini adalah
i Regular Bit-Reversed j
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
di mana setiap indeks i dikonversi ke indeks j menggunakan bit-reversal. Ini berarti outputnya adalah [0, 4, 2, 6, 1, 5, 3, 7]
.
Output untuk n dari 0 hingga 4 adalah
n Bit-Reversed Permutation
0 [0]
1 [0, 1]
2 [0, 2, 1, 3]
3 [0, 4, 2, 6, 1, 5, 3, 7]
Anda mungkin telah memperhatikan pembentukan pola. Diberikan n , Anda dapat mengambil urutan sebelumnya untuk n -1 dan menggandakannya. Kemudian gabungkan daftar yang digandakan ke daftar ganda yang sama tetapi bertambah satu. Memperlihatkan,
[0, 2, 1, 3] * 2 = [0, 4, 2, 6]
[0, 4, 2, 6] + 1 = [1, 5, 3, 7]
[0, 4, 2, 6] ⊕ [1, 5, 3, 7] = [0, 4, 2, 6, 1, 5, 3, 7]
dimana ⊕
merupakan gabungan.
Anda dapat menggunakan salah satu dari dua metode di atas untuk membentuk solusi Anda. Jika Anda tahu cara yang lebih baik, Anda bebas untuk menggunakannya juga. Metode apa pun baik-baik saja asalkan menghasilkan hasil yang benar.
Aturan
- Ini adalah kode-golf sehingga solusi terpendek menang.
- Builtin yang memecahkan tantangan ini secara keseluruhan dan builtin yang menghitung bit-reversal dari suatu nilai tidak diperbolehkan. Ini tidak termasuk builtin yang melakukan konversi biner atau operasi bitwise lainnya.
- Solusi Anda setidaknya harus valid untuk n dari 0 hingga 31.
IntegerReverse[Range[2^#]-1,2,#]&
,. (Saya tidak tahu mengapa Mathematica membutuhkan built-in tapi saya kira itu tidak jauh lebih aneh daripadaSunset
...)0
alih-alih[0]
atau haruskah itu daftar?Jawaban:
Jelly ,
76 byteTerima kasih kepada @EriktheOutgolfer untuk bermain golf 1 byte!
Cobalah online!
Bagaimana itu bekerja
sumber
05AB1E , 8 byte
Kode:
Penjelasan:
Menggunakan pengkodean CP-1252 . Cobalah online! .
sumber
0)ïsF·D>«
meskipun dekat. Punya beberapa masalah dengan '0'.¾
. Harus ingat trik itu.MATL,
13121098 byteCobalah secara Online
Penjelasan
Demi kelengkapan, inilah jawaban lama saya menggunakan pendekatan non-rekursif (9 byte).
Cobalah secara Online
Penjelasan
sumber
J,
1511 byteAda alternatif untuk 15 byte yang menggunakan konversi dan pembalikan biner lurus ke depan.
Pemakaian
Penjelasan
sumber
Jelly , 5 byte
Cobalah online!
-1 terima kasih kepada Dennis .
sumber
Haskell ,
4037 byteCobalah online!
Terima kasih kepada @Laikoni selama tiga byte!
sumber
Oktaf, 37 byte
Membuat fungsi anonim bernama
ans
yang hanya bisa dipanggil denganans(n)
.Demo online
sumber
Python 2,
565554 byteUji di Ideone .
Terima kasih kepada @xnor karena bermain golf 1 byte!
sumber
[0][n:]or
.Java,
422419 byte:Yah, saya akhirnya belajar Java untuk bahasa pemrograman kedua saya, jadi saya ingin menggunakan keterampilan baru saya untuk menyelesaikan tantangan sederhana, dan meskipun ternyata sangat lama, saya tidak kecewa. Saya senang saya bisa menyelesaikan tantangan sederhana di Jawa.
Cobalah secara Online! (Ideone)
sumber
Mathematica,
5633 byteHitungan byte mengasumsikan sumber yang disandikan ISO 8859-1.
Ini menggunakan definisi rekursif untuk mendefinisikan operator unary
±
.sumber
Perl,
4645 byteTermasuk +1 untuk
-p
Berikan nomor input pada STDIN
sumber
Pyth - 11 byte
Test Suite .
sumber
Javascript ES6,
655351 byteMenggunakan algoritma rekursif double-increment-concursive.
Contoh berjalan:
sumber
f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]
?n==1
, terima kasih.f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Python 3,
6759 byteBerkat @ Dennis untuk -8 byte
Kami mungkin juga memiliki implementasi langsung (dimodifikasi) dengan Python, meskipun ini cukup lama.
Fungsi anonim yang mengambil input dengan argumen dan mengembalikan permutasi bit-terbalik sebagai daftar.
Bagaimana itu bekerja
Cobalah di Ideone
sumber
Dyalog APL , 12 byte
Membutuhkan
⎕IO←0
yang default pada banyak sistem.2⊥
dari-base-2 of⊖
membalik2⊥⍣¯1
kebalikan dari-base-2 dari⍳
n bilangan bulat pertama , di mana n adalah2*
2 pangkat dari⎕
input numerikTryAPL online!
Sebagai perbandingan, berikut adalah metode lain:
(
kereta fungsi ...2∘×
dua kali (argumen),
digabungkan ke1+
satu ditambah2∘×
dua kali (argumen))⍣
diterapkan sebanyak yang ditentukan oleh⎕
input numerik⊢
di0
nolsumber
(⍋,⍨)⍣⎕⊢0
(⎕io←0
)K (ngn / k) ,
118 byteCobalah online!
&
adalah kata kerja terakhir dalam komposisi sehingga kita perlu:
memaksanya menjadi monadiksumber
Julia,
2322 byteImplementasi proses yang agak mudah dijelaskan dalam spec tantangan.
Cobalah online!
sumber
Pyth, 8 byte
Cobalah online: Demonstrasi atau Test Suite
Penjelasan:
sumber
Clojure, 78 byte
Cukup mengikuti spesifikasi ...
sumber
Ruby, 57 byte:
sumber
PHP, 57 byte
mengambil input dari parameter baris perintah, mencetak nilai garis bawah-dibatasi. Jalankan dengan
-nr
.solusi rekursif, 72 byte
fungsi mengambil integer, mengembalikan array
sumber
Ruby , 51 byte
Cobalah online!
sumber
Perl 6 , 42 byte
Cobalah online!
Menambah integer hanya membalik urutan bit paling tidak signifikan, misalnya dari
xxxx0111
kexxxx1000
. Jadi indeks bit-reversed berikutnya dapat diperoleh dari yang sebelumnya dengan membalik urutan bit paling signifikan. Topeng XOR dapat dihitung denganm - (m >> (ctz(i) + 1))
untukm = 2**n
ataum = 2**n-1
.Perl 6 , 30 byte
Cobalah online!
Pendekatan rekursif.
sumber
JavaScript (Firefox 30-57), 48 byte
Port of @ Dennis ♦ adalah solusi Python 2.
sumber
Japt ,
1413 byteCobalah online!
Dibongkar & Cara kerjanya
Implementasi langsung.
sumber
n2
:Í
APL (Dyalog Classic) , 9 byte
Cobalah online!
⎕
input yang dievaluasi(
)⍣⎕⊢0
terapkan benda(
)
itu berkali-kali, dimulai dengan0
,⍨
menggabungkan hasil saat ini dengan dirinya sendiri⍋
indeks permutasi sort-ascendingsumber
x86, 31 byte
Membawa cukup besar
int[] buffer
dieax
dan n diecx
, dan mengembalikan buffer dieax
.Menerapkan algoritma gabungan yang diberikan dalam pernyataan tantangan. Dimungkinkan untuk menyimpan byte dengan menambah pointer dengan 4 daripada menggunakan akses array secara langsung, tetapi
lea
/mov
sudah cukup singkat (3 byte untuk 3 regs dan pengganda).Hexdump:
sumber