inspirado en Cuenta atrás desde el infinito

Dado un número entero no negativo N, genera el número de repeticiones de los siguientes pasos que se requieren para llegar a 0:

1. Convertir Na binario ( 4812390 -> 10010010110111001100110)
2. Voltear cada bit ( 10010010110111001100110 -> 01101101001000110011001)
3. Recortar ceros a la izquierda ( 01101101001000110011001 -> 1101101001000110011001)
4. Convertir de nuevo a decimal ( 1101101001000110011001 -> 3576217)

Reglas

• La entrada y la salida pueden estar en cualquier formato coherente y sin ambigüedades
• La entrada estará dentro del rango entero representable nativo para su idioma (si su idioma admite enteros arbitrariamente grandes, no hay límite)

Casos de prueba

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

Esta secuencia es A005811 en el OEIS.

Jalea , 6 4 bytes

^HBS

Pruébalo en línea! o verificar todos los casos de prueba .

Antecedentes

Sea n un número entero no negativo.

Los pasos 2 y 3 del proceso descrito en la especificación se pueden indicar alternativamente como eliminar todos los 1 principales y alternar los bits restantes.

Esto significa que eliminaremos exactamente un grupo de dígitos binarios adyacentes e iguales en cada iteración, por lo que la longitud de la cuenta regresiva binaria de n es solo el número de estos grupos en la representación binaria de n . Para los propósitos de este desafío, piense que 0 no tiene dígitos.

Para n = 8675309 , el proceso tiene el siguiente aspecto en binario.

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

En lugar de contar estos grupos (que fallarían para el caso límite 0 ), hacemos lo siguiente.

n y n: 2 tienen las siguientes representaciones binarias.

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

Tenga en cuenta que la representación binaria de n: 2 es simplemente n 's, desplazada un bit a la izquierda.

Si hacemos XOR n y n: 2 , obtendremos un 1 (MSB) y un 1 adicional por cada par de dígitos adyacentes diferentes. El número de grupos es, por lo tanto, igual al número de bits establecidos en n ⊻ n: 2 .

Cómo 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')

Pruébalo en Ideone .

Antecedentes

Sea n un número entero no negativo.

Los pasos 2 y 3 del proceso descrito en la especificación se pueden indicar alternativamente como eliminar todos los 1 principales y alternar los bits restantes.

Esto significa que eliminaremos exactamente un grupo de dígitos binarios adyacentes e iguales en cada iteración, por lo que la longitud de la cuenta regresiva binaria de n es solo el número de estos grupos en la representación binaria de n . Para los propósitos de este desafío, piense que 0 no tiene dígitos.

Para n = 8675309 , el proceso tiene el siguiente aspecto en binario.

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

En lugar de contar estos grupos (que fallarían para el caso límite 0 ), hacemos lo siguiente.

n y n: 2 tienen las siguientes representaciones binarias.

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

Tenga en cuenta que la representación binaria de n: 2 es simplemente n 's, desplazada un bit a la izquierda.

Si hacemos XOR n y n: 2 , obtendremos un 1 (MSB) y un 1 adicional por cada par de dígitos adyacentes diferentes. El número de grupos es, por lo tanto, igual al número de bits establecidos en n ⊻ n: 2 .

Python 2, 29 bytes

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

Cuenta el número de alternancias entre 0 y 1 en la expansión binaria, contando el 1 inicial como una alternancia. Para ello, verifica si los dos últimos dígitos binarios son diferentes, y luego vuelve al número con el último dígito eliminado. Los dos últimos dígitos son diferentes exactamente si n%4es 1 o 2, lo que se puede verificar como -n%4/2.

JavaScript (ES6), 26 bytes

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

Funciona contando las transiciones entre 0 y 1. Solo funciona hasta 31 bits. 29 bytes para admitir 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

Guardado 2 bytes gracias a Dennis .

b0ÛÔg

Sin el caso de borde de 0 esto podría ser 3 bytes bÔg.

Pruébalo en línea! o como un conjunto de pruebas

Explicación

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

CJam , 14 bytes

ri0{2b:!2bj)}j

Pruébalo en línea!

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

Básicamente un golpe de mi respuesta a la otra pregunta.

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

Idea 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~:/\#:

Cuenta el número de ejecuciones en los dígitos binarios de n con el caso especial que devuelve 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

Explicación

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

¡Gracias a @Dennis por guardar un byte!

ri_2be`,e&

Pruébalo en línea!

Explicación

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

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

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

Pruebas:

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

Salida:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 bytes

BY'nwa*

Pruébalo en línea!

Explicación

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

Aquí está la salida xxd con los caracteres no imprimibles 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

Pruébalo en línea!

Explicación

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

Rubí, 26 bytes

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

Inspirado por la respuesta de Python de xnor.

PHP, 64 bytes

basado en mi solución de cuenta regresiva

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

imprime tiempos de 1caracteres k, donde kes el número de iteraciones.

+4 bytes para salida entera: (salida vacía para 0)

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

JavaScript (ES6), 44

Función recursiva

Limitado a entero positivo javascript, 31 bits:

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

Gestión de números de doble precisión de hasta 53 bits significativos - 59 bytes:

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

De otra manera: usando el sorprendente algoritmo de @Dennis, función no recursiva que administra hasta 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);

Utiliza una expresión regular para contar el número de ejecuciones de 1 o 0. Desafortunadamente, esto necesita un caso especial para la entrada 0que requiere 3 bytes adicionales (y da un aviso).

Java 7, 71 bytes

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

Sé que esto es superado por la splitsolución de Geobits (que eventualmente se publicará), pero aún así fue divertido escribir

Octava, 47 bytes

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

Según la entrada de OEIS, el valor que estamos buscando como solución a este desafío también es igual al número de 1s en el código Gray para el entero dado.

Wikipedia me dice que el código Gray se puede calcular como x ^ (x >> 1), por lo que en la función anterior calculo el código Gray como tal, lo convierto en una cadena binaria y cuento cuántos dígitos de esa cadena son 1.

Java 7, 64 bytes

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

Sé que esto podría ser superado por un puerto de una de las mejores respuestas, pero se me ocurrió en el chat, y no puedo no publicar después del empuje dijo algo al respecto :)

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 los casos de prueba (por mucho que no quiera incluir la palabra sin firmar o el último caso de prueba) ...

Bash, 57 bytes

Paquetes: Core Utilibilidades, grep, sed, vim (para xxd )

Suponga que el número se da en formato binario. Cualquier longitud es aceptable :)

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

Pruébalo en línea!

Usando el 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}

Pruébalo en línea!

Todavía no me gusta mucho para mi gusto