Integer adalah biner-berat jika representasi binernya mengandung lebih 1
dari 0
s sementara mengabaikan nol terkemuka. Sebagai contoh 1 adalah biner-berat, karena representasi binernya sederhana 1
, namun 4 tidak berat biner, seperti representasi binernya 100
. Dalam hal terjadi pengikatan (misalnya 2, dengan representasi biner 10
), jumlahnya tidak dianggap sebagai biner-berat.
Diberikan bilangan bulat positif sebagai input, menghasilkan nilai kebenaran jika biner-berat, dan nilai falsey jika tidak.
Testcases
Format: input -> binary -> output
1 -> 1 -> True
2 -> 10 -> False
4 -> 100 -> False
5 -> 101 -> True
60 -> 111100 -> True
316 -> 100111100 -> True
632 -> 1001111000 -> False
2147483647 -> 1111111111111111111111111111111 -> True
2147483648 -> 10000000000000000000000000000000 -> False
Mencetak gol
Ini adalah kode-golf sehingga byte paling sedikit di setiap bahasa menang
code-golf
number
decision-problem
binary
Skidsdev
sumber
sumber
Jawaban:
Kode Mesin x86,
1514 byteIni adalah fungsi menggunakan konvensi panggilan panggil Microsoft___ (parameter pertama dan satu-satunya di ecx, nilai balik dalam eax, callee diizinkan untuk clobber edx), meskipun secara sepele dapat dimodifikasi untuk konvensi panggilan lain yang menyampaikan argumen dalam register.
Ini mengembalikan 255 sebagai benar, dan 0 sebagai falsey.
Ini menggunakan opcode tidak berdokumen (tapi banyak didukung)
salc
.Pembongkaran di bawah ini:
Cobalah online!
Terima kasih kepada Peter Cordes untuk menyarankan mengganti
lzcnt
denganbsr
.sumber
popcnt
sebelum menggulir ke bawah untuk melihat jawaban, tetapi tidak terpikirlzcnt
untuk berurusan dengan hanya angka signifikan seperti yang dipersyaratkan oleh pertanyaan.bsr
alih-alihlzcnt
(aliasrep bsr
)? Anda harus menggunakansub
sebagai gantilea
karena memberi Anda 32-lzcnt. (Atau membiarkan pertama tidak dimodifikasi untuk src = 0, pada semua perangkat keras Intel dan AMD yang ada. AMD bahkan mendokumentasikan perilaku ini, tetapi Intel mengatakan tidak terdefinisi ... Pokoknya, OP mengatakan positif , yang mengesampingkan0
.)popcnt
danbsr
, tapi itu 17 byte. Aku berpikir itu cukup bagus dibandingkan dengan jawaban pertama yang kulihat , tapilea
trik pintar ini mengalahkan itu. Saya juga melihat membandingkanbsf
danpopcnt
. Tetapi saya tidak melihat cara apa pun yang dapat mengalahkan solusi ini, bahkan dengan memperhitungkan 1 byte yang dapat Anda hemat dengan menjatuhkanrep
awalan.salc
tidak setara dengansetc al
: yang terakhir ditetapkanal
ke 1 jika CF ditetapkan, bukan ke 255.salc
adalahsbb al, al
, tetapi Anda mendapatkan penghematan 1 byte untuk menyandikannya. Omong-omong, ini didokumentasikan oleh AMD, dan secara luas didukung oleh Intel, dengan mnemonic bahkan berasal dari peta opcode P6 Intel. Jadi yang ini sebenarnya cukup aman untuk digunakan. Juga, perbaikan yang bagus di sini untuk berpikir untuk menggunakan instruksi itu! Ini pada dasarnya adalah apa konsep awal saya lakukan, kecuali (1) saya menggunakan kode x86-64, jadiinc
dua kali lebih lama untuk menyandikan, dan (2) saya tidak memikirkannyasalc
, jadi saya melakukan pekerjaan yang sama di sebuah jalan yang lebih panjang. Sayang sekali, saya hanya bisa memilih satu kali.Jelly , 5 byte
Menghasilkan output yang tidak kosong (benar) atau output kosong (salah).
Cobalah online!
Bagaimana itu bekerja
sumber
Bo-S
, tetapi saya tidak dapat menemukan atom 1-byte yang akan mengubah positif / non-positif menjadi kebenaran / kepalsuan ...Æṃ
itu tidak ada.Python 2 , 35 byte
Cobalah online!
Jawaban lama, 38 byte
Keluaran
0
sebagai palsu dan-2
atau-1
sebagai kebenaranCobalah online!
sumber
bin
penyebab masalah ini?max
kerjanya. Dalam hal seri, max akan mengembalikan nilai pertama di iterable yang memiliki nilai maksimal. Kode ini menggunakan fakta itu untuk memastikan bahwa 1 dikembalikan pada saat seri, yang sebenarnya berarti ada lebih banyak daripada nol, karena nol tambahan ditambahkan olehbin
. Ini sebenarnya akan salah ketika ditulis dengan cara ini jika bukan karena nol tambahan.cmp
pengembalian0
ketika keduanya samaOktaf , 18 byte
TIO tidak berfungsi karena kotak alat komunikasi tidak disertakan. Itu dapat diuji di Octave-Online .
Bagaimana ini bekerja:
de2bi
mengkonversi angka desimal ke vektor angka biner, bukan string sepertidec2bin
halnya.mode
mengembalikan digit paling sering dalam vektor. Ini default ke terendah dalam kasus seri.sumber
JavaScript (ES6),
3634 bytesumber
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0
selama 35 byte.n>>1
alih-alihn>>>1
untuk menyimpan byte karena input tidak pernah negatif.n/2|0
tidak lebih baik: /MATL , 3 byte
Cobalah online!
Saya tidak benar-benar tahu MATL, saya hanya memperhatikan bahwa
mode
bisa bekerja dalam jawaban oktaf alephalpha dan menemukan ada beberapa yang setara dalam MATL.sumber
Mathematica, 22 byte
Disimpan satu byte berkat @MartinEnder dan @JungHwanMin .
sumber
@@
.#>#2&@@#~DigitCount~2&
Brachylog , 6 byte
Cobalah online!
Penjelasan
Karena
ḃ
tidak akan pernah menyatukan outputnya dengan daftar angka dengan nol terkemuka, kita tahu bahwa kejadian1
akan selalu menjadi yang pertama dan kejadian0
akan selalu menjadi yang kedua setelahọ
.sumber
Python 3 ,
44(terima kasih @ c-mcavoy) 40 byteCobalah online!
sumber
C (gcc) ,
51484140 byteCobalah online!
sumber
unsigned
n>>=1
menjadin/=2
. Saya juga berpikir Anda dapat menggunakan~n
sebagai gantinyan^-1
, yang seharusnya juga memungkinkan Anda untuk berubah&&
ke&
n
, dan tidak pernah keberatan tentang mengubah&&
untuk&
, saya tidak berpikir bahwa akan bekerja. Tetapi mengubahnya*
tampaknya bekerja&&
hanya untuk menangani kasus yang tidak ditandatangani tetapi karena saya hanya perlu menangani bilangan bulat positif saya dapat menghapus semuanya bersama-sama. Pouint bagus tentang/=
menjadi lebih pendek>>=
, terima kasih!n&1?++i:--1
menjadii+=n%2*2-1
. Anda juga dapat menyingkirkannya>0
dengan menyatakan bahwa Anda akan menghasilkan nol untuk yang berat dan yang bukan nol untuk yang tidak beratR ,
545351 byte-1 byte terima kasih kepada Max Lawnboy
membaca dari stdin; kembali
TRUE
untuk angka-angka berat biner.d
adalah jumlah digit biner;sum(n%/%2^(0:d)%%2
menghitung jumlah digit (yaitu jumlah yang).Cobalah online!
sumber
log2(n)
alih-alihlog(n,2)
menyimpan 1 bytekode mesin x86_64,
232221 byteDibongkar:
Terima kasih @Ruslan, @PeterCordes untuk
-1
byte!Cobalah online!
sumber
8d 1f
bukan89 fb
?add eax, 2
+dec eax
, tetapi komentar Anda menyarankan Anda ingin menambahebx
, bukaneax
.jnz Next
/add
/dec
(7 byte) denganlea -1(%rax, %rbx, 2), %eax
(4 byte) yang harus dilakukaneax += 2*ebx - 1
(seperti pada jawaban kode mesin x86 lainnya ). Lalu di luar loop,neg %eax
(2 byte) sebelum menggeser bit tanda ke bawah. Penghematan bersih 1 byte. Atautest %eax,%eax
/setge %al
juga akan berfungsi, jika nilai pengembalian Anda adalah abool
atauint8_t
.lea -1(%rax,rbx,2)
tetapi hanyalea -1(%eax,%eax,2)
membuang-buang byte dengan cara ini .. Bagaimanapun, Anda berdua benar, saya dapat menyimpan byte seperti ini. Terima kasih banyak (sebagai imbalannya saya akan mengubahnyalea
untukmov
sementara waktu saya melakukannya)!Perl 6 ,
3230 byteMenguji
Menguji
Diperluas:
sumber
Bijaksana ,
4039 byteCobalah online!
Penjelasan
sumber
Haskell,
4134Jika
n
aneh, ambil a-1
jika itu genap, ambil a1
. Tambahkan panggilan rekursif dengann/2
dan hentikan jikan = 0
. Jika hasilnya kurang dari0
angka itu biner-berat.Cobalah online!
Sunting: @ Ørjan Johansen menemukan beberapa pintasan dan menyimpan 7 byte. Terima kasih!
sumber
mod n 2
bisa sajan
, dan itu satu byte lebih pendek tanpa akumulator. Cobalah online!Retina ,
3734 byteCobalah online! Tautan mencakup test case yang lebih kecil (yang lebih besar mungkin akan kehabisan memori). Sunting: Disimpan 3 byte berkat @MartinEnder. Penjelasan: Tahap pertama mengkonversi dari desimal ke unary, dan dua tahap berikutnya mengkonversi dari unary ke binary (ini hampir langsung keluar dari halaman aritmatika unary di wiki Retina, kecuali bahwa saya menggunakan
@
alih-alih0
). Tahap ketiga mencari pasangan karakter yang berbeda, yang bisa berupa@1
atau1@
, dan menghapusnya sampai tidak ada yang tersisa. Tahap terakhir kemudian memeriksa sisa 1s.sumber
${1}
bisa$+
. Atau Anda bisa menggunakan dan!
bukannya0
menyingkat01|10
menjadi.\b.
.$+
melakukan hal yang benar ketika polanya berisi a|
? Saya bertanya-tanya apakah saya bisa menggunakan itu sebelumnya ...$+
itu super bodoh dan hanya menggunakan grup dengan jumlah terbesar, apakah itu digunakan atau tidak. Ini hanya berguna untuk bermain golf ketika Anda memiliki lebih dari sembilan grup atau dalam situasi seperti yang ada di sini, dan saya tidak tahu mengapa saya pernah menggunakannya dalam regex produksi.R , 43 byte
Cobalah online!
sumber
intToBits
Kotlin , 50 byte
Lambda dari tipe implisit
(Int) -> Boolean
. Versi 1.1 dan lebih tinggi hanya karena penggunaanInt.toString(radix: Int)
.Sayangnya runtime Kotio TIO tampaknya 1,0.x, jadi inilah anjing yang sedih alih-alih tautan TIO:
sumber
Pyth,
97 byteCoba di sini.
-2 Terima kasih kepada FryAmTheEggman .
sumber
>ysJjQ2lJ
.B
!)R,
3937 byteIni adalah kombinasi dari metode yang digunakan oleh @MickyT dan @Giuseppe, menghemat beberapa byte lagi.
sum(intToBits(x) > 0)
menghitung jumlah1
bit, dan2+log2(x)/2
setengah dari jumlah total bit, ketika dibulatkan ke bawah. Kami tidak harus membulatkan karena perilaku ketika kedua nilai tersebut sama.sumber
C # (.NET Core) ,
62, 49 byteTanpa LINQ.
EDIT: dana dengan -13 byte golf mengubah sementara ke rekursif dan mengembalikan bool, bukan bilangan bulat.
Cobalah online!
sumber
Regex (ECMAScript),
857371 byteCobalah online!
penjelasan oleh Deadcode
Versi 73 byte sebelumnya dijelaskan di bawah ini.
^((?=(x*?)\2(\2{4})+$)\2|(?=(x*?)(\4\4xx)*$)(\4|\5(x*)\7\7(?=\4\7$)\B))+$
Karena keterbatasan regex ECMAScript, taktik yang efektif sering kali untuk mengubah langkah nomor satu sekaligus menjaga properti yang dibutuhkan tidak berubah-ubah pada setiap langkah. Misalnya, untuk menguji kuadrat sempurna atau kekuatan 2, kurangi jumlahnya dalam ukuran sekaligus pertahankan kuadrat atau kekuatan 2 (masing-masing) di setiap langkah.
Inilah yang dilakukan solusi ini di setiap langkah:
1
1
1
10
01
01
Ketika langkah-langkah yang diulang ini tidak dapat melangkah lebih jauh, hasil akhirnya akan berupa string
1
bit yang berdekatan , yang berat, dan menunjukkan bahwa angka asli juga berat, atau kekuatan 2, yang menunjukkan bahwa angka asli tidak berat.Dan tentu saja, meskipun langkah-langkah ini dijelaskan di atas dalam hal manipulasi tipografi pada representasi angka biner, mereka sebenarnya diimplementasikan sebagai aritmatika unary.
sumber
\5
selanjutnya dimatikan satu per satu). Saya telah mempelajari ini dan menjelaskan serta berkomentar dalam jawaban saya (karena StackExchange tidak mengizinkan balasan multiline).Regex (ECMAScript), 183 byte
Ini adalah masalah lain yang menarik untuk dipecahkan dengan regex ECMA. Cara "jelas" untuk menangani ini adalah dengan menghitung jumlah
1
bit dan membandingkannya dengan jumlah total bit. Tetapi Anda tidak dapat secara langsung menghitung hal-hal dalam ECMAScript regex - kurangnya referensi-balik yang persisten berarti bahwa hanya satu angka yang dapat dimodifikasi dalam satu lingkaran, dan pada setiap langkah hanya dapat dikurangi.Algoritma unary ini berfungsi sebagai berikut:
1
bit ke posisi paling tidak signifikan di mana ada0
bit. Masing-masing langkah ini adalah pengurangan. Pada akhir loop, angka yang tersisa (karena akan diwakili dalam biner) adalah string1
s tanpa0
s. Operasi-operasi ini sebenarnya dilakukan secara unary; itu hanya secara konseptual bahwa mereka dilakukan dalam biner.1
s" ini dengan akar kuadrat yang diperoleh sebelumnya. Jika akar kuadrat harus dibulatkan, gunakan versi yang berlipat ganda. Ini memastikan bahwa "string biner1
s" harus memiliki lebih dari setengah digit biner sebanyak N agar ada pertandingan final.Untuk mendapatkan akar kuadrat, varian dari algoritma multiplikasi dijelaskan secara singkat dalam posting regex nomor Rocco saya digunakan. Untuk mengidentifikasi
0
bit paling tidak signifikan , algoritma pembagian yang dijelaskan secara singkat dalam pos faktor nomor regex saya digunakan. Ini adalah spoiler . Jadi jangan membaca lebih jauh jika Anda tidak ingin beberapa sihir regex unary canggih dimanjakan untuk Anda . Jika Anda memang ingin mencoba sendiri keajaiban ini, saya sangat menyarankan memulai dengan memecahkan beberapa masalah dalam daftar masalah yang direkomendasikan secara spoiler-tag pada posting sebelumnya , dan mencoba untuk menemukan wawasan matematika secara mandiri.Tanpa basa-basi lagi, regex:
^(?=.*?(?!(x(xx)+)\1*$)(x)*?(x(x*))(?=(\4*)\5+$)\4*$\6)(?=(((?=(x(x+)(?=\10$))*(x*))(?!.*$\11)(?=(x*)(?=(x\12)*$)(?=\11+$)\11\12+$)(?=.*?(?!(x(xx)+)\14*$)\13(x*))\16)*))\7\4(.*$\3|\4)
Cobalah online!
sumber
Jelly , 6 byte
Cobalah online!
sumber
Bo-S
dapat digunakan untuk menghitung "bobot" biner dari input, sayangnya cara terpendek untuk menggunakan yang tampaknyaBo-S>0
...Ḷ
bekerja: PJ , 12 byte
J mengeksekusi kata kerja kanan-ke-kiri, jadi mari kita mulai dari akhir dan bekerja menuju awal.
Penjelasan
sumber
(#<2*+/)@#:
harus menyimpan 1 kecuali saya kehilangan sesuatu.Julia, 22 byte
sumber
Oktaf , 26 byte
Cobalah online!
sumber
mode(dec2bin(a)-48)
PHP , 44 byte
Cobalah online!
PHP , 48 byte
Cobalah online!
sumber
Python 2 , 44 byte
Cobalah online!
Jawaban Lama, 47 byte
Ini hanyalah port dari jawaban C @ cleblanc . Ini lebih panjang daripada jawaban Python lainnya, tetapi saya pikir itu layak dikirim karena merupakan metode yang sama sekali berbeda untuk menemukan jawabannya.
Cobalah online!
sumber
C #, 82 byte
sumber
n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
Convert
dan termasukusing System.Linq;
(ditulis lebih pendek darinamespace System.Linq{}
). Ide bagus hanya tidak cukup untuk menjamin penghematan dalam kasus ini.