A sequência da curva do dragão (ou a sequência regular de dobragem de papel) é uma sequência binária. a(n)é dado pela negação do bit restante do 1 menos significativo n. Por exemplo, para calcular a(2136), primeiro convertemos para binário:

100001011000

Encontramos o nosso pouco menos significativo

100001011000
        ^

Leve o bit para a esquerda

100001011000
       ^

E devolver sua negação

0

Tarefa

Dado um número inteiro positivo como entrada, saída a(n). (Você pode imprimir por número inteiro ou por booleano). Você deve tentar tornar seu código o menor possível, medido por bytes.

Casos de teste

Aqui estão as primeiras 100 entradas em ordem

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 Bytes

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

Outras maneiras de fazer isso:

56 bytes

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

58 bytes

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

Python 3 , 22 21 bytes

1 byte graças à ETHproductions.

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

Experimente online!

Ftw aritmético bit a bit.

Retina ,38. 34 29 bytes

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

Experimente online!

Martin e Leaky vieram com essa idéia, com mais 5 bytes de desconto!

Converte a entrada em unário e, em seguida, divide progressivamente o número por 2. Uma vez que não pode mais fazer isso uniformemente (ou seja, o número é ímpar), remove os patches de 4 da entrada, calculando o resultado da última operação mod 4 Finalmente, isso verifica se o resultado foi 1, o que significa que o dígito à esquerda do 1 bit menos significativo foi zero. Se isso for verdade, o resultado final é 1, caso contrário, é zero.

Geléia , 5 bytes

&N&HṆ

Experimente online!

Como funciona

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

I2z1xnO@

Experimente online!

Recebe entrada como o ponto de código de um caractere Unicode e gera o resultado como um byte 0x00 ou 0x01 em conformidade.

Para teste, aqui está uma versão de E / S decimal em 12 bytes que usa exatamente o mesmo algoritmo (apenas E / S é diferente):

/o
\i@/2z1xn

Experimente online!

Se Alice fosse uma linguagem de golfe e não exigisse E / S explícita e encerramento do programa, isso ocorreria a meros 5 bytes ( 2z1xn), superando 05AB1E e Jelly.

Explicação

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 bytes

b0ܨθ≠

Experimente online!

Sábio , 28 20 16 bytes

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

Experimente online!

Explicação

Esta é uma porta da resposta Python do Leaky Nun. Infelizmente, ele não funciona no TIO porque a versão do intérprete está um pouco desatualizada.

Começamos fazendo 3 cópias de nossa entrada com ::, em seguida, diminuímos a cópia superior em 1. Isso aumentará todos os bits até o primeiro 1. Em seguida, fazemos isso com outra cópia de nossa entrada. Como todos os bits até o primeiro 1 em nossa entrada foram invertidos, isso resultará em todos esses bits sendo 1 no resultado. Se adicionarmos um ~-ao resultado, obteremos um único 1 no local à esquerda do nosso 1. menos significativo. Nós AND com esta entrada para obter esse bit da entrada. Agora teremos 0se esse bit estiver desativado e uma potência de 2 se esse bit estiver ativado, podemos mudar isso para um único 1ou 0com :[?>]. Uma vez feito isso, precisamos apenas negar a parte ~-^e estamos prontos.

Python 2 , 19 bytes

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

Experimente online!

Haskell , 45 43 39 bytes

6 bytes salvos graças a nimi

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

Experimente online!

Código da máquina x86, 17 16 15 bytes:

Assume uma ABI em que os parâmetros são pressionados na pilha e o valor de retorno está no ALregistro.

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

Isso é desmontado da seguinte maneira:

_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 bytes

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

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

Edit: Salvo 3 bytes, portando a resposta de @ Dennis, uma vez que notei que a saída booleana era aceitável.

C (gcc) , 20 bytes

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

Experimente online!

INTERCAL , 50 bytes

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

Os operadores unários da INTERCALs são bastante adequados para isso, então decidi escrever meu primeiro post.

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

Haskell , 33 bytes

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

Experimente online!

Usa indexação 0.

Geléia , 7 6 bytes

1 byte graças a Erik, o Outgolfer.

Bt0ṖṪṆ

Experimente online!

Programas mais longos

• 7 bytes: Họ¡2&2Ị
• 7 bytes: Bt0ṫ-ḄỊ

,,, , 10 9 bytes

::0-&2*&¬

Explicação

Tome a entrada como 3, por exemplo.

::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 bytes

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

Experimente online!

Saída booleana.

Oitava , 34 bytes

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

Experimente online!

Explicação:

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

Submissão:

Python 2 , 41 39 bytes

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

Experimente online!

-2 bytes graças a FryAmTheEggman

Solução inicial:

Python 2 , 43 bytes

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

Experimente online!

MATL , 11 10 bytes

t4*YF1)Z.~

Experimente online! Ou veja as 100 primeiras saídas .

Explicação

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 bytes

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

Usando o símbolo Kronecker .

Experimente online!

Befunge-98 , 19 bytes

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

Experimente 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?) Caracteres, 99 (78?) Bytes

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

Onde iestá a entrada.

Como você pode ver, economizo 21 bytes se não cuidar do zero (como o autor fez no caso de teste):

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

Este é o meu primeiro codegolf, então espero ter me saído bem :)

Experimente online! Embora seja muito longo para calcular lol.

C (gcc) , 35 31 bytes

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

Comutado para uma implementação recursiva. Experimente online!

Java 8, 17 bytes

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

Porta direta da resposta Python 3 do LeakyNun . Não estou familiarizado o suficiente com operações bit a bit e precedência de operadores para ver uma solução mais curta; talvez haja uma maneira de evitar a parêntese extra?

Japonês , 10 8 9 bytes

!+¢g¢a1 É

Experimente online!

Explicação

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

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

PHP> = 7.1, 32 bytes

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

Sandbox do PHP Online

PHP , 40 bytes

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

Experimente online!

PHP , 41 bytes

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

Experimente online!

Lisp comum, 56 bytes

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

Experimente online!

Chip , 93 bytes

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

Recebe entrada como pequenos bytes endian. (O TIO possui um pouco de python que faz isso por você). Dá saída como 0x0ou0x1 . (O TIO usa xxd para inspecionar o valor).

Experimente online!

Como faz isso?

O chip analisa a entrada um byte de cada vez, portanto, o manuseio da entrada multibyte adiciona um pouco de volume, mas não tanto quanto eu temia.

Vamos entrar nisso:

HZABCDEFG

Estes são HZ, bits altos do byte anterior (se houver um) e A- G, os sete bits inferiores do byte atual. Eles são usados ​​para localizar o bit mais baixo definido do número.

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

Quando o bit mais baixo é encontrado, temos algumas coisas a fazer. Esse primeiro pedaço diz "se tivermos um bit definido ( )s), então pare de Spressionar a saída e ttermine depois de imprimir a resposta.

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

Qualquer bit do byte atual ( A- H) é precedido apenas por um monte de zeros e, em seguida, um ( \e /: estes olham para os bits diretamente ao norte deles; podemos confiar que todos os bits anteriores eram zero) são passados ​​para os fios nos a direita ( v, '...), então qualquer que seja o valor que ele está é invertido e dado como o baixo pouco de saída ( ~a).