Sekwencja krzywa smok (lub określonej sekwencji składania papier) jest sekwencją binarną. a(n)jest podane przez zanegowanie bitu po lewej stronie najmniej znaczącego 1 z n. Na przykład, aby obliczyć a(2136), najpierw konwertujemy na binarny:

100001011000

Znajdujemy nasz najmniej znaczący kawałek

100001011000
        ^

Weź kawałek w lewo

100001011000
       ^

I zwróć swoją negację

0

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą jako dane wejściowe, wyjściowe a(n) . (Możesz generować przez liczbę całkowitą lub wartość logiczną). Powinieneś dążyć do tego, aby twój kod był tak mały, jak to możliwe, mierzony bajtami.

Przypadki testowe

Oto pierwsze 100 wpisów w kolejności

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

Mathematica 25 bajtów

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

Inne sposoby na to:

56 bajtów

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

58 bajtów

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&

Python 3 , 22 21 bajtów

1 bajt dzięki produktom ETH.

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

Wypróbuj online!

Bitowe arytmetyki ftw.

Siatkówka oka ,38 34 29 bajtów

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

Wypróbuj online!

Martin i Leaky zasadniczo wymyślili ten pomysł, za 5 kolejnych bajtów!

Konwertuje dane wejściowe na jednoargumentowe, a następnie stopniowo dzieli liczbę przez 2. Gdy nie może już tego zrobić równomiernie (tzn. Liczba jest nieparzysta), usuwa łatki 4 z danych wejściowych, obliczając wynik ostatniej operacji mod 4 Na koniec sprawdza, czy wynik wynosił 1, co oznacza, że ​​cyfra na lewo od najmniej znaczącego 1 bitu wynosiła zero. Jeśli to prawda, końcowy wynik to 1, w przeciwnym razie zero.

Galaretka , 5 bajtów

&N&HṆ

Wypróbuj online!

Jak to działa

&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.

Alice , 8 bajtów

I2z1xnO@

Wypróbuj online!

Pobiera dane wejściowe jako punkt kodowy znaku Unicode i odpowiednio wyświetla wynik jako bajt 0x00 lub 0x01.

W celu przetestowania, oto wersja dziesiętna we / wy na 12 bajtów, która używa dokładnie tego samego algorytmu (tylko we / wy jest inne):

/o
\i@/2z1xn

Wypróbuj online!

Gdyby Alicja była językiem golfowym i nie wymagała wyraźnego wejścia / wyjścia i zakończenia programu, 2z1xnosiągnęłoby to zaledwie 5 bajtów ( ), pokonując zarówno 05AB1E, jak i Jelly.

Wyjaśnienie

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.

05AB1E , 6 bajtów

b0ܨθ≠

Wypróbuj online!

Mądry , 28 20 16 bajtów

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

Wypróbuj online!

Wyjaśnienie

To jest port odpowiedzi Pythona Dziurawej Zakonnicy. Niestety nie działa na TIO, ponieważ wersja interpretera TIO jest nieco nieaktualna.

Zaczynamy od wykonania 3 kopii naszych danych wejściowych ::, a następnie zmniejszamy górną kopię o 1. Spowoduje to odwrócenie wszystkich bitów do pierwszej 1. Następnie xor to z inną kopią naszych danych wejściowych. Ponieważ wszystkie bity do pierwszej 1 na naszym wejściu zostały odwrócone, spowoduje to, że wszystkie te bity będą miały 1 na wyniku. Jeśli następnie dodamy jeden ~-do wyniku, otrzymamy jeden 1 w miejscu po lewej stronie naszego najmniej znaczącego 1. My ORAZ to z wejściem, aby uzyskać ten bit z wejścia. Teraz będziemy mieć 0iff, że ten bit był wyłączony i moc 2 iff, ten bit był włączony, możemy zmienić to na pojedyncze 1lub 0z :[?>]. Gdy to zrobimy, musimy tylko trochę zanegować ~-^i gotowe.

Python 2 , 19 bajtów

lambda n:n&-n&n/2<1

Wypróbuj online!

Haskell , 45 43 39 bajtów

6 bajtów zapisanych dzięki nim

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

Wypróbuj online!

Kod maszynowy x86, 17 16 15 bajtów:

Zakłada ABI, w którym parametry są wypychane na stos, a zwracana wartość znajduje się w ALrejestrze.

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

Rozkłada się to w następujący sposób:

_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

JavaScript (ES6), 17 14 bajtów

f=
n=>!(n&-n&n/2)

<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Edycja: Zapisałem 3 bajty, przenosząc odpowiedź @ Dennisa, gdy zauważyłem, że wyjście boolowskie jest dopuszczalne.

C (gcc) , 20 bajtów

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

Wypróbuj online!

INTERCAL , 50 bajtów

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

Jednoargumentowi operatorzy INTERCAL są do tego całkiem odpowiedni, więc postanowiłem napisać swój pierwszy post.

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

Haskell , 33 bajty

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

Wypróbuj online!

Wykorzystuje indeksowanie 0.

Galaretka , 7 6 bajtów

1 bajt dzięki Erik the Outgolfer.

Bt0ṖṪṆ

Wypróbuj online!

Dłuższe programy

• 7 bajtów: Họ¡2&2Ị
• 7 bajtów: Bt0ṫ-ḄỊ

,,, , 10 9 bajtów

::0-&2*&¬

Wyjaśnienie

Weź na przykład dane wejściowe jako 3.

::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                             []

Haskell , 26 bajtów

f n=even$div n$2*gcd(2^n)n

Wypróbuj online!

Wyjście logiczne.

Oktawa , 34 bajty

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

Wypróbuj online!

Wyjaśnienie:

@(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

Uległość:

Python 2 , 41 39 bajtów

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

Wypróbuj online!

-2 bajty dzięki FryAmTheEggman

Wstępne rozwiązanie:

Python 2 , 43 bajty

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

Wypróbuj online!

MATL , 11 10 bajtów

t4*YF1)Z.~

Wypróbuj online! Lub zobacz pierwsze 100 wyników .

Wyjaśnienie

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

Pari / GP , 20 bajtów

n->kronecker(-1,n)>0

Używanie symbolu Kronecker .

Wypróbuj online!

Befunge-98 , 19 bajtów

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

Wypróbuj 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

SCALA, 99 (78?) Znaków, 99 (78?) Bajtów

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

gdzie ijest wejście.

Jak widać, oszczędzam 21 bajtów, jeśli nie dbam o zero (tak jak autor w swoim przypadku testowym):

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

To mój pierwszy codegolf, więc mam nadzieję, że dobrze mi poszło :)

Wypróbuj online! Chociaż obliczenie lol jest dość długie.

C (gcc) , 35 31 bajtów

f(x){return~x&1?f(x/2):!(x&2);}

Przełączono na implementację rekurencyjną. Wypróbuj online!

Java 8, 17 bajtów

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

Prosty port odpowiedzi LeakyNun na Python 3 . Nie znam wystarczająco operacji bitowych i pierwszeństwa operatorów, aby zobaczyć krótsze rozwiązanie; może istnieje sposób na uniknięcie dodatkowego nawiasu?

Japt , 10 8 9 bajtów

!+¢g¢a1 É

Wypróbuj online!

Wyjaśnienie

!+¢   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

JavaScript (ES6), 53 34 bajty

a=>eval("for(;~a&1;a/=2);~a>>1&1")

PHP> = 7.1, 32 bajty

<?=1^!trim(decbin($argn),0)[-2];

PHP Sandbox Online

PHP , 40 bajtów

for($i=$argn;$i%2<1;)$i/=2;echo$i/2%2^1;

Wypróbuj online!

PHP , 41 bajtów

<?=1^preg_match("#110*$#",decbin($argn));

Wypróbuj online!

Common Lisp, 56 bajtów

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

Wypróbuj online!

Chip , 93 bajty

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

Pobiera dane wejściowe jako małe bajty endian. (TIO ma trochę Pythona, który robi to za Ciebie). Daje wyjście jako albo 0x0albo 0x1. (TIO używa xxd do sprawdzenia wartości).

Wypróbuj online!

Jak to zrobić?

Chip patrzy na dane wejściowe jeden bajt na raz, więc obsługa danych wielobajtowych dodaje trochę objętości, ale nie tak bardzo, jak się obawiałem.

Przejdźmy do tego:

HZABCDEFG

Są to HZ: wysoki bit poprzedniego bajtu (jeśli był) i A- Gsiedem niższych bitów bieżącego bajtu. Służą one do zlokalizowania najniższego ustawionego bitu liczby.

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

Kiedy zostanie znaleziony najniższy ustawiony bit, mamy kilka rzeczy do zrobienia. Ta pierwsza porcja mówi „jeśli mamy ustawiony bit ( )y), to przestań Szwiększać wydajność i tkończymy po wydrukowaniu odpowiedzi.

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

Niezależnie od tego, który bit bieżącego bajtu ( A- H) poprzedza tylko wiązka zer, wówczas jeden ( \i /: patrzą one na bity bezpośrednio na północ od nich; możemy ufać, że wszystkie poprzednie bity były zerowe) są przekazywane do przewodów na prawo ( v, '...), a następnie tych dwóch wartości jest odwracany i jest podawana jako niski bit wyjścia ( ~a).