Para encontrar la dureza digitales de un entero, tome su representación binaria, y contar el número de veces que tanto uno de los principales y de arrastre 1puede ser retirado hasta que o bien se inicia o termina con una 0. El número total de bits eliminados es su dureza digital.

Esa es una explicación bastante prolija, así que analicemos con un ejemplo trabajado.

Para este ejemplo, usaremos el número 3167. En binario, esto es:

110001011111

(Tenga en cuenta que, durante la conversión a binario, debe asegurarse de eliminar los ceros iniciales)

No comienza ni termina con 0, por lo que eliminamos 1 par de bits:

1  1000101111  1

Y otro:

11  00010111  11

Pero ahora hay un 0 al principio, por lo que no podemos eliminar más 1pares. En total, eliminamos 4 bits, por lo que 4 es la dureza digital de 3167.

Sin embargo, para los números que pueden escribirse como 2 ⁿ -1 para n positivo (es decir, contener solo 1en representación binaria), nunca se alcanzará 0, por lo que todos los bits se pueden eliminar. Esto significa que la dureza es simplemente la longitud de bits del entero.

El reto

Su tarea es escribir un programa o función que, dado un número entero no negativo n >= 0, determine su dureza digital.

Puede enviar un programa completo que realice E / S o una función que devuelva el resultado. Su envío debe funcionar para valores ndentro del rango entero estándar de su idioma.

Casos de prueba

Notifíqueme si alguno de estos es incorrecto o si desea sugerir algún caso marginal para agregar.

0     -> 0
1     -> 1
8     -> 0
23    -> 2
31    -> 5
103   -> 4
127   -> 7
1877  -> 2
2015  -> 10

Aquí está la solución de Python sin golf que utilicé para generar estos casos de prueba (no se garantiza que no tengan errores):

def hardness(num) -> int:
    binary = bin(num)[2:]

    if binary.count('0') == 0:
        return num.bit_length()

    revbin = binary[::-1]

    return min(revbin.find('0'), binary.find('0')) * 2

Jalea , 11 10 bytes

BµQL××Ṛa\S

Pruébalo en línea!

Cómo funciona

BµQL××Ṛa\S  Main link. Argument: n

B           Binary; convert n to base 2.
 µ          Begin a new, monadic chain. Argument: A (array of binary digits)
  Q         Unique; deduplicate the digits.
   L        Length; count the unique digits.
    ×       Multiply each digit by the result.
     ×Ṛ     Multiply the results by reversed A.
       a\   Cumulative reduce by logical AND.
            This zeroes out all elements after the first zero.
         S  Compute the sum of the result.

Python , 76 69 68 63 62 60 57 bytes

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

Pruébalo en línea!

Cómo funciona

Esta es una solución recursiva que toma una entrada ny sigue incrementando k , comenzando en 0 , mientras que LSB _k (n) (bit en el índice k desde la derecha) y MSB _k (n) (bit en el índice k desde la izquierda) se establecen. Una vez finalizado, devuelve k si todos los bits de n están establecidos y 2k si no.

Comencemos reescribiendo la lambda f como una función con nombre F , con una variable auxiliar t .

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

En cada invocación de F , primero desplazamos un bit n un total de k unidades a la derecha y almacenamos el resultado en t . De esta manera, LSB ₀ (t) = LSB _k (n) , entonces t es impar si y solo si LSB _k (n) está configurado.

Determinar si MSB _k (n) está configurado es un poco más complicado; Esto es lo que se n & t > t >> 1logra. Para ilustrar cómo funciona, consideremos un número entero n = 1αβγδεζη ₂ de longitud de bit 8 y analicemos la llamada a la función F (n, 3) , es decir, k = 3 .

Estamos tratando de determinar si MSB ₃ (n) = γ se establece examinando el valor de verdad de la comparación (n & t> t >> 1) = (1αβγδεζη ₂ & 1αβγδ ₂ > 1αβγ ₂ ) . Examinemos los enteros involucrados.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

Afirmamos que γ = 1 si y solo si n & t> t >> 1 .

• Si γ = 1 , entonces n & t tiene una longitud de bits 5 mientras que t >> 1 tiene una longitud de bits 4 , entonces n & t> t >> 1 .

  Esto prueba que γ = 1 implica n & t> t >> 1 .

• Si n & t> t >> 1 , hay dos opciones: γ = 1 o γ = 0 . En el primer caso, no queda nada que demostrar.

  En el segundo caso, tenemos que αβγδ ₂ ≥ n & t> t >> 1 = 1αβγ ₂ .

  Como αβγδ ₂ > 1αβγ ₂ , debemos tener MSB ₀ (αβγδ ₂ ) ≥ MSB ₀ (1αβγ ₂ ) , lo que significa que α = 1 .

  De esta manera, 1βγδ ₂ > 11βγ ₂ , por lo que debemos tener MSB ₁ (1βγδ ₂ ) ≥ MSB ₁ (11βγ ₂ ) , lo que significa que β = 1 .

  A su vez, esto implica que 11γδ ₂ > 111γ ₂ . Recordando que γ = 0 en el segundo caso, obtenemos la desigualdad 110δ ₂ > 1110 ₂ , lo cual es falso ya que MSB ₂ (110δ ₂ ) = 0 <1 = MSB ₂ (1110 ₂ ) .

  Por lo tanto, solo el primer caso es posible y n & t> t >> 1 implica γ = 1 .

En resumen, si ambos LSB _k (n) y MSB _k (n) se establecen, t será par y n & t> t >> 1 será verdadera , por lo que t & (n & t> t >> 1) se rendimiento 1 . Sin embargo, si LSB _k (n) o MSB _k (n) está desarmado (o si ambos lo están), t será par o n & t> t >> 1 será Falso , entonces t & (n & t> t> > 1) producirá 0 .

Llamar a F con un solo argumento inicializa k = 0 . Si bien la condición que hemos discutido anteriormente se mantiene, el código posterior andse ejecuta, lo que (entre otras cosas) llama recursivamente F con k incrementado .

Una vez que LSB _k (n) o MSB _k (n) se desarma, la condición falla y F (n, k) devuelve 0 . Cada una de las llamadas a funciones k anteriores agrega (n & (n + 1)> 0) + 1 a F (n, k) = 0 , por lo que F (n) devuelve ((n & (n + 1)> 0) + 1) k .

Ahora, si todos los bits de n son iguales (es decir, si n es 0 o todos sus bits están establecidos), n + 1 no tendrá ningún bit en común con n , entonces n & (n + 1) = 0 y F (n) devuelve k . Sin embargo, si n tiene bits establecidos y no establecidos, n & (n + 1)> 0 y F (n) devuelve 2k .

MATL , 13 12 bytes

Btv`6L&)}x@q

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

Explicación

El código repite cada dígito binario y cuenta cuántas veces es posible eliminar dos dígitos externos.

B        % Input number (implicit). Horizontal vector of binary digits
tv       % Duplicate and concatenate vertically
`        % Do...while
  6L&)   %   Flatten the array if needed (in column-major order), and split it
         %   into two subarrays: one with the inner entries, and another
         %   with the two outer entries. The latter will be used for deciding
         %   if the loop continues or is exited
}        % Finally (execute before exiting the loop)
  x      %   Delete last subarray of inner entries
  @q     %   Push last iteration index minus 1
         % End (implicit). The next iterarion is executed if the array at the
         % top of the stack is non-empty and only contains nonzero values. 
         % Otherwise the loop is exited, executing the "finally" block first
         % Display (implicit)

Python, 82 bytes

Siento que todavía se puede jugar golf, pero pasé un tiempo probando diferentes métodos y este fue el más corto.

def f(n):b=bin(n)[2:];x=min(b.find('0'),b[::-1].find('0'));print(x<0)*len(b)or x*2

Pruébalo en línea

Aunque esto funciona de manera similar al programa Python del OP, creé esto antes de que se publicara la pregunta, después de ver la pregunta en el Sandbox, que no contenía dicho programa.

Python 2, 66 bytes

s=bin(input())[2:].split('0')
print len(min(s[-1],s[0]))<<1%len(s)

Divide la representación binaria de la entrada en fragmentos de 1. Cuenta el número de 1 en la parte más pequeña de la primera y la última parte, luego la duplica, a menos que haya una sola parte que cuente dos veces.

PowerShell , 109 106 bytes

$a=[convert]::ToString($args[0],2)-split0;(((($b=$a[0].length),$a[-1].length|sort)[0]*2),$b)[$a.count-eq1]

Pruébalo en línea!

Toma de entrada $args[0], utiliza la llamada .NET para convertque toStringcon la base 2(es decir, hacer que sea binario), a continuación, -splitde que la cadena en 0s, tiendas que en $a. Importante tener en cuenta: la llamada .NET no devuelve ceros a la izquierda, por lo que el primer dígito siempre es un1 .

Por lo tanto, hay dos posibilidades: la cadena binaria son todas, o había al menos un cero. Diferenciamos entre aquellos con un pseudoternario indexado por $a.count-eq1. Si el binario tiene al menos un cero, el caso de la izquierda, tomamos el mínimo de la longitud de la primera [0]cadena de 1sy la última [-1]cadena (encontrada por |sorty luego [0]). El más corto de esos es la mayor cantidad de pares que podríamos eliminar, por lo que multiplicamos eso por 2. Tenga en cuenta que si la cadena binaria original termina en a 0, como para input 8, entonces [-1].lengthtambién será 0(ya que es una cadena vacía), que cuando se multiplica por 2sigue siendo 0.

De lo contrario, con la cadena binaria todas, tomamos solo $b(que previamente se estableció como la longitud de la primera [0]cadena, en este caso, la totalidad de la cadena binaria).

En cualquier situación, ese resultado se deja en la tubería y la salida es implícita.

JavaScript (ES6), 57 bytes

f=
n=>n.toString(2).replace(/^(1*)(.*(\1))?$/,'$1$3').length

<input oninput=o.value=1/this.value?f(+this.value):''><input id=o readonly>

Toma el binario e intenta hacer coincidir todos 1so, en su defecto, un número igual de iniciales y finales 1s.

Retina , 48 bytes

.+
$*
+`(1+)\1
$1o
o1
1
m(+`^1(.*)1$
xx¶$1
x|^1$

Pruébalo en línea

Explicación:

.+              # Convert to unary
$*
+`(1+)\1        # Convert to binary (but with `o` instead of `0` -- it's shorter)
$1o
o1
1
m(+`^1(.*)1$    # Replace pairs of surrounding ones with `xx`
xx¶$1
x|^1$,          # Count x's, including the possibility of a single remaining `1`

C #, 133 bytes

Función que devuelve dureza. Toma entero del argumento.

int h(int b){var n=Convert.ToString(b,2);for(b=0;;){if(n[0]+n[n.Length-1]==98)n=n.Substring(1,n.Length-2);else break;b+=2;}return b;}

Bueno, hoy me enteré '1' + '1' = 98en C #.

C, 89 88 85 bytes

Se guardaron dos bytes debido a que @FlipTack señalaba una declaración inútil.

Llame f()con el número para probar, la salida devuelve la función.

t,h;f(l){for(t=l;t&&~t&1<<30;t*=2);for(h=0;t&1<<30&&l&1;t*=2,l/=2)++h;return h<<!!l;}

Pruébalo con ideone .

JavaScript (ES6), 59 58 bytes

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

Casos de prueba

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

console.log(
  [0, 1, 8, 23, 31, 103, 127, 1877, 2015].map(
    n => n + ' -> ' + f(n)
  ).join('\n')
)

Jalea , 14 bytes

Eo2
BµŒg.ịṂS×Ç

Pruébalo en línea!

C, 137 132 122 119 117 114 98 94 92 87 85 Bytes

Hora de empezar a jugar al golf B-)

i,j;f(n){for(i=1<<30;i&~n;i/=2);for(j=0;n&i;n/=2,i/=4)j+=~n&1?i=0:2;return j-=n<1*j;}

Aquí está la prueba

main()
{
  printf("%d %d\n", 0, f(0));
  printf("%d %d\n", 1, f(1));
  printf("%d %d\n", 8, f(8));
  printf("%d %d\n", 23, f(23));
  printf("%d %d\n", 31, f(31));
  printf("%d %d\n", 103, f(103));
  printf("%d %d\n", 127, f(127));
  printf("%d %d\n", 1877, f(1877));
  printf("%d %d\n", 2015, f(2015));
  printf("%d %d\n", 3167, f(3167));
} 

y la salida;

0 0
1 1
8 0
23 2
31 5
103 4
127 7
1877 2
2015 10
3167 4 

Java (OpenJDK) , 181 156 150 bytes

n->{int i=0;String s=n.toString(n,2);if(s.matches("1*"))i=s.length();else for(;!s.matches("(.*0)|(0.*)");s=s.substring(1,s.length()-1))i+=2;return i;}

Pruébalo en línea!

Mathematica, 63 56 bytes

(2-Min[l=#~IntegerDigits~2])Min[Tr/@Split[l][[{1,-1}]]]&

Explicación

l=#~IntegerDigits~2

Genere la representación de base 2 de la entrada, envuelta con a List. Almacenar eso enl

(2-Min[...])

Si el elemento mínimo de les 1, salida 1. Si no, salida 2. Multiplique esto por ...

Split[l]

Dividir len carreras.

... [[{1,-1}]]

Toma el primer y el último elemento.

Tr/@ ...

Toma el total de ambos.

Min[ ... ]

Encuentra el más pequeño entre los dos.

(Multiplique el primer resultado (1 o 2) con este resultado).

Octava, 56 54 bytes

 @(n)cummin(d=dec2bin(n)-48)*cummin(flip(d))'*2^!all(d)

Pruébalo en línea!

Explicación:

d=dec2bin(n)-48

representación binaria de n

cumd= cummin(d);
cumfd = cummin(flip(d));

Tomar min acumulativo d y min acumulativo de volteadod

res = cumd * cumfd ';

hacer multiplicación de matrices

out = res*2^!all(d)

multiplique por 2 si todos los dígitos son 1;

Pyth, 18 bytes

?*FJjQ2lJyhSxR0_BJ

Un programa que toma la entrada de un número entero e imprime el resultado.

Conjunto de pruebas (primera línea para formatear)

Cómo funciona

?*FJjQ2lJyhSxR0_BJ  Program. Input: Q
?                   If
  F                 reducing
    jQ2             the binary representation of Q as a list
   J                (store in J)
 *                  by multiplication is truthy:
       lJ            Yield len(J)
                    Else:
          hS         Yield the minimum
            xR0      of the first index of zero
               _BJ   in J and its reverse
         y           * 2
                    Implicitly print

APL, 26 bytes

+/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢

Casos de prueba:

      ( +/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢ ) ¨ 0 1 8 23 31 103 127 1877 2015    
0 1 0 2 5 4 7 2 10

Explicación:

+ / ∘ (∧ \ ≢ ↑ (∊⊢ (, ∧∧) ¨⌽)) 2⊥⍣¯1⊢

                         ⊢ entrada
                    2⊥⍣¯1 convertir a representación binaria
   ()
        (⊢ ¨⌽) para cada bit y su bit correspondiente en el otro lado
            (∧) tome la lógica y de ambos bits,
             , haga una lista de ambos bits,
              ∧ luego toma el y de la lista y el y
         ∊ aplanar la matriz resultante
      ↑ ↑ tome solo los primeros N bits, donde N es el
                                longitud de la lista original de bits
    Take \ tomar un funcionamiento lógico y (dejando solo el
                                principiantes)
+ / ∘ suma esos

J, 22 bytes

(#<.2*(<.&(#.~)|.))@#:

Esto se basa en el ingenioso truco aprendido de este desafío .

Pruébalo en línea!

Explicación

(#<.2*(<.&(#.~)|.))@#:  Input: integer n
                    #:  Binary digits of n
(                 )@    Operate on those digits D
               |.         Reverse D
       <.                 Take the minimum of
         &(#.~)           the "trailing truths" of D and reverse(D)
    2*                    Multiply by 2
 #                        The length of D
  <.                      Minimum of length and the previous result

PHP, 83 74 bytes

3 + 6 bytes guardados por Jörg

<?=(~$s=decbin($argn))[$a=strspn($s,1)]?min($a,strspn(strrev($s),1))*2:$a;

toma entrada de STDIN; correr con -nR.

Descompostura

<?=                     # print ...
(~
    $s=decbin($argn)        # $s = binary representation of input
)[
    $a=strspn($s,1)         # $a = number of leading `1`s
]                           # if $s has more than $a digits,
?   min($a,                     # 2. minimum of $a and
        strspn(strrev($s),1)    # 1. number of trailing `1`s
    )*2                         # 3. *2
:   $a                      # else $a (==strlen)

JavaScript (ES6), 83 bytes

f=x=>(y=x.toString(2),y.match(/^1*$/)?y:([s,e]=y.match(/^1*|1*$/g),s<e?s:e)).length

Sin golf:

function f(n) {
    var binStr = n.toString(2);
    if(binStr.match(/^1*$/)) {
        // If binary representation is all 1s, return length of binary
        return binStr.length;
    } else {
        // Grab the starting and ending 1s in the binary representation
        var [start1s, end1s] = binStr.match(/^1*|1*$/g);
        var startHardness = start1s.length;
        var endHardness = end1s.length;
        return Math.min(startHardness, endHardness);
    }
}

Mathematica, 62 bytes

(h=0;#~IntegerDigits~2//.{{1,m___,1}:>(h+=2;{m}),{1}:>h++};h)&

Función pura donde #representa el primer argumento.

(h=0;...;h)&establece h=0, hace un montón de cosas ..., luego regresa h(la dureza). Veamos el montón de cosas:

#~IntegerDigits~2                                     Binary representation of the input
                 //.                                  Apply the following list of rules repeatedly until there is no change
                    {                                 Start of the list of rules
                     {1,m___,1}                       If you see a list starting and ending with 1 with the sequence m (possibly empty) in between
                               :>(h+=2;{m}),            replace it with just {m} after incrementing h twice.
                                            {1}       If you see the singleton list {1}
                                               :>h++    replace it with h, then increment h.
                                                    } End of the list of rules

Gracias a Greg Martin por presentarme este truco .

Haskell , 94 92 bytes

b 0=[]
b n=mod n 2:b(div n 2)
h n|(c,_:_)<-span(>0)$zipWith(*)n$reverse n=c++c|1<3=n
sum.h.b

Pruébalo en línea! Uso:

Prelude> sum.h.b $ 3167
4

Explicación:
b convierte un número a binario y devuelve una lista de cero y unos con el bit menos significativo primero. En h, esta lista se invierte y se multiplica por elementos con la lista original, luego se span(>0)divide después de la inicial 1s:

       b 3167 = [1,1,1,1,1,0,1,0,0,0,1,1] = n
    reverse n = [1,1,0,0,0,1,0,1,1,1,1,1] = m
zipWith(*)n m = [1,1,0,0,0,0,0,0,0,0,1,1] = z
   span(>0) z = ([1,1],[0,0,0,0,0,0,0,0,1,1])

La tupla resultante coincide con el patrón (c,_:_)donde _:_coincide con cualquier lista no vacía, por lo tanto c = [1,1]. Debido a que los bytes se eliminan en la parte delantera y trasera, c++c = [1,1,1,1]se devuelve y finalmente se resume para obtener la dureza digital .

Si la segunda lista de tuplas está vacía, entonces la representación binaria solo contiene unos, y el número de unos es la dureza digital. Con la coincidencia de patrones, el error hdevuelve solo n, lo que nuevamente se resume.

Perl, 61 bytes

sub f{$_=sprintf('%b',pop);length(/0/?/^(1+).*\1$/&&$1x2:$_)}

El corazón de esto es la expresión regular, /^(1+).*\1$/donde 2 veces la longitud $1es la respuesta. El resto del código está sobrecargado y se ocupa del caso especial de todos los 1.

PHP, 65 bytes

<?=strlen(preg_filter('#^(1*)(.*(\1))?$#',"$1$3",decbin($argn)));

Versión en línea

CJam, 14 bytes

ri2b_0#\W%0#e<

Explicación:

ri e# Read integer:      | 3167
2b e# Convert to binary: | [1 1 0 0 0 1 0 1 1 1 1 1]
_  e# Duplicate:         | [1 1 0 0 0 1 0 1 1 1 1 1] [1 1 0 0 0 1 0 1 1 1 1 1]
0# e# Index of first 0:  | [1 1 0 0 0 1 0 1 1 1 1 1] 2
\  e# Swap:              | 2 [1 1 0 0 0 1 0 1 1 1 1 1]
W% e# Reverse:           | 2 [1 1 1 1 1 0 1 0 0 0 1 1]
0# e# Index of first 0:  | 2 5
e< e# Minimum:           | 2