Tujuan
Dengan bilangan bulat non-negatif, buat fungsi yang mengembalikan posisi awal jumlah 1 terbesar berturut-turut dalam nilai biner bilangan bulat itu.
Saat diberi input 0
, kembali 0
.
Jika angka memiliki beberapa goresan dengan panjang yang sama, Anda harus mengembalikan posisi goresan terakhir.
Memasukkan
Integer lebih besar dari atau sama dengan 0.
Keluaran
Bilangan bulat dihitung seperti dijelaskan di bawah ini.
Aturan
- Ini adalah kode-golf, jadi kode terpendek dalam byte di setiap bahasa menang.
- Celah standar dilarang.
Contoh dan Kasus Uji
Contoh 1
- Fungsi Anda melewati bilangan bulat 142
- 142 sama dengan 10001110 dalam biner
- Coretan terpanjang adalah "111" (coretan tiga yang)
- Garis mulai pada posisi 2 ^ 1
- Fungsi Anda mengembalikan 1 sebagai hasilnya
Contoh 2
- Fungsi Anda melewati integer 48
- 48 sama dengan 110000 dalam biner
- Coretan terpanjang adalah "11" (coretan dua yang)
- Garis mulai pada posisi 2 ^ 4
- Fungsi Anda mengembalikan 4 sebagai hasilnya
Contoh 3
- Fungsi Anda melewati bilangan bulat 750
- 750 sama dengan 1011101110 dalam biner
- Coretan terpanjang adalah "111" (coretan tiga yang)
- Karena ada dua garis dengan panjang yang sama, kami mengembalikan garis selanjutnya.
- Coretan selanjutnya dimulai pada posisi 2 ^ 5
- Fungsi Anda mengembalikan 5 sebagai hasilnya
0
. Itu adalah ujian penting.Jawaban:
Jelly ,
108 byteCobalah online!
Bagaimana itu bekerja
sumber
JavaScript (ES6),
41403634 byteDisimpan 4 byte berkat @ThePirateBay
Uji kasus
Tampilkan cuplikan kode
Bagaimana?
Kasus umum x> 0
Kami secara rekursif DAN input x dengan x / 2 yang secara progresif mengurangi pola bit set berurutan hingga hanya bit paling kanan dari urutan yang tersisa. Kami menyimpan salinan dari nilai non-nol terakhir dan menentukan posisi bit paling signifikan dengan membulatkan logaritma basis-2.
Berikut adalah langkah-langkah yang kami lalui untuk x = 750 ( 1011101110 dalam biner).
Kasing tepi x = 0
Kasus khusus
x = 0
segera mengarah keMath.log2(0) | 0
. Logaritma dari0
evaluasi ke-Infinity
dan bitwise biner ATAU memaksa pemaksaan ke bilangan bulat 32-bit. Sesuai dengan spesifikasi operasi abstrak ToInt32 , ini memberikan yang diharapkan0
:sumber
0
, yang merupakan bagian dari rentang input.Math.log2(k)|0
sebaliknya31-Math.clz32(k)
? Atau apakah saya melewatkan sesuatu?Math.log2(k)|0
sebenarnya lebih pendek dan lebih sederhana untuk kasus khususx=0
. Terima kasih. :)kode mesin x86, 14 byte
Menggunakan @ algoritma Arnauld ini dari
x &= x>>1
dan mengambil set posisi bit tertinggi pada langkah sebelumnyax
menjadi0
.Dipanggil dari C / C ++ dengan tanda tangan
unsigned longest_set(unsigned edi);
di Sistem V86 ABI x86-64. Byte kode mesin yang sama akan mendekode dengan cara yang sama dalam mode 32-bit, tetapi konvensi pemanggilan standar 32-bit tidak memasukkan arg pertamaedi
. (Mengubah register input keecx
atauedx
untuk Windows_fastcall
/_vectorcall
ataugcc -mregparm
dapat dilakukan tanpa merusak apa pun.)BSR
Instruksi x86 (Bit Scan Reverse) sangat cocok untuk ini, memberikan kami indeks-bit secara langsung, daripada menghitung angka nol di depan. (bsr
tidak secara langsung menghasilkan 0 untuk input = 0 seperti32-lzcnt(x)
akan, tetapi kita perlu bsr = 31-lzcnt untuk input non-nol, jadilzcnt
bahkan tidak akan menyimpan instruksi, apalagi jumlah byte. Mem-kosongkan eax sebelum loop bekerja karenabsr
' perilaku setengah resmi meninggalkan tujuan tidak dimodifikasi ketika inputnya nol.)Ini akan menjadi lebih pendek jika kita dapat mengembalikan posisi MSB dari perjalanan terpanjang. Dalam hal ini,
lea ecx, [rdi+rdi]
(3 byte) akan menyalin + kiri- alih alih-alihmov
+shr
(4 byte).Lihat tautan TIO ini untuk pemanggil asm yang melakukannya
exit(longest_set(argc-1));
Pengujian dengan loop shell:
sumber
Jelly ,
191711 byteCobalah online!
-6 (!) Byte berkat pengamatan tajam @ Dennis
Bagaimana itu bekerja
sumber
0
, yang ada dalam rentang input.ȯ-µ...
B
selalu mengembalikan array yang dimulai dengan 1 ,BUṪMṪ’×Ṡ
bisa menjadiṪBL’
. Juga, Anda tidak perluḞ
, danḟ0
menyimpan satu byte lebih¹Ðf
.Python 2 , 45 byte
Cobalah online!
Menyimpan banyak byte berkat Dennis! (Kepala untuk
len(bin(...))-3
bukannyamath.frexp
)Terima kasih kepada @xnor karena menemukan bug, yang untungnya mudah diperbaiki!
sumber
x=3
, saya kira karenaand/or
sirkuit pendek salah ketika fungsi mengembalikan 0.Perl 6 ,
4535 byteVersi yang sangat ditingkatkan ini adalah milik @nwellnhof.
Cobalah online!
sumber
:g
untuk mendapatkan semua kecocokan. Dengan operator pertandingan-pintar, saya dapat menurunkannya hingga 40 byte:{sort(.base(2).flip~~m:g/1+/).tail.from}
{.msb+1-(.base(2)~~m:g/1+/).max.to}
:g
dan tidak tahu bagaimana saya bisa menggunakan kata keterangan dengan operator smartmatch. Juga.msb
metode ini sangat membantu di sini dan saya tidak tahu sebelumnya.Python 2 ,
8978 byteCobalah online!
EDIT: Disimpan 11 byte berkat Tn. Xcoder.
sumber
05AB1E ,
141211 byteCobalah online! atau menjalankan test case .
Penjelasan
sumber
J ,
1817 byteCobalah online!
Penjelasan
sumber
x
angka dua semuanya 0 dan 1, apa artinya itu? Nomor basis 2 memiliki digit0
dan1
, jadi1
nomor dasar memiliki digit ...0
? lalu apa1
artinya dalam konteks itu? Dan apakah angka dasar0
selalu0
?x #. y
penghitungan pertamaw =: */\. }. x , 1
kemudian kembali+/ w * y
#.
, karena Anda lebih mengandalkan detail implementasi internal daripada api publik?C # (.NET Core) ,
6460 byteCobalah online!
Versi AC # dari jawaban @ Arnauld
Ucapan Terima Kasih
4 byte disimpan berkat Kevin Cruijssen.
C # (.NET Core) ,
131123 + 18 = 141 byteCobalah online!
+18 byte untuk
using System.Linq;
Ucapan Terima Kasih
8 byte disimpan berkat Grzegorz Puławski.
Merosot
C # (.NET Core) ,
164161 byteCobalah online!
Sebuah non-
Linq
solusi , yang saya yakin dapat ditingkatkan, meskipun tidak ada yang langsung terlihat.Merosot
sumber
r
memasukkan jawaban pertama: tio.run/##dY9RS8MwFIWfza/…T=a=>{int x=(int)Math.Log(a,2);return(a&=a/2)>0?T(a):x<0?0:x;}
T=a=>(a&a/2)>0?T(a&a/2):Math.Log(a,2)<0?0:(int)Math.Log(a,2)
Sekam , 12 byte
Cobalah online!
Penjelasan
sumber
Jelly ,
14 13 1211 byteTautan monadik yang mengambil dan mengembalikan bilangan bulat non-negatif.
Cobalah online! atau lihat test-suite .
Bagaimana?
sumber
ŒrṪP
pada awalan sebagai gantinya.Jelly , 19 byte
Cobalah online!
Terima kasih kepada Jonathan Allan karena telah menghemat
46 byte!Saya telah bekerja terlalu banyak untuk meninggalkan ini, meskipun agak lama. Saya benar-benar ingin menambahkan solusi yang benar-benar mencari substring terpanjang
1
dalam representasi biner ...Penjelasan
sumber
BŒgḄṀB
sebaliknyaBwÇɓÇL+ɓBL_‘
Kotlin , 77 byte
Yg diperindahkan
Uji
sumber
Haskell ,
101989675 byteCobalah online! Penggunaan:
snd.maximum.(`zip`[0..]).c $ 142
hasil1
.Penjelasan:
c
mengubah input menjadi biner sementara pada saat yang sama menghitung panjang goresan satu, mengumpulkan hasilnya dalam daftar.r<-c$div n 2
rekursif menghitung sisar
daftar ini, sambilsum[r!!0+1|mod n 2>0]:r
menambahkan panjang beruntun saat ini ker
. Pemahaman daftar memeriksa apakahmod n 2>0
, yaitu apakah digit biner saat ini adalah satu, dan jika demikian, mengambil panjang dari garis sebelumnya (elemen pertamar
) dan menambahkannya. Kalau tidak, pemahaman daftar kosong, dansum[]
menghasilkan0
. Sebagai input contoh,c 142
menghasilkan daftar[0,3,2,1,0,0,0,1,0]
.(`zip`[0..])
menambahkan posisi ke setiap elemen dari daftar sebelumnya sebagai komponen kedua tupel. Sebagai contoh ini memberi[(0,0),(3,1),(2,2),(1,3),(0,4),(0,5),(0,6),(1,7),(0,8)]
.maximum
menemukan tupel maksimal leksikografis dalam daftar ini, yaitu panjang garis dianggap pertama karena mereka adalah komponen pertama, dan jika terjadi ikatan komponen kedua, yaitu indeks yang lebih besar, memutuskan. Ini menghasilkan(3,1)
dalam contoh, dansnd
mengembalikan komponen kedua dari tupel.sumber
Python 2 atau 3 , 58 byte
Cobalah online!
sumber
C (gcc) ,
8180 byteCobalah online!
C (gcc) , 43 byte
Versi AC dari jawaban @ Arnauld
Cobalah online!
sumber
n<1?0:log2(n)
alih-alih(k=log2(n))<0?0:k
MS SQL Server,
437426407398 byteSQL Fiddle
Saya yakin bahwa saya bisa menghapus jeda baris, dll, tapi ini kompak seperti yang saya inginkan:
Ini versi yang lebih mudah dibaca:
Trik sebenarnya adalah sejauh yang saya bisa temukan, tidak ada fungsi SQL asli untuk mengubah angka dari desimal menjadi biner. Akibatnya, saya harus mengkodekan konversi ke biner secara manual, kemudian saya dapat membandingkannya sebagai string, satu karakter pada satu waktu sampai saya menemukan nomor yang tepat.
Saya yakin ada cara yang lebih baik untuk melakukan ini, tapi saya tidak melihat (n) jawaban SQL, jadi saya pikir saya akan membuangnya di sana.
sumber
APL (Dyalog Unicode) , 22 karakter = 53 byte
Membutuhkan
⎕IO←0
yang default pada banyak sistem.Cobalah online!
⎕
meminta input⊢
hasilkan itu (terpisah¯1
dari⎕
)2⊥⍣¯1
konversikan ke basis-2, menggunakan posisi sebanyak yang diperlukanb←
simpan sebagaib
(untuk b inary)⌽
membalikkan(
...)
tandai posisi awal sebagai berikut:⊆⍨b
partisi sendirib
(yaitu 1-coretanb
)↑
campur (buat daftar daftar menjadi matriks, diisi dengan nol)∨⌿
pengurangan OR vertikal (menghasilkan goresan terpanjang)⍸
d ndices posisi awal⌽
membalikkan⊃
pilih yang pertama (hasilkan nol jika tidak ada yang tersedia)sumber
MATL , 15 byte
Cobalah online!
Gunakan separuh dan ide AND. Yang
k
diperlukan hanya untuk membuatnya berakhir1
- karena alasan tertentu, 1 DAN 0,5 mengembalikan 1, menyebabkan loop tak terbatas.(solusi alternatif:
BtnwY'tYswb*&X>)-
dengan mengkonversi ke pengkodean biner dan run-length)sumber
Google Sheets, 94 byte
Tidak, tidak terlalu cantik. Sungguh menyenangkan bisa menyimpan
Dec2Bin(A1)
sebagai variabel untuk referensi.Poin utama: Seperti Excel,
Dec2Bin
fungsi ini memiliki nilai input maksimal511
. Apa pun yang lebih besar dari itu akan mengembalikan kesalahan, seperti yang terlihat di bawah ini.sumber
R, 117 Bytes
sumber
rev
, gunakanReduce(...,T,T)
untuk menumpuk dari kanan (beralihx,y
dalam definisi fungsi). Kemudian gunakan1+max(z)-which.max(z)
karena hasilnya agak berbeda. Gunakan"if"
daripada"ifelse"
karena kita tidak perlu vektorisasi; aaand jika Anda menggunakanany(z)
alih-alih!sum(z)
Anda menjatuhkan byte.Excel VBA,
5444 Bytes-10 Bytes berkat @EngineerToast
Fungsi jendela langsung VBE anonim yang mengambil input dari jarak
[A1]
dan keluaran ke jendela langsung VBEsumber
C1
masih ada di sana alih-alihA1
, saya pikir Anda dapat menampilkanInstr
hasilnya secara langsung dengan sedikit memutar untuk koreksi input nol:?Instr(1,StrReverse([Dec2Bin(A1)]),1)+([A1]>0)
(46 byte). Benar = -1 karena ... VBA.>0
ke[A1]
notasiAPL (Dyalog Classic) ,
2421 byteCobalah online!
sumber
Pyth , 17 byte
Ini adalah fungsi rekursif. Tautan ini termasuk
y
untuk memanggil fungsi pada input yang diberikan.Verifikasi semua kasus uji.
Pyth , 20 byte
Verifikasi semua kasus uji.
sumber
R, 66 Bytes
Penjelasan:
sumber
a$l
bukannyaa[[1]]
dana$v
bukannyaa[[2]]
untuk menyimpan beberapa byte :), dan>0
bukannya==1
.Python 2 , 41 byte
Cobalah online!
Berdasarkan solusi ini oleh Mr. Xcoder .
sumber
Javascript, 54 karakter
i.toString(2)
mendapat string biner untuk integer..split(0)
mendapat masing-masing orang bagian berurutan dalam elemen array..sort().reverse()
memberi kita nilai tertinggi sebagai yang pertama.[0].length
memberi kita panjang yang nilai pertama.sumber
the starting position of number of largest consecutive 1's
Perl 5, 45 + 1 (-p)
Jika Anda menulis ini di baris perintah sebagian besar shell, Anda mungkin harus mengetik ini sebagai:
Tarian kutipan di akhir hanya untuk mendapatkan perl melihat a
'
, yang seharusnya dikonsumsi oleh shell.sumber
Retina ,
5243 byteKonversikan ke biner, lalu ganti dengan panjang dari apa yang mengikuti string terbesar.
Coba online - semua test case
Disimpan 9 byte berkat Martin.
sumber
$+
untuk${1}
. Tetapi Anda dapat menyimpan lebih banyak lagi dengan mengganti tahap terakhir dengan sekelompok tahapan seperti ini: tio.run/##K0otycxL/K/…${1}
disalin dari tutorial Anda di Github.