Los antiguos griegos tenían estas cosas llamadas números simples y doblemente pares. Un ejemplo de un número par individual es 14. Se puede dividir por 2 una vez, y en ese punto se ha convertido en un número impar (7), después de lo cual ya no es divisible por 2. Un número doblemente par es 20. Se puede dividir por 2 dos veces, y luego se convierte en 5.

Su tarea es escribir una función o programa que tome un número entero como entrada y genere el número de veces que es divisible por 2 como número entero, en la menor cantidad de bytes posible. La entrada será un número entero distinto de cero (cualquier valor positivo o negativo, dentro de los límites de su idioma).

Casos de prueba:

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

La respuesta con la menor cantidad de bytes gana.

Consejo: Intenta convertir el número a base 2. Mira lo que te dice.

Jalea , 4 bytes

Æfċ2

En la última versión de Jelly, ÆEḢ(3 bytes) funciona.

Æf      Calculate the prime factorization. On negative input, -1 appended to the end.
  ċ2    Count the 2s.

Pruébalo aquí .

Código de máquina x86_64, 4 bytes

¡La instrucción BSF (bit scan forward) hace exactamente esto !

0x0f    0xbc    0xc7    0xc3

En el ensamblaje de estilo gcc, esto es:

    .globl  f
f:
    bsfl    %edi, %eax
    ret

La entrada se proporciona en el registro EDI y se devuelve en el registro EAX según las convenciones de llamadas c estándar de 64 bits .

Debido a la codificación binaria del complemento a dos, esto funciona para los números -ve y + ve.

Además, a pesar de la documentación que dice "Si el contenido del operando de origen es 0, el contenido del operando de destino no está definido". , Encuentro en mi Ubuntu VM que la salida de f(0)es 0.

Instrucciones:

• Guarde lo anterior como evenness.sy arme congcc -c evenness.s -o evenness.o
• Guarde el siguiente controlador de prueba como evenness-main.cy compile con gcc -c evenness-main.c -o evenness-main.o:

#include <stdio.h>

extern int f(int n);

int main (int argc, char **argv) {
    int i;

    int testcases[] = { 14, 20, 94208, 7, 0, -4 };

    for (i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++) {
        printf("%d, %d\n", testcases[i], f(testcases[i]));
    }

    return 0;
}

Entonces:

• Enlazar: gcc evenness-main.o evenness.o -o evenness
• Correr: ./evenness

@FarazMasroor solicitó más detalles sobre cómo se obtuvo esta respuesta.

Estoy más familiarizado con c que las complejidades del ensamblaje x86, por lo que generalmente uso un compilador para generar código de ensamblaje para mí. Sé por experiencia que las extensiones gcc como __builtin_ffs(), __builtin_ctz()y__builtin_popcount() típicamente compilan y ensamblan a 1 o 2 instrucciones en x86. Entonces comencé con una función c como:

int f(int n) {
    return __builtin_ctz(n);
}

En lugar de usar la compilación gcc regular hasta el código objeto, puede usar la -Sopción de compilar solo para ensamblar - gcc -S -c evenness.c. Esto da un archivo de ensamblaje evenness.scomo este:

    .file   "evenness.c"
    .text
    .globl  f
    .type   f, @function
f:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    rep bsfl    %eax, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   f, .-f
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

Mucho de esto se puede jugar al golf. En particular, sabemos que la convención de llamada c para funciones con firma es agradable y simple: el parámetro de entrada se pasa en el registro y el valor de retorno se devuelve en el registro. Por lo tanto, podemos extraer la mayoría de las instrucciones: muchas de ellas se preocupan por guardar registros y configurar un nuevo marco de pila. No usamos la pila aquí y solo usamos el registro, por lo que no debemos preocuparnos por otros registros. Esto deja el código de ensamblaje "golfizado":int f(int n);EDIEAXEAX

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Tenga en cuenta que, como señala @zwol, también puede usar una compilación optimizada para lograr un resultado similar. En particular, -Osproduce exactamente las instrucciones anteriores (con algunas directivas de ensamblador adicionales que no producen ningún código de objeto adicional).

Esto ahora se ensambla con gcc -c evenness.s -o evenness.o, que luego se puede vincular a un programa de controlador de prueba como se describe anteriormente.

Hay varias formas de determinar el código de máquina correspondiente a este ensamblaje. Mi favorito es usar el disasscomando de desmontaje gdb :

$ gdb ./evenness
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
...
Reading symbols from ./evenness...(no debugging symbols found)...done.
(gdb) disass /r f
Dump of assembler code for function f:
   0x00000000004005ae <+0>: 0f bc c7    bsf    %edi,%eax
   0x00000000004005b1 <+3>: c3  retq   
   0x00000000004005b2 <+4>: 66 2e 0f 1f 84 00 00 00 00 00   nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005bc <+14>:    0f 1f 40 00 nopl   0x0(%rax)
End of assembler dump.
(gdb) 

Entonces podemos ver que el código de máquina para la bsfinstrucción es 0f bc c7y para retes c3.

Python, 25 bytes

lambda n:len(bin(n&-n))-3

n & -n pone a cero cualquier cosa excepto el bit menos significativo, por ejemplo, esto:

100010101010100000101010000
            v
000000000000000000000010000

Estamos interesados ​​en el número de ceros finales, por lo que lo convertimos a una cadena binaria usando bin, que será el número anterior "0b10000". Como no nos preocupamos por el 0b, ni el 1, restamos 3 de esa longitud de cadenas.

Pyth, 6 bytes

/P.aQ2

Pruébalo aquí .

 P.aQ         In the prime factorization of the absolute value of the input
/    2        count the number of 2s.

JavaScript (ES6), 18 bytes

n=>Math.log2(n&-n)

4 bytes más cortos que 31-Math.clz32. Jaja

JavaScript ES6, 22 19 bytes

f=x=>x%2?0:f(x/2)+1

Parece que la recursión es la ruta más corta.

Pyth, 8 bytes

lec.BQ\1

     Q    autoinitialized to eval(input())
   .B     convert to binary string
  c   \1  split on "1", returning an array of runs of 0s
 e        get the last run of 0s, or empty string if number ends with 1
l         take the length

Por ejemplo, la representación binaria de 94208es:

10111000000000000

Después de dividirse en 1sy tomar el último elemento de la matriz resultante, esto se convierte en:

000000000000

Eso es 12 ceros, por lo que es "12-ly even".

Esto funciona porque x / 2es esencialmente x >> 1, es decir, un desplazamiento de bits a la derecha 1. Por lo tanto, un número es divisible por 2 solo cuando el LSB es 0(al igual que un número decimal es divisible por 10 cuando su último dígito es 0).

05AB1E , 4 5 bytes

Ahora admite números negativos. Código:

Äb1¡g

Pruébalo en línea!

Explicación:

Ä      # Abs(input)
 b     # Convert the number to binary
  1¡   # Split on 1's
    g  # Take the length of the last element

Utiliza la codificación CP-1252.

Pyth, 6 bytes

x_.BQ1

Básicamente solo

convert2BinString(evaluatedInput())[::-1].index("1")

MATL , 5 bytes

Yf2=s

Esto funciona para todos los enteros.

Pruébalo en línea!

Yf      % implicit input. Compute (repeated) prime factors. For negative input
        % it computes the prime factors of the absolute value, except that for
        % -1 it produces an empty array instead of a single 1
2=s     % count occurrences of "2" in the array of prime factors

C, 36 (28) bytes

int f(int n){return n&1?0:f(n/2)+1;}

(No prueba el argumento cero porque se especificó un argumento distinto de cero).

Actualización (en respuesta al comentario) : si permitimos declaraciones de funciones de estilo K&R, entonces podemos tener una versión de 28 bytes:

f(n){return n&1?0:f(n/2)+1;}

En este caso, confiamos en el hecho de que el compilador predetermina ambos ny el tipo de retorno de fto int. Sin embargo, este formulario genera una advertencia con C99 y no se compila como código C ++ válido.

Java 7, 39 o quizás 44 bytes

int s(int a){return a%2!=0?0:s(a/2)+1;}

int s(int a){return a%2!=0|a==0?0:s(a/2)+1;}

Yay recursión! Tuve que usar una !=comparación en lugar de una comparación más corta para que no se desbordara en la entrada negativa, pero aparte de eso, es bastante sencillo. Si es extraño, envíe un cero. Si es par, agregue uno y vuelva a hacerlo.

Hay dos versiones porque en este momento la salida para cero es desconocida. El primero se repetirá hasta que la pila se desborde y no muestre nada, porque 0 es infinitamente par. El segundo escupe un 0 agradable, seguro, pero probablemente no matemáticamente riguroso para la salida.

JavaScript (ES6), 20 bytes 19 bytes.

f=x=>~x%2&&1+f(x/2)

Este es un puerto de la solución Haskell de @nimi a JavaScript. Utiliza las propiedades de "cortocircuito" de las &&cuales devuelve su lado izquierdo si es falsey (que en este caso es -0) o si no devuelve su lado derecho. Para implementar odd x = 0, por lo tanto, hacemos el lado izquierdo 1 - (x % 2)que burbujea a 0través del &&, de lo contrario recurrimos a 1 + f(x / 2).

El afeitado de 1 - (x % 2)as (~x) % 2se debe a @Neil a continuación, y tiene la extraña propiedad que hace que la función anterior se emita -0para números impares pequeños. Este valor es una peculiaridad de la decisión de JS de que los enteros son dobles IEEE754; Este sistema tiene un separado +0y -0que están especialmente revestidos en JavaScript para ser el ===uno al otro. El ~operador calcula la inversión en bits de enteros con signo de 32 bits para el número, que para números impares pequeños será un número par negativo. (El número positivo, Math.pow(2, 31) + 1por ejemplo, produce en 0lugar de -0). La extraña restricción a los enteros con signo de 32 bits no tiene ningún otro efecto; en particular no afecta la corrección.

Perl 6, 23 18 bytes

{+($_,*/2...^*%2)}

uso

> my &f = {+($_,*/2...^*%2)}
-> ;; $_? is raw { #`(Block|117104200) ... }
> f(14)
1
> f(20)
2
> f(94208)
12
> f(7)
0
> f(-4)
2

Ruby 24 bytes

Mi primer envío de código de golf (¡sí!)

("%b"%$*[0])[/0*$/].size

Como llegué aquí :

Primero quería obtener un código que realmente cumpliera con las especificaciones para entender el problema, así que construí el método sin importar el número de bytes:

def how_even(x, times=1)
  half = x / 2
  if half.even?
    how_even(half, times+1)
  else
    times
  end
end

con este conocimiento, reduje la función a un ciclo while y agregué $*(ARGV) como entrada e i como el recuento de cuántas veces se ha reducido a la mitad el número antes de que se vuelva impar.

x=$*[0];i=1;while(x=x/2)%2<1;i+=1;end;i

Estaba bastante orgulloso de esto y casi lo presenté antes de que me diera cuenta de que todo esto dividido por dos me pareció un poco binario, ser ingeniero de software pero no tanto científico de la computación, esto no fue lo primero que se me ocurrió.

Así que reuní algunos resultados sobre cómo se veían los valores de entrada en binario:

input      in binary      result
---------------------------------
   14               1110   1
   20              10100   2
94208  10111000000000000  12

Noté que el resultado era el número de posiciones a la izquierda que tenemos que recorrer antes de que el número se vuelva impar.

Haciendo algunas manipulaciones de cadena simples, dividí la cadena en la última aparición de 1 y conté la longitud de los ceros restantes:

("%b"%$*[0])[/0*$/].size

usando el ("%b" % x)formato para convertir un número en binario, y String # slice para cortar mi cadena.

¡He aprendido algunas cosas sobre el rubí en esta búsqueda y espero tener más campos de golf pronto!

J, 6 bytes

1&q:@|

Explicación:

     |    absolute value
1&q:      exponent of 2 in the prime factorization

C, 37 bytes

f(int x){return x?x&1?0:1+f(x/2):0;} Verifique recursivamente el último bit hasta que no sea un 0.

Haskell, 28 bytes

f x|odd x=0|1<2=1+f(div x 2)

Ejemplo de uso: f 94208-> 12.

Si el número es impar, el resultado es 0, de lo contrario, 1más una llamada recursiva con la mitad del número.

Befunge, 20

&:2%#|_\1+\2/#
   @.<

La ejecución del código se mueve hacia la derecha y se ajusta al segundo carácter de la primera línea (gracias al final #) hasta las 2%salidas 1, lo que hace _que cambie la dirección hacia la izquierda, luego |hacia arriba, que se envuelve <en la segunda fila, que sale y sale. Incrementamos el elemento del segundo al tope de la pila cada vez a través del ciclo, luego dividimos la parte superior por 2.

retina ,29 17

+`\b(1+)\1$
;$1
;

Pruébalo en línea!

¡2 bytes guardados gracias a Martin!

Toma entrada unaria. Esto coincide repetidamente con la mayor cantidad de 1s que puede, de modo que ese número de 1s coincida exactamente con el resto de 1s en el número. Cada vez que hace esto, antepone un ;a la cadena. Al final, contamos el número de ;s en la cadena.

Si desea entrada decimal, agregue:

\d+
$0$*1

al comienzo del programa.

Jolf, 6 bytes

Pruébalo aquí!

Zlm)j2
Zl   2  count the number occurrences of 2 in
  m)j   the prime factorization of j (input)

Más bien simple ... Felicitaciones a ETHProductions por expulsar a Jolf con la versión que realmente debería funcionar.

PARI / GP, 17 bytes

n->valuation(n,2)

6502 lenguaje máquina, 7 bytes

Para encontrar el valor posicional del 1 bit menos significativo del valor distinto de cero en el acumulador, dejando el resultado en el registro X:

A2 FF E8 4A 90 FC 60

Para ejecutar esto en el simulador 6502 en e-tradition.net , agregue un prefijo A9seguido de un entero de 8 bits.

Esto desmonta a lo siguiente:

count_trailing_zeroes:
    ldx #$FF
loop:
    inx
    lsr a     ; set carry to 0 iff A divisible by 2, then divide by 2 rounding down
    bcc loop  ; keep looping if A was divisible by 2
    rts       ; return with result in X

Esto es equivalente a la siguiente C, excepto que C debe intser de al menos 16 bits:

unsigned int count_trailing_zeroes(int signed_a) {
    unsigned int carry;
    unsigned int a = signed_a;  // cast to unsigned makes shift well-defined
    unsigned int x = UINT_MAX;
    do {
        x += 1;
        carry = a & 1;
        a >>= 1;
    } while (carry == 0);
    return x;
}

Lo mismo funciona en un 65816, suponiendo MX = 01 (acumulador de 16 bits, índice de 8 bits), y es equivalente al fragmento C anterior.

Brachylog , 27 15 bytes

$pA:2xlL,Al-L=.

Explicación

$pA             § Unify A with the list of prime factors of the input
   :2x          § Remove all occurences of 2 in A
      lL,       § L is the length of A minus all the 2s
         Al-L=. § Unify the output with the length of A minus L

CJam, 8 bytes

rizmf2e=

Leer entero, valor absoluto, factorizar primo, contar dos.

JavaScript ES6, 36 38 bytes

Golfed dos bytes gracias a @ETHproductions

Respuesta bastante aburrida, pero hace el trabajo. En realidad, puede ser demasiado similar a otra respuesta, si agrega los cambios sugeridos, eliminaré la mía.

b=>{for(c=0;b%2-1;c++)b/=2;alert(c)}

Para ejecutarlo, asígnelo a una variable ( a=>{for...) ya que es una función anónima, luego llámelo con a(100).

ES6, 22 bytes

n=>31-Math.clz32(n&-n)

Devuelve -1 si pasa 0.

DUP , 20 bytes

[$2/%0=[2/f;!1+.][0]?]f:

Try it here!

Convertido a recursividad, la salida es ahora el número superior en la pila. Uso:

94208[2/\0=[f;!1+][0]?]f:f;!

Explicación

[                ]f: {save lambda to f}
 2/\0=               {top of stack /2, check if remainder is 0}
      [     ][ ]?    {conditional}
       f;!1+         {if so, then do f(top of stack)+1}
              0      {otherwise, push 0}

Japt, 9 5 bytes

¢w b1

¡Pruébelo en línea!

La versión anterior debería haber sido de cinco bytes, pero esta realmente funciona.

Cómo funciona

       // Implicit: U = input integer
¢      // Take the binary representation of U.
w      // Reverse.
b1     // Find the first index of a "1" in this string.
       // Implicit output

C, 44 40 38 36 bytes

2 bytes de descuento gracias @ JohnWHSmith . 2 bytes de descuento gracias @luserdroog .

a;f(n){for(;~n&1;n/=2)a++;return a;}

Prueba en vivo en ideone .