Les anciens Grecs avaient ces choses appelées des nombres simples et doublement pairs. Par exemple, un nombre pair est 14. Il peut être divisé par 2 une fois et est devenu un nombre impair (7) après lequel il n'est plus divisible par 2. Un nombre doublement pair est 20. Il peut être divisé par 2, puis devient 5.

Votre tâche consiste à écrire une fonction ou un programme prenant un nombre entier en entrée et indiquant le nombre de fois qu'il est divisible par 2 sous forme de nombre entier, avec le moins d'octets possible. L'entrée sera un entier différent de zéro (toute valeur positive ou négative, dans les limites de votre langue).

Cas de test:

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

La réponse avec le moins d'octets gagne.

Conseil: Essayez de convertir le nombre en base 2. Voyez ce que cela vous dit.

Gelée , 4 octets

Æfċ2

Dans la dernière version de Jelly, ÆEḢ(3 octets) fonctionne.

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

Essayez ici .

x86_64 code machine, 4 octets

L'instruction BSF (bit scan forward) fait exactement cela !

0x0f    0xbc    0xc7    0xc3

En assembleur de style gcc, ceci est:

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

L'entrée est donnée dans le registre de l' EDI et renvoyé dans le registre EAX selon la norme 64 bits c conventions d' appel.

En raison de l’encodage binaire à complément à deux, cela fonctionne pour les nombres aussi bien que les +.

En outre, malgré la documentation qui dit "Si le contenu de l'opérande source est 0, le contenu de l'opérande de destination est indéfini". , Je trouve sur ma machine virtuelle Ubuntu que la sortie f(0)est 0.

Instructions:

• Enregistrer ce qui précède evenness.set assembler avecgcc -c evenness.s -o evenness.o
• Enregistrez le pilote de test suivant sous evenness-main.cet compilez avec 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;
}

Ensuite:

• Lien: gcc evenness-main.o evenness.o -o evenness
• Courir: ./evenness

@FarazMasroor a demandé plus de détails sur la manière dont cette réponse a été obtenue.

C étant plus familier avec les subtilités de l’assemblage x86, j’utilise généralement un compilateur pour générer le code d’assemblage. Je sais par expérience que les extensions gcc telles que __builtin_ffs(), __builtin_ctz()et__builtin_popcount() généralement compiler et assembler 1 ou 2 instructions sur x86. J'ai donc commencé avec une fonction c comme:

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

Au lieu d’utiliser une compilation gcc normale jusqu’au code objet, vous pouvez utiliser l’ -Soption de compilation juste pour assembler - gcc -S -c evenness.c. Cela donne un fichier d'assemblage evenness.scomme ceci:

    .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

Beaucoup de cela peut être joué au golf. En particulier, nous savons que la convention d'appel c pour les fonctions avec signature est simple et agréable: le paramètre d'entrée est passé dans le registre et la valeur de retour est renvoyée dans le registre. Nous pouvons donc extraire la plupart des instructions - beaucoup d’entre elles concernent la sauvegarde des registres et la configuration d’un nouveau cadre de pile. Nous n'utilisons pas la pile ici, mais uniquement le registre, vous n'avez donc pas à vous soucier des autres registres. Cela laisse le code de montage "golfé":int f(int n);EDIEAXEAX

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

Notez que @zwol fait remarquer que vous pouvez également utiliser une compilation optimisée pour obtenir un résultat similaire. En particulier, -Osproduit exactement les instructions ci-dessus (avec quelques directives d'assembleur supplémentaires qui ne produisent pas de code objet supplémentaire).

Ceci est maintenant assemblé avec gcc -c evenness.s -o evenness.o, qui peut ensuite être lié à un programme de pilote de test comme décrit ci-dessus.

Il existe plusieurs façons de déterminer le code machine correspondant à cet assemblage. Mon préféré est d'utiliser la disasscommande de désassemblage de 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) 

Nous pouvons donc voir que le code machine pour l' bsfinstruction est 0f bc c7et pour retest c3.

Python, 25 octets

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

n & -n met à zéro tout sauf le bit le moins significatif, par exemple ceci:

100010101010100000101010000
            v
000000000000000000000010000

Nous sommes intéressés par le nombre de zéros à la fin, nous le convertissons donc en une chaîne binaire en utilisant bin, ce qui sera pour le nombre ci-dessus "0b10000". Puisque nous ne nous soucions pas de la 0b, ni de la 1, nous soustrayons 3 de la longueur de cette chaîne.

Pyth, 6 octets

/P.aQ2

Essayez ici .

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

JavaScript (ES6), 18 octets

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

4 octets plus court que 31-Math.clz32. Hah.

JavaScript ES6, 22 19 octets

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

On dirait que la récurrence est le chemin le plus court.

Pyth, 8 octets

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

Par exemple, la représentation binaire de 94208est:

10111000000000000

Après division sur 1s et prise du dernier élément du tableau résultant, ceci devient:

000000000000

C'est 12 zéros, donc c'est "même 12".

Cela fonctionne parce qu’il x / 2s’agit essentiellement, x >> 1c’est-à-dire d’un changement de bit à droite 1. Par conséquent, un nombre n'est divisible par 2 que lorsque le LSB l'est 0(comme un nombre décimal est divisible par 10 lorsque son dernier chiffre est 0).

05AB1E , 4 à 5 octets

Prend maintenant en charge les nombres négatifs. Code:

Äb1¡g

Essayez-le en ligne!

Explication:

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

Utilise le codage CP-1252.

Pyth, 6 octets

x_.BQ1

Fondamentalement juste

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

MATL , 5 octets

Yf2=s

Cela fonctionne pour tous les entiers.

Essayez-le en ligne!

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) octets

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

(Ne pas tester l'argument zéro car un argument différent de zéro a été spécifié.)

Mise à jour (en réponse au commentaire) : Si nous autorisons les déclarations de fonction de style K & R, nous pouvons avoir une version de 28 octets:

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

Dans ce cas, nous nous basons sur le fait que le compilateur utilise par défaut les deux net le type de retour fto int. Ce formulaire génère cependant un avertissement avec C99 et ne compile pas en tant que code C ++ valide.

Java 7, 39 ou peut-être 44 octets

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 récursion! Je devais utiliser un!= comparaison au lieu d'une comparaison plus courte pour ne pas déborder sur les entrées négatives, mais à part cela, c'est assez simple. Si c'est étrange, envoyez un zéro. Si même, ajoutez-en un et recommencez.

Il existe deux versions car, pour le moment, la sortie pour zéro est inconnue. Le premier recurse jusqu'à ce que la pile déborde et ne génère rien car 0 est infiniment pair. La seconde crache un joli 0, sûr, mais probablement non rigoureux mathématiquement, pour la sortie.

JavaScript (ES6), 20 octets 19 octets.

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

Ceci est un portage de la solution Haskell de @nimi to JavaScript. Il utilise les propriétés "court-circuit" &&dont renvoie son côté gauche s'il s'agit de falsey (ce qui est dans ce cas -0) ou son autre côté. Pour mettre en œuvre, odd x = 0nous faisons donc le côté gauche 1 - (x % 2)qui bouillonne à 0travers le &&, sinon nous retournons à 1 + f(x / 2).

Le rasage de 1 - (x % 2)as (~x) % 2est dû à @Neil ci-dessous et présente la propriété étrange qui permet à la fonction ci-dessus d'être émise -0pour de petits nombres impairs. Cette valeur est une particularité de la décision de JS selon laquelle les entiers sont des doubles IEEE754; ce système a un séparé +0et -0qui sont spécialement conçus en JavaScript pour être l'un ===pour l'autre. L' ~opérateur calcule l'inversion binaire sur le nombre entier signé de 32 bits pour le nombre, qui pour les petits nombres impairs sera un nombre pair négatif. (Le nombre positif Math.pow(2, 31) + 1par exemple produit 0plutôt que -0.) La restriction étrange aux nombres entiers signés 32 bits n'a aucun autre effet; en particulier cela n'affecte pas la correction.

Perl 6, 23 18 octets

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

usage

> 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 octets

Ma première soumission de golf de code (yey!)

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

Comment je suis arrivé ici :

Tout d'abord, je souhaitais obtenir un code conforme aux spécifications afin de comprendre le problème. J'ai donc construit la méthode sans tenir compte du nombre d'octets:

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

Fort de cette connaissance, j'ai décompressé la fonction dans une boucle while et ajouté $*(ARGV) comme entrée et i comme nombre de fois que le nombre a été divisé par deux avant de devenir impair.

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

J'étais assez fier de cela et je l'avais presque soumis avant de me rendre compte que toute cette division par deux me semblait un peu binaire, étant un ingénieur en logiciel mais pas tellement un informaticien, ce n'était pas la première chose à laquelle on a pensé.

J'ai donc rassemblé quelques résultats sur les valeurs d'entrée en binaire:

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

J'ai remarqué que le résultat était le nombre de positions à gauche que nous devons parcourir avant que le nombre ne devienne impair.

En faisant quelques manipulations simples de chaîne, j'ai divisé la chaîne à la dernière occurrence de 1 et compté la longueur des 0 restants:

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

en utilisant le ("%b" % x)formatage pour convertir un nombre en binaire, et String # slice pour trancher ma chaîne.

J'ai appris quelques choses sur le rubis au cours de cette quête et j'ai hâte de voir d'autres golfs bientôt!

J, 6 octets

1&q:@|

Explication:

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

C, 37 octets

f(int x){return x?x&1?0:1+f(x/2):0;} Vérifiez récursivement le dernier bit jusqu'à ce que ce ne soit pas un 0.

Haskell, 28 octets

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

Exemple d'utilisation: f 94208-> 12.

Si le nombre est impair, le résultat est 0, sinon, 1plus un appel récursif avec la moitié du nombre.

Befunge, 20

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

L’exécution du code continue de se déplacer vers la droite et d’enrouler autour du deuxième caractère de la première ligne (grâce au tirant arrière #) jusqu’à la 2%sortie 1, ce qui entraîne _le changement de direction vers la gauche, puis |vers le haut, qui encercle <la deuxième ligne, qui sorties et sorties. Nous incrémentons chaque élément de la pile à travers la boucle, puis divisons le sommet par 2.

Rétine ,29 17

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

Essayez-le en ligne!

2 octets sauvés grâce à Martin!

Prend une entrée unaire. Cela correspond de manière répétée à la plus grande quantité de 1s possible, de sorte que le nombre de 1s corresponde exactement au reste des 1s du nombre. Chaque fois qu'il le fait, il ajoute un a ;à la chaîne. À la fin, nous comptons le nombre de ;s dans la chaîne.

Si vous voulez une entrée décimale, ajoutez:

\d+
$0$*1

au début du programme.

Jolf, 6 octets

Essayez-le ici!

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

Plutôt simple ... Félicitations à ETHProductions pour avoir évincé Jolf de la version qui devrait vraiment fonctionner!

PARI / GP, 17 octets

n->valuation(n,2)

6502 langage machine, 7 octets

Pour trouver la valeur de position du bit le moins significatif 1 de la valeur non nulle dans l'accumulateur, en laissant le résultat dans le registre X:

A2 FF E8 4A 90 FC 60

Pour exécuter ceci sur le simulateur 6502 sur e-tradition.net , préfixez -le A9suivi d'un entier de 8 bits.

Cela se désassemble comme suit:

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

Ceci est équivalent au C suivant, sauf que C requiert int avoir au moins 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;
}

La même chose fonctionne sur un 65816, en supposant que MX = 01 (accumulateur 16 bits, index 8 bits), et est équivalente à l’extrait C ci-dessus.

Brachylog , 27 15 octets

$pA:2xlL,Al-L=.

Explication

$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 octets

rizmf2e=

Lire un entier, une valeur absolue, factoriser en premier, compter deux.

JavaScript ES6, 36 38 octets

Golfé deux octets grâce à @ETHproductions

Réponse assez ennuyeuse, mais ça fait le travail. Peut-être en réalité trop semblable à une autre réponse, s’il ajoute les modifications suggérées, je supprimerai les miennes.

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

Pour l'exécuter, attribuez-le à une variable ( a=>{for...) car il s'agit d'une fonction anonyme, puis appelez-le avec a(100).

ES6, 22 octets

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

Retourne -1 si vous passez 0.

DUP , 20 octets

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

Try it here!

Converti en récursion, la sortie est maintenant le premier chiffre de la pile. Usage:

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

Explication

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

¢w b1

Testez-le en ligne!

La version précédente aurait dû être cinq octets, mais celle-ci fonctionne réellement.

Comment ça fonctionne

       // 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 octets

2 octets off merci @JohnWHSmith . 2 octets off merci @luserdroog .

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

Testez en direct sur ideone .