Os gregos antigos tinham essas coisas chamadas números individuais e duplamente pares. Um exemplo de um número par é 14. Ele pode ser dividido por 2 uma vez e nesse ponto se tornou um número ímpar (7), após o qual não é mais divisível por 2. Um número duplamente uniforme é 20. Ele pode ser dividido por 2 duas vezes e depois se torna 5.
Sua tarefa é escrever uma função ou programa que use um número inteiro como entrada e produza o número de vezes que é divisível por 2 como número inteiro, no menor número possível de bytes. A entrada será um número inteiro diferente de zero (qualquer valor positivo ou negativo, dentro dos limites do seu idioma).
Casos de teste:
14 -> 1
20 -> 2
94208 -> 12
7 -> 0
-4 -> 2
A resposta com o mínimo de bytes vence.
Dica: Tente converter o número na base 2. Veja o que isso diz.
The input will be a nonzero integer
Isso precisa ser editado após o seu comentário sobre zero como uma entrada potencial?Respostas:
Gelatina , 4 bytes
Na versão mais recente do Jelly,
ÆEḢ
(3 bytes) funciona.Experimente aqui .
fonte
código de máquina x86_64, 4 bytes
A instrução BSF (bit scan forward) faz exatamente isso !
Na montagem no estilo gcc, é:
A entrada é fornecida no registro EDI e retornada no registro EAX de acordo com as convenções padrão de chamada c de 64 bits .
Por causa da codificação binária do complemento de dois, isso funciona para os números -ve e + ve.
Além disso, apesar da documentação dizendo "Se o conteúdo do operando de origem for 0, o conteúdo do operando de destino será indefinido". , Acho na minha VM do Ubuntu que a saída
f(0)
é 0.Instruções:
evenness.s
e monte comgcc -c evenness.s -o evenness.o
evenness-main.c
e compile comgcc -c evenness-main.c -o evenness-main.o
:Então:
gcc evenness-main.o evenness.o -o evenness
./evenness
O @FarazMasroor pediu mais detalhes sobre como essa resposta foi obtida.
Eu estou mais familiarizado com c do que com os meandros do assembly x86, então normalmente eu uso um compilador para gerar código de assembly para mim. Eu sei por experiência que as extensões do CCG como
__builtin_ffs()
,__builtin_ctz()
e__builtin_popcount()
tipicamente compilar e montar a 1 ou 2 instruções sobre x86. Então eu comecei com uma função c como:Em vez de usar a compilação gcc regular até o código do objeto, você pode usar a
-S
opção para compilar apenas para montagem -gcc -S -c evenness.c
. Isso fornece um arquivo de montagemevenness.s
como este:Muito disso pode ser jogado fora. Em particular, sabemos que a convenção de chamada c para funções com assinatura é agradável e simples - o parâmetro de entrada é passado no registrador e o valor retornado é retornado no registrador. Portanto, podemos tirar a maioria das instruções - muitas delas estão preocupadas em salvar registros e configurar um novo quadro de pilha. Nós não usamos a pilha aqui e apenas o registro, portanto, não precisa se preocupar com outros registros. Isso deixa o código de montagem "golfed":
int f(int n);
EDI
EAX
EAX
Observe como o @zwol aponta, você também pode usar a compilação otimizada para obter um resultado semelhante. Em particular,
-Os
produz exatamente as instruções acima (com algumas diretivas de montagem adicionais que não produzem nenhum código de objeto extra).Agora isso é montado
gcc -c evenness.s -o evenness.o
, o qual pode ser vinculado a um programa de driver de teste, conforme descrito acima.Existem várias maneiras de determinar o código da máquina correspondente a esta montagem. Meu favorito é usar o
disass
comando gdb disassembly:Portanto, podemos ver que o código da máquina para a
bsf
instrução é0f bc c7
e pararet
éc3
.fonte
evenness-main.c
com diferentes configurações de otimização; para mim ele quebra com-O
,-O2
ou-O3
.Python, 25 bytes
n & -n
zera qualquer coisa, exceto o bit menos significativo, por exemplo:Como estamos interessados no número de zeros à direita, convertemos para uma string binária usando
bin
, o que para o número acima será"0b10000"
. Como não nos importamos com o0b
, nem o1
, subtraímos 3 desse comprimento das strings.fonte
Pitão, 6 bytes
Experimente aqui .
fonte
JavaScript (ES6), 18 bytes
4 bytes mais curtos que
31-Math.clz32
. Hah.fonte
Math.clz32
...JavaScript ES6,
2219 bytesParece que a recursão é a rota mais curta.
fonte
Pitão, 8 bytes
Por exemplo, a representação binária de
94208
é:Após dividir em se
1
pegar o último elemento da matriz resultante, isso se torna:São 12 zeros, então é "12-pares".
Isso funciona porque
x / 2
é essencialmentex >> 1
- ou seja, um deslocamento de bits à direita1
. Portanto, um número é divisível por 2 somente quando o LSB estiver0
(assim como um número decimal é divisível por 10 quando seu último dígito for0
).fonte
05AB1E ,
45 bytesAgora suporta números negativos. Código:
Experimente online!
Explicação:
Usa a codificação CP-1252.
fonte
Pitão, 6 bytes
Basicamente apenas
fonte
MATL , 5 bytes
Isso funciona para todos os números inteiros.
Experimente online!
fonte
C, 36 (28) bytes
(Não foi testado o argumento zero, pois foi especificado um argumento diferente de zero.)
Atualização (em resposta ao comentário) : se permitirmos declarações de função no estilo K&R, poderemos ter uma versão de 28 bytes:
Nesse caso, contamos com o fato de o compilador usar como padrão ambos
n
e o tipo de retorno def
comoint
. Este formulário gera um aviso com C99 e não é compilado como código C ++ válido.fonte
int n
->n
ainda é um código C válido e corta 4 caracteres.Java 7, 39 ou talvez 44 bytes
Yay recursão! Eu tive que usar uma
!=
comparação em vez de uma comparação mais curta, para que ela não transbordasse com informações negativas, mas fora isso é bem simples. Se for estranho, envie um zero. Se for o caso, adicione um e faça-o novamente.Existem duas versões porque, no momento, a saída para zero é desconhecida. O primeiro recursará até a pilha estourar e não produzir nada, porque 0 é infinitamente uniforme. O segundo cospe um 0 agradável, seguro, mas provavelmente não matematicamente rigoroso para a saída.
fonte
JavaScript (ES6),
20 bytes19 bytes.Esta é uma porta da solução Haskell de @nimi para JavaScript. Ele usa as propriedades de "curto-circuito"
&&
que retornam seu lado esquerdo se for falsey (o que neste caso é-0
) ou então retornam seu lado direito. Para implementarodd x = 0
, portanto, fazemos o lado esquerdo1 - (x % 2)
que borbulha0
através do&&
, caso contrário, recorremos a1 + f(x / 2)
.A raspagem de
1 - (x % 2)
as(~x) % 2
é devida a @ Neil abaixo e tem a propriedade estranha que faz com que a função acima seja emitida-0
para pequenos números ímpares. Esse valor é uma peculiaridade da decisão da JS de que números inteiros são dobra IEEE754; esse sistema possui um código separado+0
e-0
que é especial em JavaScript para serem===
um para o outro. O~
operador calcula a inversão bit a bit de número inteiro com sinal de 32 bits para o número, que para números ímpares pequenos será um número par negativo. (O número positivo,Math.pow(2, 31) + 1
por exemplo, produz em0
vez de-0
.) A restrição estranha aos números inteiros assinados de 32 bits não tem outros efeitos; em particular, não afeta a correção.fonte
~x&1
é um byte menor que1-x%2
.Perl 6,
2318 bytesuso
fonte
Ruby 24 bytes
Meu primeiro envio de código de golfe (sim!)
Como cheguei aqui :
Primeiro, eu queria obter um código que realmente atendesse às especificações para resolver o problema, então criei o método sem considerar o número de bytes:
com esse conhecimento, eu recursionei a função em um loop while e adicionei
$*
(ARGV) como entrada ei como a contagem de quantas vezes o número foi dividido pela metade antes que se tornasse ímpar.Eu estava bastante orgulhoso disso e quase o enviei antes que me parecesse que toda essa divisão por dois parecia um pouco binária para mim, sendo um engenheiro de software, mas não tanto como um cientista da computação, essa não foi a primeira coisa que me veio à mente.
Então, reuni alguns resultados sobre como eram os valores de entrada em binário:
Percebi que o resultado foi o número de posições à esquerda que precisamos percorrer antes que o número se torne ímpar.
Fazendo algumas manipulações simples de sequência, divida a sequência na última ocorrência de 1 e contei o comprimento dos 0s restantes:
usando a
("%b" % x)
formatação para transformar um número em binário e String # slice para dividir minha string.Eu aprendi algumas coisas sobre o rubi nessa missão e estou ansioso por mais golfe em breve!
fonte
@wizzwizz4
no início de um comentário para responder a mim. (Isso funciona com todos os nomes de usuário!)J, 6 bytes
Explicação:
fonte
C, 37 bytes
f(int x){return x?x&1?0:1+f(x/2):0;}
Verifique recursivamente o último bit até que não seja um 0.fonte
f(int n){return __builtin_ctz(n);}
se você estiver disposto a usar extensões gcc. Ou até mesmo#define f __builtin_ctz
int
. Está implícito, assim como o tipo de retorno.f(n){...}
? O GCC não o compilará. Não sou especialista em C, mas uma pesquisa rápida revela que talvez esse recurso tenha sido removido nas versões mais recentes do C. Então, talvez ele seja compilado com os sinalizadores apropriados?-ansi
ou-gnu99
? Eu sei que consegui funcionar. Eu escrevi uma resposta de dicas sobre isso!Haskell, 28 bytes
Exemplo de uso:
f 94208
->12
.Se o número for ímpar, o resultado é
0
, outra coisa1
além de uma chamada recursiva com metade do número.fonte
div x 2
? Por que nãox/2
?div
é divisão inteira,/
divisão de ponto flutuante.Befunge, 20
A execução do código continua se movendo para a direita e passando para o segundo caractere da primeira linha (graças à direita
#
) até as2%
saídas1
, o que faz_
com que você mude a direção para a esquerda e depois|
para cima, o que envolve<
a segunda linha, quais saídas e saídas. Nós incrementamos o segundo da parte superior da pilha todas as vezes através do loop e, em seguida, dividimos a parte superior por 2.fonte
Retina ,
2917Experimente online!
2 bytes economizados graças ao Martin!
Recebe entrada unária. Isso corresponde repetidamente à maior quantidade de
1
s possível, de modo que esse número de1
s corresponda exatamente ao restante dos1
s no número. Cada vez que faz isso, ele anexa;
a à string. No final, contamos o número de;
s na string.Se você deseja entrada decimal, adicione:
para o início do programa.
fonte
Jolf, 6 bytes
Experimente aqui!
Bastante simples ... Parabéns ao ETHProductions por derrubar Jolf com a versão que realmente deve funcionar!
fonte
PARI / GP, 17 bytes
fonte
6502 linguagem de máquina, 7 bytes
Para encontrar o valor local do 1 bit menos significativo do valor diferente de zero no acumulador, deixando o resultado no registro X:
Para executar isso no simulador 6502 no e-tradition.net , prefixe-o
A9
seguido de um número inteiro de 8 bits.Isso desmonta para o seguinte:
Isso é equivalente ao C a seguir, exceto que C precisa
int
ter pelo menos 16 bits:O mesmo funciona em um 65816, assumindo MX = 01 (acumulador de 16 bits, índice de 8 bits) e é equivalente ao snippet C acima.
fonte
Braquilog ,
2715 bytesExplicação
fonte
CJam, 8 bytes
Leia inteiro, valor absoluto, fatorize primo, conte dois.
fonte
JavaScript ES6, 36
38bytesGolpeou dois bytes graças a @ETHproductions
Resposta bastante chata, mas faz o trabalho. Na verdade, pode ser muito semelhante a outra resposta, se ele adicionar as alterações sugeridas, removerei as minhas.
Para executar, atribua-o a uma variável (
a=>{for...
) como uma função anônima e, em seguida, chame-o coma(100)
.fonte
b%2==0
pode ser alterado parab%2-1
ec++
pode ser movido para a última parte dafor
instrução. Eu acho que isso também funcionaria:b=>eval("for(c=0;b%2-1;b/=2)++c")
b%2-1
=>~b&1
Além disso, penso que esta falha na entrada de0
, o que pode ser corrigido comb&&~b&1
b%2-1
a verificação falha para números ímpares negativos.ES6, 22 bytes
Retorna -1 se você passar 0.
fonte
DUP , 20 bytes
Try it here!
Convertida em recursão, a saída é agora o número superior na pilha. Uso:
Explicação
fonte
Japonês,
95 bytesTeste online!
A versão anterior deveria ter cinco bytes, mas esta realmente funciona.
Como funciona
fonte
C,
444038 36 bytes2 bytes de desconto, graças a @JohnWHSmith . 2 bytes de desconto, graças a @luserdroog .
Teste ao vivo em ideone .
fonte
!(n%2)
por um pouco mais~n&1
.=0
. Globals são implicitamente inicializado com 0.a
, não é garantido que funcione apenas na primeira vez em que é chamada? Eu não sabia que isso era permitido.