Tulis kode terpendek untuk membalik urutan bit integer 32-bit.
Aturan:
- Input dianggap bilangan bulat atau string yang setara jika bahasa Anda tidak mendukung nilai numerik (mis. Windows Batch).
- Output harus berupa bilangan bulat atau string yang setara jika bahasa Anda tidak mendukung nilai numerik (mis. Windows Batch).
- Hanya perpustakaan standar.
- Mungkin fungsi atau program lengkap.
- Input dapat berasal dari
stdin
atau sebagai argumen fungsi. - Output harus berupa
stdout
atau sebagai nilai yang dikembalikan. - Jika bahasa Anda memiliki fungsi pustaka built-in atau standar yang melakukan ini dalam satu langkah (misalnya
rbit
dalam perakitan ARM), itu tidak dapat digunakan.
Contoh:
Kunci:
- desimal
- biner
- (membalikkan)
- biner terbalik
- output desimal
Contoh:
-90
(Contoh 8-bit untuk demonstrasi)10100110b
- (membalikkan)
01100101b
101
486
00000000000000000000000111100110b
- (membalikkan)
01100111100000000000000000000000b
1736441856
-984802906
11000101010011010001100110100110b
- (membalikkan)
01100101100110001011001010100011b
1704506019
Catatan: Kelalaian adalah permainan gratis. Jika saya tidak mengatakannya, dan itu bukan salah satu celah standar , maka itu sepenuhnya diizinkan.
Jawaban:
perakitan x86, 9 byte
Dalam bentuk byte:,
33 C0 40 D1 E9 13 C0 73 FA
9 byte.sumber
__fastcall
dan tidak punyaret
.Perakitan MMIX (28 Bytes)
Angka 64 bit
Ini berkumpul untuk:
Bagaimana cara kerjanya?
The
MOR
instruksi melakukan perkalian matriks pada dua jumlah 64-bit yang digunakan sebagai dua 8x8 matriks boolean. Angka boolean dengan digit abcdefghklmnopqr 2 digunakan sebagai matriks seperti ini:The
MOR
mengalikan instruksi matriks diwakili oleh argumen mereka di mana perkalianand
dan penambahan adalahor
. Ini:dan selanjutnya:
yang merupakan urutan kebalikan dari bit dari nomor aslinya.
Angka 32 bit
Jika Anda hanya ingin kebalikan dari angka 32 bit alih-alih angka 64 bit, Anda dapat menggunakan metode yang dimodifikasi ini:
dirakit:
Multiplikasi matriks pertama pada dasarnya bekerja seperti ini:
octabyte yang sesuai adalah
#0000000001020408
yang kita muat dalam dua instruksi pertama. Perkalian kedua terlihat seperti ini:Octabyte yang sesuai adalah
#0102040810204080
yang kita buat dari matriks pertama seperti ini:Perkalian kedua adalah bisnis seperti biasa, kode yang dihasilkan memiliki panjang yang sama (28 byte).
sumber
POLY
Instruksi dari VAX pada dasarnya adalah penggandaan-dan-tambahkan yang menyatu dengan loop bawaan. Hal serupa juga ada dalam arsitektur modern (seperti x86), tetapi mereka biasanya tidak memiliki loop bawaan untuk mengevaluasi seluruh polinomial sekaligus.80386 unit (
1312 byte)Sebagai fungsi dalam sintaks AT&T menggunakan konvensi pemanggilan cdecl.
Fungsi ini berkumpul ke urutan byte berikut:
Dipecah menjadi instruksi:
Ia bekerja seperti ini: Di masing-masing dari 32 iterasi dari loop, argumen, yang terletak di
4(%esp)
, benar bergeser oleh satu posisi. Bit terakhir secara implisit bergeser ke bendera carry. Theadc
instruksi menambahkan dua nilai dan menambah nilai membawa bendera untuk hasilnya. Jika Anda menambahkan nilai pada dirinya sendiri, yaitu%eax
, Anda secara efektif menggesernya dengan satu posisi. Ini membuatadc %eax,%eax
cara yang mudah untuk bergeser ke kiri%eax
satu posisi dengan satu posisi sambil menggeser konten bendera carry ke bit orde rendah.Saya ulangi proses ini 32 kali sehingga seluruh konten
4(%esp)
dibuang ke%eax
. Saya tidak pernah secara eksplisit menginisialisasi%eax
karena isinya sebelumnya digeser selama loop.sumber
C,
635248Versi asli:
Versi terbaru (dengan perubahan yang disarankan oleh Allbeert , es1024 , dan Dennis ):
Catatan: Karena versi kedua menghilangkan pengaturan
r=0
, kode ini mengasumsikan bahwaint
32 bit. Jika asumsi ini salah, fungsi kemungkinan besar akan menghasilkan hasil yang salah, tergantung pada keadaan awalr
saat masuk ke fungsi.Versi final (dengan perubahan lebih lanjut disarankan oleh Dennis dan Alchymist ):
Catatan: Ini menempatkan deklarasi variabel kerja
r
dani
ke dalam daftar parameter. Parameternya adalah sebagai berikut:n
adalah angka yang akan dibalik sedikit.r
dani
variabel kerja yang harus dilewatkan sebagai 0.sumber
int
tipe fungsi, dan juga berubahreturn r
menjadi sesuatu sepertii=r
karena kebanyakan kompiler C cenderung meninggalkan hasil operasi terakhir dalam register kembali. Ini bekerja pada gcc dan cl untuk saya.r(n){...}
bukannyar(int n){...}
int
diint r=0,i=32;
kecuali Anda memindahkan mereka keluar dari fungsi tubuh.-1 >> 1
adalah-1
untuk AS dan2**31 - 1
untuk LS, sementara-1 / 2
ini0
.r
dani
sebagai argumen? Akan menghemat tiga byte lagi ...Julia 0.2, 33 byte
Seperti apa bentuknya.
bits
memberi Anda representasi bit (menghormati komplemen dua).parseint
tidak peduli tentang komplemen dua, tetapi mengembalikan integer 32 bit, sehingga komplemen keduanya hanya ditangani oleh overflow.Menurut changelogs, deteksi overflow ditambahkan ke
parseint
dalam Julia 0.3, jadi ini mungkin tidak berfungsi lagi.sumber
Python 2, 50
Secara umum sama dengan solusi Pyth saya. Ambil input mod 2 ** 32, konversikan ke biner empuk 32-bit, balikkan, ubah sengatan biner menjadi desimal dan cetak.
sumber
CJam, 15 byte
Cobalah online.
"Game gratis" yang digunakan joker: Outputnya akan selalu berupa integer yang tidak ditandai .
Uji kasus
Bagaimana itu bekerja
sumber
JavaScript (E6) 37
39 40 50Fungsi, input angka dan mengembalikan nomor terbalik.
Algoritma paling dasar, mungkin bisa lebih banyak golf dengan beberapa trik pintar.Edit Rekursi alih-alih loop
Sunting 2 Mengikuti saran @bebe
k*2
alih-alihk<<1
Sunting 3 Sesuatu yang saya lewatkan sama sekali: itu loop 32 bit penuh, tidak perlu menginisialisasi k. Terima kasih @ FuZxxl
Dulu
Uji Di konsol FireFox, uji menggunakan angka dalam OP dan beberapa angka 16 dan 32 bit yang lebih acak
Contoh hasil uji
sumber
b=k=0,R=v=>b++<32?R(v>>1,k+=k+(v&1)):k
untuk sekali pakai danR=(v,b=0,k=0)=>b<32?R(v>>1,b+1,k+k+(v&1)):k
dapat digunakan kembalik<<1
menjadik*2
danv>>1
menjadiv/2
. itu bekerja untuk 486. saya tidak tahu tentang kasus tes lainassemply x86, 10 Bytes
Ini menganggap input dalam eax, output dalam edx. (Juga, pada output eax adalah nol dan CF dan ZF diatur, jika ada yang peduli).
Alih-alih penghitung, 1 tambahan didorong di awal sebagai penanda data akhir
sumber
ret
instruksi untuk kembali dari fungsi dan mengimplementasikan cdecl (yaitu mengubahrcr %eax
kercr 4(%esp)
danrcl %edx
kercl %eax
), Anda berakhir dengan satu byte tambahan untukret
dan dua byte lainnya untuk referensi memori. Tetap saja, solusi yang bagus.J (
171513 byte)Berikut adalah definisi eksplisit untuk menjelaskan apa yang dilakukannya:
#: y
mewakiliy
sebagai nomor basis 2 menggunakan tempat sebanyak yang diperlukan.x {. y
mengambil|x
(besarnyax
) item dariy
, dari depan jikax
positif, dari belakang jikax
negatif. Jika kami mengambil lebih banyak item daripada yang ada, hasilnya diisi dengan nol._32 {. #: y
secara efektif bantalan#: y
hingga 32 bit.|. y
membaliky
, i. membalik urutan item dalamy
.#. y
ditafsirkany
sebagai nomor basis-2.sumber
Dyalog APL , 10 byte
2⊥
dari-base-2 of⌽
yang terbalik⎕
input numerik⊤⍨
dalam sistem bilangan yang terdiri dari32/2
32 bitTryAPL online!
sumber
Python - 89
Python mewakili angka biner negatif secara sederhana
-0b{positive_number}
. Jadi untuk mengatasi ini, lengkapi angka negatif dan kemudian XOR dengan semua 1.Setelah itu, buat representasi string dari integer berdasarkan pada format
{:032b}
yang menyediakan representasi 32bit dari angka tersebut. Akhirnya, balikkan string dan putar kembali menjadi integer.EDIT
Terima kasih kepada @Martin Büttner karena menunjukkan masalah komplemen dua. Jika
n
diakhiri dengan 1 maka dengan komplemen dua's versi terbalik akan negatif.Untungnya, seperti yang dijelaskan di atas, Python menyukai angka biner negatif dengan cara yang cukup sederhana. Untungnya,
int
fungsi Python memungkinkan karakter tanda opsional dalam argumen pertamanya.Jadi sekarang, tambahkan tanda minus jika
n
aneh untuk memuaskan komplemen dua.sumber
['','-'][n%2]
adalah'-'*(n%2)
.Pyth ,
333222Penjelasan:
Golf:
33 -> 32: Memindahkan add to sebelum membalikkan untuk menyimpan kutipan akhir.
32 -> 22: Digunakan Q mod 2 ^ 32 bukan mesin yang rumit. Menggabungkan kedua string menjadi satu.
Kasus uji:
sumber
GNU dc, 27 byte
Keluaran:
Bash + coreutils, 45 byte
Keluaran:
Fungsi C, 89 byte
Ide yang sama seperti /codegolf//a/36289/11259 - menggunakan Stanford bit twiddling hacks . Tidak akan memenangkan golf, tetapi tetap menarik:
Keluaran:
sumber
Fungsi Java, 64 karakter.
Harus juga bekerja di C.
sumber
PHP, 46 Bytes
Versi Online
atau
sumber
substr
perlu (-12 byte). Anda harus menyebutkan cara menjalankannya.-984802906
?<?=bindec(strrev(sprintf("%064b",$argn<<32)));
JS 115
Yah itu sama sekali tidak terlihat bagus: D
Metode @Florian F di JS panjangnya 53 byte:
sumber
it may be a function
berarti aturan Anda tidak perlu peringatan atau cepatC #
8174Operasi bit yang kemungkinan besar dapat dilakukan lebih pendek di semua bahasa pemrograman.
Pada dasarnya, loop melalui semua kekuatan 2 hingga integer maksimum + 1 (Yang berubah menjadi kekuatan dua) dan karena (2.147.483.647 +1) = 0 Saya dapat loop ke 0. Bit bergeser ke kiri untuk memindahkan bit ke yang pertama posisi. Bit terakhir di tempat 32 berjalan 31 langkah ke kanan, kedua terakhir ke 30 dll. Jadi dengan menggunakan DAN operator dengan 1 saya akan tahu apakah itu 1 atau 0. Jika 1, saya akan menambahkan nilai i saat ini ke hasil dan Kembalikan.
sumber
i
ketika Anda mendeklarasikannya, dan menyimpan byte dengan menghapusi++
dari for loop, dan alih-alih membandingkan hasil1&...
dengan 0 Anda dapat menghapus pernyataan if sama sekali dan kalikani
dengan hasil yang diberikanr|=i*(1&(V>>(31-l++)));
di dalam loopC # 142
Diperluas
sumber
Python - 37
Mirip dengan solusi @ isaacg.
sumber
C ++, 160
Ini bukan yang terpendek, namun hanya menggunakan 24 operasi.
Diambil dari buku Hacker's Delight.
Golf:
Tidak Disatukan:
sumber
Haskell, 145 - tidak ada operasi bitwise
Bit-twiddling menganggap saya sebagai antitesis dari Haskell, jadi saya telah menghindari penggunaan operator bitwise. Program yang dihasilkan tentu saja bukan kontestan terpendek, tapi saya pikir penggunaan matematika bukannya sedikit-sedikit menarik setidaknya.
Penjelasan
0
s dan1
s, bit paling signifikan pertama dengan berulang kali membagi dengan 2 dan mengambil sisanya0
hingga s ke akhir daftar ini0
dan1
menjadi integer dengan asumsi bit paling signifikan adalah yang pertama (berulang ganda dan tambahkan).Saya tidak yakin apa yang merupakan "perpustakaan standar" di Haskell jadi saya berasumsi Data.Tuple dan Data.List OK (mereka cukup standar).
Juga, outputnya adalah bilangan bulat 32-bit yang tidak ditandatangani karena perubahan itu akan menghabiskan banyak byte: Saya berpendapat ini di bawah "kelalaian adalah permainan gratis".
sumber
PHP,
4641 bytecoba online
bitwise ... lebih atau kurang. Jalankan sebagai pipa dengan
php -nR '<code>'
.PHP, 46 byte
solusi bitwise murni; dijalankan sebagai pipa dengan
-nR
.PHP,
4759 bytependekatan bawaan lainnya; simpan ke file dan jalankan sebagai pipa dengan
-F
.sumber
Perl - 60
+1 untuk p flag (beri tahu saya jika saya salah menghitung ini).
Jalankan dengan:
sumber
C ++ 69
sumber
e;i;
? Deklarasi tanpa tipe bukan C ++ yang valid. Untuk variabel itu bahkan tidak valid C.int r(int n){int e=0,i=0;for(;i<32;)e=e*2|1&n>>i++;return e;}
61 byte :)R, 45
Contoh:
Selalu saja malu dengan jawaban Python. Kata kunci fungsi sialan itu.
sumber
Rubi,
4341 bytedef r(n)(0..31).inject(0){|a,b|a*2+n[b]}end
Di Ruby, menggunakan notasi indeks braket (foo [i]) mengembalikan bit di tempat ke-n.
--Edit--
Refactoring
inject
fungsionalitas mencukur beberapa bytedef r(n)z=0;32.times{|i|z=z*2+n[i]};z;end
sumber
Perl5: 46
Tidak ada yang mewah. Ini menggeser output ke kiri, salin lsb sebelum menggeser sumber ke kanan.
sumber
Clojure,
202156142sumber
Perl (37 + 1)
pada dasarnya port solusi C oleh Todd Lehman
perl -E '$t=<>;map$r=2*$r|1&$t>>$_,0..31;say$r'
sumber