inspiré par Count down from infinity

Étant donné un entier non négatif N, affichez le nombre de répétitions des étapes suivantes pour atteindre 0:

1. Convertir Nen binaire ( 4812390 -> 10010010110111001100110)
2. Retournez chaque bit ( 10010010110111001100110 -> 01101101001000110011001)
3. Couper les zéros non significatifs ( 01101101001000110011001 -> 1101101001000110011001)
4. Convertir en décimal ( 1101101001000110011001 -> 3576217)

Règles

• L'entrée et la sortie peuvent être dans n'importe quel format cohérent et sans ambiguïté
• L'entrée sera dans la plage entière représentable native pour votre langue (si votre langue prend en charge des entiers arbitrairement grands, il n'y a pas de limite)

Cas de test

0 -> 0
1 -> 1
42 -> 6
97 -> 3
170 -> 8
255 -> 1
682 -> 10
8675309 -> 11
4812390 -> 14
178956970 -> 28
2863311530 -> 32

Cette séquence est A005811 dans l'OEIS.

Gelée , 6 4 octets

^HBS

Essayez-le en ligne! ou vérifiez tous les cas de test .

Contexte

Soit n un entier non négatif.

Les étapes 2 et 3 du processus décrit dans la spécification peuvent également être déclarées comme supprimant tous les 1 en tête et basculant les bits restants.

Cela signifie que nous supprimerons exactement un groupe de chiffres binaires adjacents et égaux à chaque itération, donc la longueur du compte à rebours binaire de n est juste le nombre de ces groupes dans la représentation binaire de n . Aux fins de ce défi, pensez à 0 comme n'ayant pas de chiffres.

Pour n = 8675309 , le processus se présente comme suit en binaire.

100001000101111111101101
 11110111010000000010010
     1000101111111101101
      111010000000010010
         101111111101101
          10000000010010
           1111111101101
                   10010
                    1101
                      10
                       1
                       0

Au lieu de compter ces groupes (ce qui échouerait pour le cas de bord 0 ), nous procédons comme suit.

n et n: 2 ont les représentations binaires suivantes.

n   = 8675309 = 100001000101111111101101_2
n:2 = 4337654 =  10000100010111111110110_2

Notez que la représentation binaire de n: 2 est simplement n , décalée d'un bit vers la gauche.

Si nous XOR n et n: 2 , nous obtiendrons un 1 (MSB) et un 1 supplémentaire pour chaque paire de chiffres adjacents différents. Le nombre de groupes est donc égal au nombre de bits mis en n ⊻ n: 2 .

Comment ça fonctionne

^HBS  Main link. Argument: n

 H    Halve; yield n:2.
^     XOR n with n:2.
  B   Convert the result to binary.
   S  Compute the sum of the resulting binary digits.

Python 2, 30 octets

lambda n:bin(n^n/2).count('1')

Testez-le sur Ideone .

Contexte

Soit n un entier non négatif.

Les étapes 2 et 3 du processus décrit dans la spécification peuvent également être déclarées comme supprimant tous les 1 en tête et basculant les bits restants.

Cela signifie que nous supprimerons exactement un groupe de chiffres binaires adjacents et égaux à chaque itération, donc la longueur du compte à rebours binaire de n est juste le nombre de ces groupes dans la représentation binaire de n . Aux fins de ce défi, pensez à 0 comme n'ayant pas de chiffres.

Pour n = 8675309 , le processus se présente comme suit en binaire.

100001000101111111101101
 11110111010000000010010
     1000101111111101101
      111010000000010010
         101111111101101
          10000000010010
           1111111101101
                   10010
                    1101
                      10
                       1
                       0

Au lieu de compter ces groupes (ce qui échouerait pour le cas de bord 0 ), nous procédons comme suit.

n et n: 2 ont les représentations binaires suivantes.

n   = 8675309 = 100001000101111111101101_2
n:2 = 4337654 =  10000100010111111110110_2

Notez que la représentation binaire de n: 2 est simplement n , décalée d'un bit vers la gauche.

Si nous XOR n et n: 2 , nous obtiendrons un 1 (MSB) et un 1 supplémentaire pour chaque paire de chiffres adjacents différents. Le nombre de groupes est donc égal au nombre de bits mis en n ⊻ n: 2 .

Python 2, 29 octets

f=lambda n:n and-n%4/2+f(n/2)

Compte le nombre d'alternances entre 0 et 1 dans l'expansion binaire, en comptant le 1 en tête comme une alternance. Le fait en vérifiant si les deux derniers chiffres binaires sont différents, puis en revenant sur le numéro avec le dernier chiffre supprimé. Les deux derniers chiffres sont exactement différents si n%4est 1 ou 2, ce qui peut être vérifié comme -n%4/2.

JavaScript (ES6), 26 octets

f=n=>n&&(n^(n>>=1))%2+f(n)

Fonctionne en comptant les transitions entre 0 et 1. Fonctionne uniquement jusqu'à 31 bits. 29 octets pour prendre en charge 53 bits:

f=n=>1<=n&&(n%2^n/2%2)+f(n/2)

Haskell, 34 octets

b 0=0
b n|x<-b$div n 2=x+mod(x+n)2

05AB1E , 7 5 octets

Enregistré 2 octets grâce à Dennis .

b0ÛÔg

Sans le cas de bord de 0, cela pourrait être de 3 octets bÔg.

Essayez-le en ligne! ou comme suite de tests

Explication

b      # convert to binary
 0Û    # trim off leading zeroes
   Ô   # remove adjacent duplicates
    g  # length

CJam , 14 octets

ri0{2b:!2bj)}j

Essayez-le en ligne!

ri      e# read integer
0       e# value for terminal case
{       e# recursive function
  2b    e#   create binary representation with no leading zeros
  :!    e#   flip bits
  2b    e#   convert binary back to integer
  j     e#   recursive call
  )     e#   increment from 0 on the way up
}j      e# end

Fondamentalement, un coup de ma réponse à l'autre question.

Java 7,112 108 100 90 73 octets

int c(int i){int l=1,j=i;for(;(j=j/2)>0;l*=2);return i<1?0:1+c(2*l-1-i);}

Idée basique

 Lets take an no 10110(21)
 then you do set all bits in no 21 and you will get 11111
 and after that you would subtract the original number from 11111.
 You will get 01001 and loop it until you will get 0

J, 14 octets

**1+/@,2~:/\#:

Compte le nombre d'exécutions dans les chiffres binaires de n avec le cas spécial retournant 0 pour n = 0.

Usage

   f =: **1+/@,2~:/\#:
   (,.f"0) 0 1 42 97 170 255 682 8675309 4812390 178956970 2863311530
         0  0
         1  1
        42  6
        97  3
       170  8
       255  1
       682 10
   8675309 11
   4812390 14
 178956970 28
2863311530 32

Explication

**1+/@,2~:/\#:  Input: integer n
            #:  Get the binary digits of n
       2   \    For each overlapping sublist of size 2
        ~:/       Reduce by not-equals
  1   ,         Prepend a 1
   +/@          Reduce by addition
*               Sign(n), returns 0 for n = 0 else 1
 *              Multiply with the previous sum and return

CJam , 11 10 octets

Merci à @Dennis d'avoir enregistré un octet!

ri_2be`,e&

Essayez-le en ligne!

Explication

ri            #e Read as integer
              #e STACK: 97
  _           #e Duplicate
              #e STACK: 97, 97
   2b         #e Convert to binary
              #e STACK: 97, [1 1 0 0 0 0 1]
     e`       #e Run-length encoding
              #e STACK: 97, [[2 1] [4 0] [1 1]]
       ,      #e Length
              #e STACK: 97, 3
        e&    #e Return first value if 0, or else the second value
              #e STACK: 3

Raquette 349 octets

(define(h s)(apply string(map(λ(x)(if(eq? x #\0)#\1 #\0))(string->list s))))(define(g s)(let*
((l(string-length s))(k(for/list((i s)(n l)#:final(not(equal? i #\0)))n)))(substring s(last k))))
(define(f n)(if(= 0 n)0(begin(let loop((n n)(c 1))(define m(string->number(string-append "#b"
(g(h(number->string n 2))))))(if(> m 0)(loop m(add1 c))c))))

Non golfé:

(define (invertBinary s)
  (apply string
         (map
          (λ(x)(if(eq? x #\0)#\1 #\0))
          (string->list s))))

(define (trimLeading0s s)
  (let* ((l (string-length s))
         (k (for/list ((i s)
                       (n l)
                       #:final (not(equal? i #\0)))
              n)))
    (substring s (last k))))

(define (f n)
  (if (= 0 n) 0
      (begin
        (let loop ((n n)
                   (c 1))
          (define m 
            (string->number
             (string-append
              "#b"
              (trimLeading0s
               (invertBinary
                (number->string n 2))))))

          (if (> m 0)
              (loop m (add1 c))
              c)))))

Essai:

(f 0)
(f 1)
(f 42)
(f 97)
(f 170)
(f 255)
(f 682)
(f 8675309)
(f 4812390)
(f 178956970)
(f 2863311530)

Production:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 octets

BY'nwa*

Essayez-le en ligne!

Explication

          % Implicit input, for example 97
          % STACK: 97
B         % Convert to binary
          % STACK: [1 1 0 0 0 0 1]
 Y'       % Run-length encoding
          % STACK: [1 0 1], [2 4 1]
   n      % Number of elements
          % STACK: [1 0 1], 3
    w     % Swap
          % STACK: 3, [1 0 1]
     a    % Any: gives 1 if any element is nonzero
          % STACK: 3, 1
      *   % Multiply
          % STACK: 3
          % Implicit display

Vim, 62 59 octets

-3 octets grâce à DJMcMayhem

C0
<C-r>=pri<Tab>'%b',<C-r>")
<Esc>0qqC<C-r>=tr(@",'01','10')
<Esc>:s/^0\+
k<C-a>j@qq@q

Voici la sortie xxd avec les caractères non imprimables intacts:

0000000: 4330 0d12 3d70 7269 0927 2562 272c 1222  C0..=pri.'%b',."
0000010: 290d 1b30 7171 4312 3d74 7228 4022 2c27  )..0qqC.=tr(@",'
0000020: 3031 272c 2731 3027 290d 1b3a 732f 5e30  01','10')..:s/^0
0000030: 5c2b 0d6b 016a 4071 7140 71              \+.k.j@qq@q

Essayez-le en ligne!

Explication

C                                   " Delete the number (it goes in @")
0<CR>                               " Print 0 (our counter) and a carriage return
<C-r>=pri<Tab>'%b',<C-r>")<CR><Esc> " Use `printf()` to insert the number as base 2
0qq                                 " Return to column 0, start recording a macro
  C<C-r>=tr(@",'01','10')<CR><Esc>  "   Replace 0s with 1s and vice versa
  :s/^0\+<CR>                       "   Delete leading 0s
  k<C-a>                            "   Increment the number on the line above
  j                                 "   Return to the previous line
  @q                                "   Invoke macro recursively
q@q                                 " Stop recording and invoke macro

Rubis, 26 octets

f=->n{n<1?0:-n%4/2+f[n/2]}

Inspiré par la réponse Python de xnor.

PHP, 64 octets

basé sur ma solution de compte à rebours

for($n=$argv[1];$n;print 1)$n=bindec(strtr(decbin($n),"01",10));

imprime les temps des 1caractères k, où kest le nombre d'itérations.

+4 octets pour la sortie entière: (sortie vide pour 0)

for($n=$argv[1];$n;$i++)$n=bindec(strtr(decbin($n),"01",10));echo$i;

JavaScript (ES6), 44

Fonction récursive

Limité à un entier positif javascript, 31 bits:

f=(a,s=0)=>a?f((-1>>>Math.clz32(a))-a,s+1):s

Gestion du nombre double précision jusqu'à 53 bits significatifs - 59 octets:

F=(a,s=0)=>a?F('0b'+a.toString(2).replace(/./g,1)-a,s+1):s

D'une autre manière: en utilisant l'algorithme étonnant de @Dennis, fonction non récursive gérant jusqu'à 53 bits, 43 octets:

a=>a&&a.toString(2).match(/(.)\1*/g).length

PHP, 51 octets

<?=preg_match_all('/(1+|0+)/',decbin($argv[1])?:o);

Utilise une expression régulière pour compter le nombre d'exécutions de 1 ou 0. Malheureusement, cela nécessite un cas spécial pour l'entrée de 0qui nécessite 3 octets supplémentaires (et donne un avis).

Java 7, 71 octets

int b(Long a){return a==0?0:1+b(~a&-1L>>>64-a.toString(a,2).length());}

Je sais que cela est battu par la splitsolution de Geobits (qui sera finalement publiée) mais c'était toujours amusant à écrire

Octave, 47 octets

@(x)(sum(dec2bin(bitxor(x,idivide(x,2)))=='1'))

Selon l'entrée OEIS, la valeur que nous recherchons comme solution à ce défi est également égale au nombre de1 s dans le code Gray pour l'entier donné.

Wikipedia me dit que le code Gray peut être calculé comme x ^ (x >> 1), donc dans la fonction ci-dessus, je calcule le code Gray en tant que tel, le convertis en une chaîne binaire et compte le nombre de chiffres de cette chaîne 1.

Java 7, 64 octets

long g(Long n){return n.toString(n,2).split("0+").length*2-n%2;}

Je sais que cela pourrait être battu par un port d'une des meilleures réponses, mais je l'ai trouvé dans le chat, et je ne peux pas ne pas le poster après que Poke en ait parlé :)

C, 76 octets

unsigned n,m,i;f(x){for(i=0;x;x^=m-1,i++)for(n=x,m=2;n>>=1;m<<=1);return i;}

Fonctionne pour tous les cas de test (autant que je ne veux pas inclure le mot non signé ou dernier cas de test) ...

Bash, 57 octets

Paquets: Core Utililities, grep, sed, vim (pour xxd)

Supposons que le nombre soit donné au format binaire. Toute longueur est acceptable :)

xxd -b -c1|cut -d" " -f2|sed s/^0*//|grep -o .|uniq|wc -l

Perl 5 , 31 + 1 ( p) = 32 octets

$_=(sprintf'%b',$_^$_/2)=~y/1//

Essayez-le en ligne!

Utilisation de la méthode de @ Dennis.

Tcl , 119 octets

proc D n i\ 0 {
while \$n {set n [regsub ^0+(?=.) [string map {0 1 1 0} [format %b $n]] ""]
incr i
scan $n %b n}
set i}

Essayez-le en ligne!

Encore très dépourvu de goût