Gol
Dado un entero no negativo, cree una función que devuelva la posición inicial del número de los 1 consecutivos más grandes en el valor binario de ese entero.
Cuando se le da una entrada 0
, regrese 0
.
Si el número tiene varias líneas de igual longitud, debe devolver la posición de la última línea.
Entrada
Un entero mayor o igual a 0.
Salida
Un entero calculado como se explica a continuación.
Reglas
- Este es el código de golf, por lo que gana el código más corto en bytes en cada idioma.
- Las lagunas estándar están prohibidas.
Ejemplos y casos de prueba
Ejemplo 1
- Su función se pasa al entero 142
- 142 es igual a 10001110 en binario
- La racha más larga es "111" (una racha de tres)
- La racha comienza en la posición 2 ^ 1
- Su función devuelve 1 como resultado
Ejemplo 2
- Su función se pasa al entero 48
- 48 es igual a 110000 en binario
- La racha más larga es "11" (una racha de dos)
- La racha comienza en la posición 2 ^ 4
- Su función devuelve 4 como resultado
Ejemplo 3
- Su función se pasa al entero 750
- 750 es igual a 1011101110 en binario
- La racha más larga es "111" (una racha de tres)
- Como hay dos líneas de igual longitud, devolvemos la línea posterior.
- La racha posterior comienza en la posición 2 ^ 5
- Su función devuelve 5 como resultado
0
. Ese es un caso de prueba importante.Respuestas:
Jalea ,
108 bytesPruébalo en línea!
Cómo funciona
fuente
JavaScript (ES6),
41403634 bytesGuardado 4 bytes gracias a @ThePirateBay
Casos de prueba
Mostrar fragmento de código
¿Cómo?
Caso general x> 0
Recurrimos Y la entrada x con x / 2, que reduce progresivamente los patrones de los bits establecidos consecutivos hasta que solo quede el bit más a la derecha de la secuencia. Mantenemos una copia del último valor distinto de cero y determinamos la posición de su bit más significativo redondeando su logaritmo de base 2.
A continuación se detallan los pasos que seguimos para x = 750 ( 1011101110 en binario).
Caso de borde x = 0
El caso especial
x = 0
lleva inmediatamente aMath.log2(0) | 0
. El logaritmo de0
evalúa-Infinity
y el binario OR a nivel de bit fuerza una coerción a un entero de 32 bits. En cumplimiento con la especificación de la operación abstracta ToInt32 , esto proporciona lo esperado0
:fuente
0
produce errores en la entrada , que forma parte del rango de entrada.Math.log2(k)|0
lugar de31-Math.clz32(k)
? ¿O me estoy perdiendo algo?Math.log2(k)|0
es en realidad más corto y más simple para el caso especialx=0
. Gracias. :)código de máquina x86, 14 bytes
Usando @ algoritmo de Arnauld de
x &= x>>1
y tomando la posición de bit más alta establecida en el paso anteriorx
se hace0
.Llamable desde C / C ++ con firma
unsigned longest_set(unsigned edi);
en el x86-64 System V ABI. Los mismos bytes de código de máquina se decodificarán de la misma manera en el modo de 32 bits, pero las convenciones de llamada estándar de 32 bits no ponen el primer argumentoedi
. (Cambio de la entrada de registro paraecx
oedx
para Windows_fastcall
/_vectorcall
ogcc -mregparm
se podría hacer sin romper nada.)La
BSR
instrucción de x86 (Bit Scan Reverse) es perfecta para esto, ya que nos proporciona el índice de bits directamente, en lugar de contar los ceros a la izquierda. (bsr
no produce directamente 0 para input = 0 como lo32-lzcnt(x)
haría, pero necesitamos bsr = 31-lzcnt para entradas que no sean cero, porlzcnt
lo que ni siquiera guardaría instrucciones, y mucho menos contar bytes. Poner a cero eax antes de que el bucle funcione debido absr
' s comportamiento semioficial de dejar el destino sin modificar cuando la entrada es cero).Esto sería aún más corto si pudiéramos devolver la posición MSB de la carrera más larga. En ese caso,
lea ecx, [rdi+rdi]
(3 bytes) copiaría + desplazamiento a la izquierda en lugar demov
+shr
(4 bytes).Vea este enlace TIO para una llamada asm que
exit(longest_set(argc-1));
Prueba con un bucle de shell:
fuente
Jalea ,
191711 bytesPruébalo en línea!
-6 (!) Bytes gracias a las agudas observaciones de @ Dennis
Cómo funciona
fuente
0
, que está en el rango de entrada.ȯ-µ...
B
siempre devuelve una matriz que comienza con un 1 ,BUṪMṪ’×Ṡ
puede convertirseṪBL’
. Además, no necesita elḞ
yḟ0
ahorra un byte¹Ðf
.Python 2 , 45 bytes
Pruébalo en línea!
¡Ahorré muchos bytes gracias a Dennis! (El aviso en
len(bin(...))-3
lugar demath.frexp
)Gracias a @xnor por encontrar un error, que afortunadamente fue fácilmente reparable.
fuente
x=3
, creo, porque losand/or
cortocircuitos son incorrectos cuando la función devuelve 0.Perl 6 ,
4535 bytesEsta versión altamente mejorada es cortesía de @nwellnhof.
Pruébalo en línea!
fuente
:g
para obtener todas las coincidencias. Con el operador inteligente partido, pude campo se reduce a 40 bytes:{sort(.base(2).flip~~m:g/1+/).tail.from}
{.msb+1-(.base(2)~~m:g/1+/).max.to}
:g
y no descubrí cómo puedo usar el adverbio con el operador smartmatch. También el.msb
método es bastante útil aquí y no lo sabía antes.Python 2 ,
8978 bytesPruébalo en línea!
EDITAR: Guardado 11 bytes gracias al Sr. Xcoder.
fuente
05AB1E ,
141211 bytesPruébalo en línea! o ejecutar casos de prueba .
Explicación
fuente
J ,
1817 bytesPruébalo en línea!
Explicación
fuente
x
díada son todas 0 y 1, ¿qué significa eso? Un número base 2 tiene dígitos0
y1
, entonces, un1
número base tiene dígitos ...0
? entonces, ¿qué significa un1
en ese contexto? ¿Y es un0
número base siempre0
?x #. y
primero computaw =: */\. }. x , 1
luego regresa+/ w * y
#.
, ya que depende de los detalles de implementación internos en lugar de la API pública?C # (.NET Core) ,
6460 bytesPruébalo en línea!
AC # versión de la respuesta @ Arnauld
Expresiones de gratitud
4 bytes guardados gracias a Kevin Cruijssen.
C # (.NET Core) ,
131123 + 18 = 141 bytesPruébalo en línea!
+18 bytes para
using System.Linq;
Expresiones de gratitud
8 bytes guardados gracias a Grzegorz Puławski.
Degolfed
C # (.NET Core) ,
164161bytesPruébalo en línea!
Un no
Linq
solución, que estoy seguro podría mejorarse, aunque nada es evidente de inmediato.Degolfed
fuente
r
en la primera respuesta: tio.run/##dY9RS8MwFIWfza/…T=a=>{int x=(int)Math.Log(a,2);return(a&=a/2)>0?T(a):x<0?0:x;}
T=a=>(a&a/2)>0?T(a&a/2):Math.Log(a,2)<0?0:(int)Math.Log(a,2)
Casco , 12 bytes
Pruébalo en línea!
Explicación
fuente
Jalea ,
14 13 1211 bytesUn enlace monádico que toma y devuelve enteros no negativos.
Pruébalo en línea! o ver el conjunto de pruebas .
¿Cómo?
fuente
ŒrṪP
en su lugar usé los prefijos.Jalea , 19 bytes
Pruébalo en línea!
¡Gracias a Jonathan Allan por guardar
46 bytes!He trabajado demasiado para abandonar esto, aunque es un poco largo. Realmente quería agregar una solución que literalmente busca la subcadena más larga de
1
s en la representación binaria ...Explicación
fuente
BŒgḄṀB
en su lugarBwÇɓÇL+ɓBL_‘
Kotlin , 77 bytes
Embellecido
Prueba
fuente
Haskell ,
101989675 bytesPruébalo en línea! Uso:
snd.maximum.(`zip`[0..]).c $ 142
rendimientos1
.Explicación:
c
convierte la entrada en binario y, al mismo tiempo, cuenta la longitud de las rayas de una, y recopila los resultados en una lista.r<-c$div n 2
calcula recursivamente el restor
de esta lista, mientrassum[r!!0+1|mod n 2>0]:r
agrega la longitud actual de la rachar
. La comprensión de la lista verifica simod n 2>0
, es decir, si el dígito binario actual es uno, y si es así, toma la longitud de la racha anterior (el primer elemento der
) y agrega uno. De lo contrario, la comprensión de la lista está vacía ysum[]
rinde0
. Para la entrada de ejemplo, sec 142
obtiene la lista[0,3,2,1,0,0,0,1,0]
.(`zip`[0..])
agrega la posición a cada elemento de la lista anterior como el segundo componente de una tupla. Por el ejemplo esto da[(0,0),(3,1),(2,2),(1,3),(0,4),(0,5),(0,6),(1,7),(0,8)]
.maximum
encuentra la tupla lexicográficamente máxima en esta lista, es decir, las longitudes de las rayas se consideran primero ya que son el primer componente y, en caso de empate, el segundo componente, es decir, el índice más grande, decide. Esto rinde(3,1)
en el ejemplo ysnd
devuelve el segundo componente de la tupla.fuente
Python 2 o 3 , 58 bytes
Pruébalo en línea!
fuente
C (gcc) ,
8180 bytesPruébalo en línea!
C (gcc) , 43 bytes
Versión de CA de la respuesta de @ Arnauld
Pruébalo en línea!
fuente
n<1?0:log2(n)
lugar de(k=log2(n))<0?0:k
Servidor MS SQL,
437426407398 bytesViolín de SQL
Estoy seguro de que podría eliminar los saltos de línea, etc., pero esto es tan compacto como estaba dispuesto a hacerlo:
Aquí hay una versión más legible:
El verdadero truco es que, por lo que pude encontrar, no hay una funcionalidad SQL nativa para convertir un número de decimal a binario. Como resultado, tuve que codificar la conversión a binario manualmente, luego pude comparar eso como una cadena, un carácter a la vez hasta que encontré el número correcto.
Estoy seguro de que hay una mejor manera de hacer esto, pero no vi una respuesta (n) de SQL, así que pensé que lo lanzaría allí.
fuente
APL (Dyalog Unicode) , 22 caracteres = 53 bytes
Requiere
⎕IO←0
cuál es el predeterminado en muchos sistemas.Pruébalo en línea!
⎕
solicitud de entrada⊢
rendimiento que (se separa¯1
de⎕
)2⊥⍣¯1
convertir a base-2, usando tantas posiciones como sea necesariob←
almacenar comob
(para b inary)⌽
marcha atrás(
…)
Marque las posiciones iniciales de lo siguiente en eso:⊆⍨b
autoparticiónb
(es decir, las 1 rayas deb
)↑
mezclar (hacer una lista de listas en matriz, relleno con ceros)∨⌿
reducción vertical O (produce la racha más larga)⍸
d ndices de posiciones iniciales⌽
marcha atrás⊃
elija el primero (produce cero si no hay ninguno disponible)fuente
MATL , 15 bytes
Pruébalo en línea!
Utiliza la mitad y la idea AND. El
k
sólo es necesario para que sea interrumpido a causa de1
- por alguna razón, 1 y 0,5 devuelve 1, provocando un bucle infinito.(solución alternativa:
BtnwY'tYswb*&X>)-
convirtiendo a codificación binaria y de longitud de ejecución)fuente
Hojas de cálculo de Google, 94 bytes
No, no es muy bonita. Sería realmente bueno poder almacenar
Dec2Bin(A1)
como una variable de referencia.Punto clave: al igual que Excel, la
Dec2Bin
función tiene un valor de entrada máximo de511
. Cualquier cosa mayor que eso devuelve un error, como se ve a continuación.fuente
R, 117 bytes
fuente
rev
, useReduce(...,T,T)
para acumular desde la derecha (cambiandox,y
la definición de la función). Luego, use1+max(z)-which.max(z)
ya que el resultado es algo diferente. Usar en"if"
lugar de"ifelse"
ya que no necesitamos la vectorización; y si usa enany(z)
lugar de!sum(z)
soltar un byte.Excel VBA,
5444 Bytes-10 Bytes gracias a @EngineerToast
Función de ventana inmediata anónima de VBE que toma entrada del rango
[A1]
y salidas a la ventana inmediata de VBEfuente
C1
todavía está allí, en lugar deA1
, creo que puede generar losInstr
resultados directamente con un pequeño giro para la corrección de entrada cero:?Instr(1,StrReverse([Dec2Bin(A1)]),1)+([A1]>0)
(46 bytes). Verdadero = -1 porque ... VBA.>0
en la[A1]
notaciónAPL (Dyalog Classic) ,
2421 bytesPruébalo en línea!
fuente
Pyth , 17 bytes
Esta es una función recursiva. El enlace incluye
y
para llamar a la función en la entrada dada.Verifique todos los casos de prueba.
Pyth , 20 bytes
Verifique todos los casos de prueba.
fuente
R, 66 bytes
Explicación:
fuente
a$l
lugar dea[[1]]
y ena$v
lugar dea[[2]]
guardar algunos bytes :), así como en>0
lugar de==1
.Python 2 , 41 bytes
Pruébalo en línea!
Basado en esta solución por el Sr. Xcoder .
fuente
Javascript, 54 caracteres
i.toString(2)
obtiene la cadena binaria para el entero..split(0)
obtiene cada parte las secuencial en un elemento de matriz..sort().reverse()
nos da el valor más alto como el primero.[0].length
nos da la longitud de ese primer valor.fuente
the starting position of number of largest consecutive 1's
Perl 5, 45 + 1 (-p)
Si escribe esto en la línea de comando de la mayoría de los shells, puede que tenga que escribir esto como:
El baile de las citas al final es solo para que Perl vea a
'
, que de lo contrario sería consumido por el caparazón.fuente
Retina ,
5243 bytesConvierta a binario, luego reemplace con la longitud de lo que sigue a la cadena más grande de unos.
Pruébalo en línea : todos los casos de prueba
Guardado 9 bytes gracias a Martin.
fuente
$+
para${1}
. Pero puede ahorrar aún más al reemplazar la última etapa con un montón de etapas como esta: tio.run/##K0otycxL/K/…${1}
fue copiado de su tutorial en Github.