Urutan Kurva naga

23

The urut kurva naga (atau biasa kertas urutan lipat) adalah urutan biner. a(n)diberikan oleh negasi dari bit kiri dari 1 paling tidak signifikan n. Sebagai contoh untuk menghitung, a(2136)pertama-tama kita mengkonversi ke biner:

100001011000

Kami menemukan bagian terkecil kami

100001011000
        ^

Ambil bit ke kiri

100001011000
       ^

Dan kembalikan negasinya

0

Tugas

Diberikan bilangan bulat positif sebagai input, output a(n). (Anda dapat menampilkan dengan integer atau boolean). Anda harus berusaha membuat kode sekecil mungkin yang diukur dengan byte.

Uji Kasus

Berikut adalah 100 entri pertama secara berurutan

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1
Wisaya Gandum
sumber
9
Sedikit yang paling tidak signifikan 100001011000adalah a 0. Apakah maksud Anda yang paling tidak penting 1?
bubar

Jawaban:

16

Mathematica 25 Bytes

1/2+JacobiSymbol[-1,#]/2&

Cara lain untuk melakukan ini:

56 byte

(v:=1-IntegerDigits[#,2,i][[1]];For[i=1,v>0,i++];i++;v)&

58 byte

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Kelly Lowder
sumber
3
Wow! Sebuah jawaban matematika dan itu tidak dibangun hanya. Selamat menikmati!
KeyWeeUsr
2
Satu-satunya hal yang dapat membuat jawaban ini lebih baik adalah penjelasan mengapa dan bagaimana cara kerjanya. : P
Martin Ender
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf Lihat komentar setelah Contoh 13.
alephalpha
7

Python 3 , 22 21 byte

1 byte berkat produk ETH.

lambda n:n&2*(n&-n)<1

Cobalah online!

Ftw aritmatika bitwise.

Biarawati Bocor
sumber
2
"Anda dapat menampilkan dengan integer atau dengan boolean" jadi saya kira Anda tidak perlu 0+(...)?
Martin Ender
Urutan operasi di sini benar-benar membingungkan saya. Bisa n&1dimasukkan ke dalam tanda kurung? Atau apakah 1+(n^~-n)<1itu bisa dimasukkan ke dalam tanda kurung? Atau apakah itu 1+(n^~-n)...
ETHproduksi
oh tuhan apa. inilah yang saya cari: o bagus!
HyperNeutrino
&memiliki prioritas lebih rendah, jadi1+(n^~-n)
Leaky Nun
Ah, temukan tabel diutamakan. Sekarang semuanya masuk akal: P
ETHproduksi
6

Retina ,38 34 29 byte

\d+
$*
+`^(1+)\1$|1111
$1
^1$

Cobalah online!

Martin dan Leaky pada dasarnya datang dengan ide ini, untuk 5 byte lagi!

Mengubah input menjadi unary, dan kemudian secara progresif membagi angka dengan 2. Setelah itu tidak dapat melakukan hal itu secara merata lagi (yaitu angkanya ganjil), maka ia akan menghilangkan tambalan 4 dari input, menghitung hasil dari mod operasi terakhir 4 Akhirnya, ini memeriksa jika hasilnya adalah 1, yang berarti digit di sebelah kiri dari bit 1 yang paling signifikan adalah nol. Jika itu benar, hasil akhirnya adalah 1, jika tidak maka nol.

FryAmTheEggman
sumber
31 byte (haruskah saya mempostingnya sendiri?)
Leaky Nun
Saya menemukan cara untuk menghindari konversi biner penuh dan sebagai gantinya hanya membagi faktor 2 dan memeriksa kesetaraan dengan 1 (mod 4): tio.run/##K0otycxL/…
Martin Ender
@ MartinEnder pada dasarnya algoritma saya ... dengan 2 byte off
Leaky Nun
@ LeakyNun Oh ya, mereka berdua ide yang sama. Pikiran dan hal-hal hebat ...;)
Martin Ender
Saya akan mengeditnya, tetapi jika salah satu dari Anda ingin mempostingnya, saya akan kembali, karena saya mungkin tidak akan memikirkannya sendiri;)
FryAmTheEggman
6

Jeli , 5 byte

&N&HṆ

Cobalah online!

Bagaimana itu bekerja

&N&HṆ  Main link. Argument: n

 N     Negate; yield -n.
&      Bitwise AND; compute n&-n.
       This yields the highest power of 2 that divides n evenly.
   H   Halve; yield n/2.
  &    Bitwise AND; compute n&-n&n/2. This rounds n/2 down if n is odd.
    Ṇ  Take the logical NOT of the result.
Dennis
sumber
4

Alice , 8 byte

I2z1xnO@

Cobalah online!

Mengambil input sebagai titik kode karakter Unicode dan mengeluarkan hasilnya sebagai byte 0x00 atau 0x01.

Untuk pengujian, berikut adalah versi I / O desimal pada 12 byte yang menggunakan algoritma yang sama persis (hanya I / O yang berbeda):

/o
\i@/2z1xn

Cobalah online!

Jika Alice adalah bahasa golf dan tidak memerlukan I / O dan penghentian program secara eksplisit, ini hanya akan memakan waktu 5 byte (2z1xn ) mengalahkan 05AB1E dan Jelly.

Penjelasan

I    Read input.
2z   Drop all factors of 2 from the input, i.e. divide it by 2 as long
     as its even. This shifts the binary representation to the right
     until there are no more trailing zeros.
1x   Extract the second-least significant bit.
n    Negate it.
O    Output it.
@    Terminate the program.
Martin Ender
sumber
3

Bijaksana , 28 20 16 byte

::-~^~-&:[?>]~-^

Cobalah online!

Penjelasan

Ini adalah port jawaban Python Leaky Nun. Sayangnya itu tidak bekerja pada TIO karena versi TIO dari interpreter agak ketinggalan jaman.

Kita mulai dengan membuat 3 salinan dari input kita dengan ::, kita kemudian mengurangi salinan atas dengan 1. Ini akan membalik semua bit sampai yang pertama. Kita lalu xor ini dengan salinan lain dari input kita. Karena semua bit hingga 1 pertama pada input kami telah dibalik, ini akan menghasilkan semua bit tersebut menjadi 1 pada hasilnya. Jika kemudian kita tambahkan satu ~-ke hasil, kita akan mendapatkan satu 1 di tempat di sebelah kiri dari kita paling tidak signifikan 1. Kita DAN ini dengan input untuk mendapatkan bit dari input. Sekarang kita akan memiliki 0iff bit itu mati dan kekuatan 2 iff bit itu menyala, kita bisa mengubahnya menjadi satu 1atau 0dengan :[?>]. Setelah ini dilakukan, kita hanya perlu meniadakan bit ~-^dan kita selesai.

Wisaya Gandum
sumber
3

Haskell , 45 43 39 byte

6 byte disimpan berkat nimi

f x|d<-div x 2=[f d,mod(1+d)2]!!mod x 2

Cobalah online!

Wisaya Gandum
sumber
Anda bisa menggunakan divbukan quot.
nimi
Bahkan lebih baik: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
Nimi
@nimi Saya bahkan tidak mengerti cara kerjanya. Anda mungkin harus mempostingnya sendiri.
Wheat Wizard
Ini masih algoritma yang sama, tetapi hanya cara yang berbeda untuk memilih cabang (secara rekursif panggil f lagi vs kasus dasar), jadi jangan ragu untuk mengeditnya. Ini |(d,m)<-divMod x 2adalah penjaga pola untuk diikat dke div x 2dan mke mod x 2. Kami menggunakan muntuk mengindeks daftar dua elemen [...,...]!!m. Dalam kasus m==0kami kembali mod(1+d)2dan dalam kasus m==1 f d.
nimi
1
Oh, maaf, Anda harus membalik elemen daftar: [f d,mod(1+d)2]. Cobalah online! .
nimi
3

x86 Kode Mesin, 17 16 15 byte:

Mengasumsikan ABI di mana parameter didorong pada tumpukan dan nilai kembali ada di ALregister.

8B 44 24 04 0F BC C8 41 0F BB C8 0F 93 C0 C3

Ini dibongkar sebagai berikut:

_dragoncurve:
  00000000: 8B 44 24 04        mov         eax,dword ptr [esp+4]
  00000004: 0F BC C8           bsf         ecx,eax
  00000007: 41                 inc         ecx
  00000008: 0F BB C8           btc         eax,ecx
  0000000B: 0F 93 C0           setae       al
  0000000E: C3                 ret
Govind Parmar
sumber
1
@ PeterTaylor Saya menghitung ukuran instruksi CPU dalam byte untuk jawaban saya; itu adalah praktik yang cukup umum di PPCG untuk jawaban perakitan.
Govind Parmar
1
Saya tidak bisa mengatakan seberapa umum itu, tetapi itu pasti salah
Peter Taylor
1
Bukan hanya bertele-tele, tapi juga tidak ada artinya. Tidak ada perbedaan antara "kode mesin" dan "kode perakitan" sejauh menyangkut komputer. Perbedaannya hanyalah salah satu interpretasi. Kami menetapkan mnemonik ke byte kode mesin agar lebih mudah dibaca manusia. Dengan kata lain, kita ungolf byte untuk membuatnya lebih mudah dimengerti.
Cody Grey
3
Itu tidak relevan, @Peter. Kode perakitan hanyalah terjemahan kode mesin yang dapat dibaca manusia. Mereka persis bahasa yang sama, hanya dalam dua bentuk / representasi yang berbeda. Tidak ada bedanya dengan TI BASIC, di mana secara umum diterima bahwa kita menghitung token , daripada byte karakter, karena ini adalah bagaimana sistem menyimpannya secara internal. Hal yang sama akan berlaku dengan bahasa assembly: mnemonics instruksi tidak disimpan sebagai karakter individu, melainkan direpresentasikan sebagai byte kode mesin yang setara.
Cody Grey
2
Selain itu, secara praktis, mengapa ada orang yang memasuki mnemonik bahasa rakitan yang diperluas dalam kompetisi kode-golf, ketika mereka dapat menerjemahkannya ke dalam kode mesin setara 100%, di mana entri dijamin lebih pendek secara gratis? Itu saja membuat perbedaan antara keduanya tidak ada gunanya, jika tidak sepenuhnya absurd.
Cody Grey
3

JavaScript (ES6), 17 14 byte

f=
n=>!(n&-n&n/2)
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Sunting: Disimpan 3 byte dengan mengirimkan jawaban @ Dennis ketika saya perhatikan bahwa output boolean dapat diterima.

Neil
sumber
3

C (gcc) , 20 byte

f(n){n=!(n&-n&n/2);}

Cobalah online!

Dennis
sumber
Ini sebenarnya tidak "bekerja"; Anda mengandalkan quirk dari generator kode untuk satu versi tertentu dari kompiler yang menargetkan satu arsitektur tertentu, di mana perhitungan menengah dilakukan dalam register yang sama yang digunakan untuk nilai pengembalian. Mengaktifkan semua jenis optimasi, mengubah arsitektur target, atau menggunakan versi GCC yang berbeda akan menghentikannya. Anda mungkin juga hanya mengatakan "sampah di tumpukan saya berisi output yang tepat ketika ada bulan purnama pada 13 Oktober".
Cody Grey
Sementara semua yang Anda katakan adalah benar dan kode seperti ini tidak pernah digunakan dalam kode produksi, kami mendefinisikan bahasa dengan penerapannya untuk tujuan golf kode. Tanpa bendera tambahan, ini berfungsi di semua versi terbaru gcc dan tcc, dan hanya perlu bekerja dalam satu versi agar dianggap valid.
Dennis
"Kami mendefinisikan bahasa dengan penerapannya untuk tujuan golf kode" Tunggu, apa? Jadi setiap flag kompiler dan setiap versi GCC mendefinisikan bahasa yang berbeda? Anda sadar itu gila, bukan? Standar bahasa C adalah apa yang mendefinisikan bahasa.
Cody Grey
Tidak disini. Jika ada standar C tetapi tidak ada implementasi, kami bahkan tidak akan menganggapnya sebagai bahasa. Seperti yang saya katakan sebelumnya, kompiler mendefinisikan bahasa . Akibatnya, mengandalkan perilaku yang tidak terdefinisi diperbolehkan . Set flag yang berbeda tidak dianggap bahasa yang berbeda, tetapi kecuali jika Anda menambahkannya ke jumlah byte Anda, semua jawaban menggunakan flag kompilasi standar.
Dennis
Wow. Itu gila. Maksud saya, saya bisa mengerti jika Anda mengatakan bahwa perilaku yang ditentukan implementasi diizinkan, tetapi perilaku yang tidak terdefinisi tidak didefinisikan didefinisikan oleh implementasi. Secara harfiah tidak terdefinisi. Implementasi diperbolehkan untuk melakukan hal-hal acak setiap kali. Dan gagasan "flag kompilasi standar" ini adalah sesuatu yang baru saja Anda temukan. Bendera kompilasi standar saya menyertakan beberapa yang merusak kode Anda. Dan saya pikir pengoptimal itu tidak standar. Yah, jelas situs ini bukan untuk saya.
Cody Grey
3

INTERCAL , 50 byte

DOWRITEIN.1DO.1<-!?1~.1'~#1DOREADOUT.1PLEASEGIVEUP

Operator INTERCAL unary sangat cocok untuk ini, jadi saya memutuskan untuk menulis posting pertama saya.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Bernd Fischer
sumber
3

Haskell , 33 byte

g~(a:b:c)=1:a:0:b:g c
d=g d
(d!!)

Cobalah online!

Menggunakan pengindeksan 0.

Anders Kaseorg
sumber
1
Apa yang ~dilakukan dalam konteks ini? Saya mengerti bahwa ini adalah pertandingan yang malas, tetapi mengapa Anda membutuhkan pertandingan yang malas?
Wheat Wizard
2

Jelly , 7 6 byte

1 byte berkat Erik the Outgolfer.

Bt0ṖṪṆ

Cobalah online!

Program yang lebih panjang

Biarawati Bocor
sumber
Hmm ... yah, Anda bisa melakukan ṖṪṆ(sebagai jawaban saya yang dihapus) alih-alih ṫ-ḄỊ.
Erik the Outgolfer
1
Satu lagi untuk daftar 7-byte Anda:BUḌDḊḢ¬
steenbergh
2

,,, , 10 9 bytes

::0-&2*&¬

Penjelasan

Ambil input sebagai 3 misalnya.

::0-&2*&1≥
               implicitly push command line argument       [3]
::             duplicate twice                             [3, 3, 3]
  0            push 0 on to the stack                      [3, 3, 3, 0]
   -           pop 0 and 3 and push 0 - 3                  [3, 3, -3]
    &          pop -3 and 3 and push -3 & 3 (bitwise AND)  [3, 1]
     2         push 2 on to the stack                      [3, 1, 2]
      *        pop 2 and 1 and push 2 * 1                  [3, 2]
       &       pop 2 and 3 and push 2 & 3                  [2]
        ¬      pop 2 and push ¬ 2 (logical NOT)            [0]
               implicit output                             []
benar-benar manusiawi
sumber
2

Oktaf , 34 byte

@(x)~(k=[de2bi(x),0])(find(k,1)+1)

Cobalah online!

Penjelasan:

@(x)                               % Anonymous function taking a decimal number as input
    ~....                          % Negate whatever comes next
     (   de2bi(x)   )              % Convert x to a binary array that's conveniently 
                                   % ordered with the least significant bits first
        [de2bi(x),0]               % Append a zero to the end, to avoid out of bound index
     (k=[de2bi(x),0])              % Store the vector as a variable 'k'
                     (find(k,1)    % Find the first '1' in k (the least significant 1-bit)
                               +1  % Add 1 to the index to get the next bit
     (k=[de2bi(x),0])(find(k,1)+1) % Use as index to the vector k to get the correct bit
Stewie Griffin
sumber
Kenapa saya tidak pernah mendengar tentang de2bi ...: O
Sanchises
1

Pengajuan:

Python 2 , 41 39 byte

x=input()
while~-x&1:x/=2
print 1-x/2%2

Cobalah online!

-2 byte terima kasih kepada FryAmTheEggman

Solusi Awal:

Python 2 , 43 byte

lambda x:1-int(bin(x)[bin(x).rfind('1')-1])

Cobalah online!

HyperNeutrino
sumber
Jadi yang mana kiriman Anda?
Leaky Nun
@ LeakyNun Yang pertama karena lebih pendek; yang kedua adalah pengiriman asli saya. Haruskah saya mempostingnya secara terpisah?
HyperNeutrino
~-x&1bekerja untuk kondisi sementara, saya pikir.
FryAmTheEggman
(Saya lupa nama pengguna); Saya menolak hasil edit Anda karena suntingan ke golf kode orang lain tidak disarankan di PPCG. Anda dapat memposting saran (btw, terima kasih @FryAmTheEggman), tapi tolong jangan membuat suntingan golf. Terima kasih!
HyperNeutrino
@StewieGriffin Ah ya, terima kasih. Sayangnya saya tidak bisa mem-ping pengguna karena hasil edit ditolak.
HyperNeutrino
1

MATL , 11 10 byte

t4*YF1)Z.~

Cobalah online! Atau lihat 100 output pertama .

Penjelasan

t    % Implicit input. Duplicate
4*   % Multiply by 4. This ensures that the input is a multiple of 2, and
     % takes into account that bit positions are 1 based
YF   % Exponents of prime factorization
1)   % Get first exponent, which is that of factor 2
Z.   % Get bit of input at that (1-based) position
~    % Negate. Implicit display
Luis Mendo
sumber
1

Befunge-98 , 19 byte

&#;:2%\2/\#;_;@.!%2

Cobalah online!

&#                       Initial input: Read a number an skip the next command
  ;:2%\2/\#;_;           Main loop: (Direction: East)
   :2%                    Duplicate the current number and read the last bit
      \2/                 Swap the first two items on stack (last bit and number)
                          and divide the number by two => remove last bit
         \                swap last bit and number again
          #;_;            If the last bit is 0, keep going East and jump to the beginning of the loop
                          If the last bit is 1, turn West and jump to the beginning of the loop, but in a different direction.
&#;           @.!%2      End: (Direction: West)
&#                        Jump over the input, wrap around
                 %2       Take the number mod 2 => read the last bit
               .!         Negate the bit and print as a number
              @          Terminate
ovs
sumber
1

SCALA, 99 (78?) Karakter, 99 (78?) Byte

if(i==0)print(1)else
print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

dimana iinputnya

Seperti yang Anda lihat, saya menghemat 21 byte jika saya tidak menangani nol (seperti yang penulis lakukan dalam test case-nya):

print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

Ini codegolf pertama saya jadi saya harap saya melakukannya dengan baik :)

Cobalah online! Meskipun cukup lama untuk menghitung lol.

V. Courtois
sumber
Selamat datang di situs ini!
DJMcMayhem
1

Java 8, 17 byte

n->(n&2*(n&-n))<1

Port langsung jawaban LeakyNun's Python 3 . Saya tidak cukup terbiasa dengan operasi bitwise dan prioritas operator untuk melihat solusi yang lebih pendek; mungkin ada cara untuk menghindari tanda kurung tambahan?

JollyJoker
sumber
0

Japt , 10 8 9 byte

!+¢g¢a1 É

Cobalah online!

Penjelasan

!+¢   g    a1 É
!+Us2 gUs2 a1 -1 # Implicit input (U) as number
!+               # Return the boolean NOT of
      g          #   the character at index
       Us2       #     the input converted to binary
           a1    #     the index of its last 1
              -1 #     minus 1
      g          #   in string
  Us2            #     the input converted to binary
Luke
sumber
Ini mengembalikan falsesemua karena karakter (0 atau 1) selalu berupa string.
Shaggy
Ups, harusnya memperhatikan bahwa ... Tetap sekarang
Luke
Sepertinya gagal untuk1 saat ini.
Shaggy
0

JavaScript (ES6), 53 34 byte

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Luke
sumber
42 byte:a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Shaggy
Saya sudah menemukan solusi yang lebih pendek (matematis) ...
Luke
Bagus :) Keberatan jika saya memposting satu 42 byte itu?
Shaggy
@Shaggy, tidak sama sekali
Luke
0

Gangguan Umum, 56 byte

(defun f(n)(if(oddp n)(- 1(mod #1=(ash n -1)2))(f #1#)))

Cobalah online!

Renzo
sumber
0

Chip , 93 byte

HZABCDEFG,t
 ))))))))^~S
H\\\\\\\/v~a
G\\\\\\/v'
F\\\\\/v'
E\\\\/v'
D\\\/v'
C\\/v'
B\/v'
A/-'

Mengambil input sebagai byte endian kecil. (TIO memiliki sedikit python yang melakukan ini untuk Anda). Memberikan output sebagai salah satu 0x0atau0x1 . (TIO menggunakan xxd untuk memeriksa nilainya).

Cobalah online!

Bagaimana ini?

Chip melihat input satu byte pada satu waktu, sehingga penanganan input multibyte menambahkan sejumlah besar, tetapi tidak dekat seperti yang saya takutkan.

Mari kita masuk ke dalamnya:

HZABCDEFG

Ini adalah HZ, bit tinggi dari byte sebelumnya (jika ada satu), dan A- G, tujuh bit lebih rendah dari byte saat ini. Ini digunakan untuk menemukan bit set angka terendah.

        ,t
))))))))^~S

Ketika bit set terendah ditemukan, kami memiliki beberapa hal yang harus dilakukan. Potongan pertama ini mengatakan "jika kita memiliki bit yang diset ( )'s), kemudian berhenti Smenekan output, dan tberkembang setelah kita mencetak jawabannya.

H\\\\\\\/v~a
G\\\\\\/v'
...
A/-'

Bit mana pun dari byte saat ini ( A- H) hanya didahului oleh sekelompok nol kemudian satu ( \dan /: ini melihat bit langsung di utara mereka; kita dapat percaya bahwa semua bit sebelumnya nol) dilewatkan ke kabel di hak ( v,, '...), maka nilai mana pun yang dibalik dan diberikan sebagai bit output yang rendah ( ~a).

Phlarx
sumber