inspirado pela contagem regressiva do infinito

Dado um número inteiro não negativo N, imprima o número de repetições das seguintes etapas necessárias para atingir 0:

1. Converta Nem binário ( 4812390 -> 10010010110111001100110)
2. Virar cada bit ( 10010010110111001100110 -> 01101101001000110011001)
3. Cortar zeros à esquerda ( 01101101001000110011001 -> 1101101001000110011001)
4. Converter de volta para decimal ( 1101101001000110011001 -> 3576217)

Regras

• Entrada e saída podem estar em qualquer formato inequívoco e consistente
• A entrada estará dentro do intervalo inteiro representável nativo do seu idioma (se o seu idioma suportar números inteiros arbitrariamente grandes, não haverá limite)

Casos de teste

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

Essa sequência é A005811 no OEIS.

Geléia , 6 4 bytes

^HBS

Experimente online! ou verifique todos os casos de teste .

fundo

Seja n um número inteiro não negativo.

Passos 2 e 3 do processo descrito na especificação pode, alternativamente, ser indicado como a remoção de todos os principais 1 's e alternando os restantes bits.

Isso significa que removeremos exatamente um grupo de dígitos binários adjacentes e iguais em cada iteração; portanto, o Comprimento da contagem regressiva binária de n é apenas o número desses grupos na representação binária de n . Para os propósitos deste desafio, pense em 0 como não tendo dígitos.

Para n = 8675309 , o processo parece da seguinte forma em binário.

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

Em vez de contar esses grupos (o que falharia no caso 0 de extremidade ), fazemos o seguinte.

n e n: 2 têm as seguintes representações binárias.

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

Observe que a representação binária de n: 2 é simplesmente n , deslocada um bit para a esquerda.

Se XOR n e n: 2 , obteremos 1 (MSB) e 1 adicional para cada par de dígitos adjacentes diferentes. O número de grupos é, portanto, igual ao número de bits definidos em n ⊻ n: 2 .

Como funciona

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

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

Teste em Ideone .

fundo

Seja n um número inteiro não negativo.

Passos 2 e 3 do processo descrito na especificação pode, alternativamente, ser indicado como a remoção de todos os principais 1 's e alternando os restantes bits.

Isso significa que removeremos exatamente um grupo de dígitos binários adjacentes e iguais em cada iteração; portanto, o Comprimento da contagem regressiva binária de n é apenas o número desses grupos na representação binária de n . Para os propósitos deste desafio, pense em 0 como não tendo dígitos.

Para n = 8675309 , o processo parece da seguinte forma em binário.

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

Em vez de contar esses grupos (o que falharia no caso 0 de extremidade ), fazemos o seguinte.

n e n: 2 têm as seguintes representações binárias.

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

Observe que a representação binária de n: 2 é simplesmente n , deslocada um bit para a esquerda.

Se XOR n e n: 2 , obteremos 1 (MSB) e 1 adicional para cada par de dígitos adjacentes diferentes. O número de grupos é, portanto, igual ao número de bits definidos em n ⊻ n: 2 .

Python 2, 29 bytes

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

Conta o número de alternâncias entre 0 e 1 na expansão binária, contando o 1 inicial como uma alternância. Faz isso verificando se os dois últimos dígitos binários são diferentes e, em seguida, recorrendo ao número com o último dígito removido. Os dois últimos dígitos são diferentes exatamente se n%4for 1 ou 2, que pode ser marcado como -n%4/2.

JavaScript (ES6), 26 bytes

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

Funciona contando as transições entre 0 e 1. Funciona apenas até 31 bits. 29 bytes para suportar 53 bits:

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

Haskell, 34 bytes

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

05AB1E , 7 5 bytes

Economizou 2 bytes graças a Dennis .

b0ÛÔg

Sem a aresta de 0, isso pode ser de 3 bytes bÔg.

Experimente online! ou como um conjunto de testes

Explicação

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

CJam , 14 bytes

ri0{2b:!2bj)}j

Experimente online!

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

Basicamente, uma imitação da minha resposta à outra pergunta.

Java 7,112 108 100 90 73 bytes

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);}

Ideia básica

 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 bytes

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

Conta o número de execuções nos dígitos binários de n com o caso especial retornando 0 para n = 0.

Uso

   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

Explicação

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

Obrigado a @Dennis por salvar um byte!

ri_2be`,e&

Experimente online!

Explicação

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

Raquete 349 bytes

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

Ungolfed:

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

Teste:

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

Resultado:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 bytes

BY'nwa*

Experimente online!

Explicação

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

-3 bytes graças a 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

Aqui está a saída xxd com os caracteres não imprimíveis intactos:

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

Experimente online!

Explicação

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

Ruby, 26 bytes

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

Inspirado pela resposta Python do xnor.

PHP, 64 bytes

com base na minha solução de contagem regressiva

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

imprime 1caracteresk tempos dos , onde ké o número de iterações.

+4 bytes para saída inteira: (saída vazia para 0)

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

JavaScript (ES6), 44

Função recursiva

Limitado ao número inteiro positivo javascript, 31 bits:

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

Gerenciando número de precisão dupla até 53 bits significativos - 59 bytes:

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

De outra maneira: usando o incrível algoritmo de @Dennis, função não recursiva gerenciando 53 bits, 43 bytes:

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

PHP, 51 bytes

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

Usa um regex para contar o número de execuções de 1 ou 0. Infelizmente, isso precisa de um caso especial para a entrada 0que requer 3 bytes adicionais (e fornece um aviso).

Java 7, 71 bytes

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

Eu sei que isso é derrotado pela solução do Geobitssplit (que será publicada), mas ainda assim foi divertido escrever

Oitava, 47 bytes

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

De acordo com a entrada da OEIS, o valor que procuramos como solução para este desafio é também igual ao número de1 s no código Gray para o número inteiro especificado.

A Wikipedia me diz que o código Gray pode ser calculado como x ^ (x >> 1), portanto, na função acima, calculo o código Gray como tal, converto-o em uma string binária e conto quantos dígitos dessa string 1.

Java 7, 64 bytes

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

Eu sei que isso pode ser derrotado por um porto de uma das melhores respostas, mas eu criei isso no chat e não consigo postá-lo depois que Poke disse algo sobre isso :)

C, 76 bytes

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;}

Funciona para todos os casos de teste (por mais que eu não queira incluir a palavra não assinado ou o último caso de teste) ...

Bash, 57 bytes

Pacotes: Utilitários Principais, grep, sed, vim (para xxd )

Suponha que o número seja fornecido em formato binário. Qualquer comprimento é aceitável :)

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

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

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

Experimente online!

Usando o método de @ Dennis.

Tcl , 119 bytes

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}

Experimente online!

Ainda muito destruída pelo meu gosto