¿Un poco, un mordisco o un byte?

45

Inspirado por este desafío

Dado un número entero en el rango 0 <= n < 2**64, envíe el contenedor de tamaño mínimo en el que puede caber

  • bit: 1
  • mordisco: 4
  • byte: 8
  • corto: 16
  • int: 32
  • largo: 64

Casos de prueba:

0 -> 1
1 -> 1
2 -> 4
15 -> 4
16 -> 8
123 -> 8
260 -> 16
131313 -> 32
34359750709 -> 64

Este es el , por lo que gana la respuesta más corta en bytes.

Azul
fuente
10
Esto sería considerablemente más fácil si también 2fuera una salida ...
ETHproductions
1
@ETHproductions Lo haría pero, por desgracia, no lo es (me llevó demasiado tiempo escribir un algoritmo que lo hiciera)
Azul
Desearía haber entendido el problema. ... espera, ¿todo lo que quiere es la cantidad de bits necesarios para contener el número, redondeado a la siguiente estructura fundamental?
z0rberg's
2
¡Gracias! Me di cuenta cuando escribí el comentario y lo edité demasiado tarde. Supongo que necesito un pato de goma con quien hablar ...
z0rberg's
2
@Daniel las respuestas aquí toman un enfoque completamente diferente a la otra pregunta. Cuando digo 'inspirado por' no significa 'duplicado de'. No se pueden modificar trivialmente las respuestas para que sean válidas para esta pregunta
azul

Respuestas:

3

05AB1E , 10 bytes

bg.²îD1Q+o

Explicación

bg         Push the length of the binary representation of input without leading zeros
  .²î      Push x = ceil(log2(length))
     D1Q+  Add 1 if x == 1 or add 0 otherwise
         o Push pow(2,x) and implicitly display it

Pruébalo en línea!

Osable
fuente
22

Python, 39 bytes

f=lambda n:4**(n>1)*(n<16)or 2*f(n**.5)

Cuenta cuántas veces se debe tomar la raíz cuadrada para nestar debajo 16, con una carcasa especial para evitar salidas de 2.

Si se incluyeran 2, podríamos hacer

f=lambda n:n<2or 2*f(n**.5)

con True para 1.


41 bytes:

f=lambda n,i=1:i*(2**i>n)or f(n,i<<1+i%2)

Duplica repetidamente el exponente ihasta 2**i>n. Salta de i=1a i=4al cambiar un bit adicional cuando ies extraño.

Alt 45 bytes:

f=lambda n,i=4:4**(n>1)*(2**i>n)or 2*f(n,i*2)
xnor
fuente
77
Nunca deja de sorprenderme cómo puedes encontrar tantas soluciones para un problema. Básicamente, como programador, he aprendido a encontrar una solución a un problema y trabajar con él hasta que funcione. ¡Supongo que todavía tengo mucho que aprender sobre el golf! El respeto.
ElPedro
@xnor, ¿cómo sale tu primera respuesta 1cuando la raíz cuadrada de 0 o 1 es siempre 1 (recursividad infinita en or 2*f(n**.5))?
dfernan
2
@dfernan Creo que la parte después de la orsolo se evalúa si la parte anterior se evalúa como algo falso (cero). Para n = 0 y para n = 1, n>1evalúa a False, que se trata como cero en una expresión numérica, y n<16evalúa a True, que se trata como uno en una expresión numérica. Así 4**(n>1)*(n<16)es 1.
trichoplax
1
@trichoplax, eso es correcto. Gracias por la explicación.
dfernan
12

J, 19 bytes

Verbo monádico tomando el número a la derecha y escupiendo el tamaño del contenedor. Hay un par de formas equivalentes de escribirlo, así que he incluido ambos.

2^2(>.+1=>.)@^.#@#:
2^s+1=s=.2>.@^.#@#:

Explicado por explosión:

2^2(>.+1=>.)@^.#@#: NB. takes one argument on the right...
                 #: NB. write it in binary
               #@   NB. length (i.e. how many bits did that take?)
  2          ^.     NB. log base 2 of that
   (>.     )@       NB. ceiling
      +1=>.         NB. +1 if needed (since no container is two bits wide)
2^                  NB. base 2 exponential

Lo que es genial es que vemos dos formas diferentes de tomar la base de registro 2 en J. La primera es la obvia 2^., que es un logaritmo numérico. El segundo es #@#:, que puede leerse como "longitud de representación de base 2". Esto es casi equivalente a one-plus-floor-of-log-base-2, excepto que #:0es la lista de un elemento 0, que es exactamente lo que queremos. Esto late 1+2<.@^.1&>.por 8 bytes.

En uso en REPL:

   f =: 2^2(>.+1=>.)@^.#@#:
   f 131313
32
   f 34359750709
64
   (,.f"0) 0 1 2 15 16 123 260
  0  1
  1  1
  2  4
 15  4
 16  8
123  8
260 16

Solución antigua de 20 bytes demasiado inteligente.

2&^.(>.+1=>.&.)@#@#: NB. takes one argument on the right...
                #@#: NB. how many bits
2&^.                 NB. log base 2 of that
     >.              NB. ceiling
       +1=>.         NB. +1 if needed (since no container is two bits wide)
    (       &.)      NB. undo log base 2
Algoritmo de tiburón
fuente
9

Python, 53 50 49 bytes

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]
orlp
fuente
1
lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]es un byte más corto
Azul
Estaba a punto de publicar algo similar. +1
ElPedro
8

Mathematica, 44 39 38 bytes

Gracias @orlp por 5 bytes y @MartinEnder por 1 byte.

FirstCase[{1,4,8,16,32,64},x_/;2^x>#]&

Encuentra los primeros elementos de la lista de {1, 4, 8, 16, 32, 64}modo que el número 2 ^ sea mayor que la entrada.

JungHwan Min
fuente
8

Pip , 19 bytes

(a<2**_FI2**,7RM2i)

Pruébalo en línea!

Cómo funciona

                     a is 1st cmdline arg, i is 0 (implicit)
         2**,7       Construct powers of 2 from 0 to 6 [1 2 4 8 16 32 64]
              RM2    Remove 2
       FI            Filter for elements for which:
 a<2**_                a is less than 2 to that element
(                i)  Get 0th item of resulting list and autoprint
DLosc
fuente
7

JavaScript (ES7), 35 bytes

n=>[1,4,8,16,32,64].find(b=>2**b>n)
Neil
fuente
2
Una versión recursiva como f=(n,b=1)=>2**b>n&&b-2?b:f(n,b*2)debería ser un poco más corta.
Arnauld
6

Mathematica, 46 43 38 bytes

¡Gracias a JungHwan Min y Martin Ender por guardar 3 bytes! ¡Gracias a ngenisis por un gran ahorro de 5 bytes!

2^⌈Log2@BitLength@#⌉/.{2->4,0->1}&

Función sin nombre que toma un entero no negativo como entrada y devuelve un entero positivo. BitLength@#calcula el número de bits en la entrada y luego 2^⌈Log2@...⌉calcula la potencia más pequeña de 2 que es al menos tan grande como el número de bits. Finalmente, /.{2->4,0->1}se ocupa del caso especial de que no hay "niblit" entre bit y nybble, y también corrige la respuesta para la entrada extraña 0.

Greg Martin
fuente
2
Ahorre 3 bytes usando en BitLength@#lugar de ⌊1+Log2@#⌋. Luego, en lugar de reemplazar con 1usted, puede reemplazar 0, guardando otros 2 bytes y estará empatado en primer lugar.
ngenisis
1
En realidad, esto se puede hacer completamente con BitLength. Ver mi respuesta
ngenisis
4

Julia, 40 bytes

n->filter(x->n<big(2)^x,[1;2.^(2:6)])[1]

Esta es una función anónima que genera una matriz de las potencias de 2 de 0 a 6, excluyendo 2, y la filtra solo a aquellos elementos x de modo que 2 x sea ​​mayor que la entrada. El primer elemento es la respuesta. Desafortunadamente, esto requiere promover 2 a a BigIntpara evitar el desbordamiento en x = 64.

En realidad, esto es bastante similar a la respuesta de Python de orlp, aunque no lo vi antes de inventar este enfoque.

Pruébalo en línea!

Alex A.
fuente
4

Perl 6 , 30 bytes

{first 1+<*>$_,1,4,8,16,32,64}

+<es el operador de desplazamiento de bit izquierdo de Perl 6, que muchos otros idiomas llaman <<.

Sean
fuente
4

Haskell, 31 bytes

f n=[2^i|i<-0:[2..],2^2^i>n]!!0

Alt de 32 bytes:

f n|n<2=1|n<16=4|1>0=2*f(sqrt n)
xnor
fuente
2

Java, 143 bytes.

int f(long a){a=Long.toBinaryString(a).length();if(a<2)return 1;if(a<5)return 4;if(a<9)return 8;if(a<17)return 16;if(a<33)return 32;return 64;}
Pavel
fuente
1
Sé que puedo acortar esto, lo hago cuando estoy frente a una computadora.
Pavel
2
guardar 50 bytes: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64;
Mindwin
@Mindwin Lo sé, pero estoy de viaje y no tendré acceso a una computadora por un tiempo. Me pondré a ello.
Pavel
¿El puntaje lo convierte en un ... byte de amor ?
Engineer Toast el
2

Haskell, 43 bytes

f x=head$filter((>x).(2^))$[1,4,8,16,32,64]
Álcali
fuente
2

Ruby, 39 36 bytes

->n{2**[0,*2..6].find{|p|2**2**p>n}}

Gracias GB por ayudar al golf.

Alexis Andersen
fuente
También debería funcionar sin paréntesis. Además, la lista podría ser 0,2,3,4,5,6 y usar 1 << 2 ** p.
GB
... porque entonces podrías usar 0, * 2..6.
GB
2

Java 8, 65 55 bytes

Esta es una expresión lambda que toma un longy devuelve un int. Nunca jugué golf en Java antes, por lo que esto debería ser fácilmente superable:

x->{int i=1;while(Math.pow(2,i)<=x)i<<=1+i%2;return i;}

Pruébalo en línea!


Para 47 bytes , podríamos tener:

x->{int i=1;while(1L<<i<=x)i<<=1+i%2;return i;}

Sin embargo, se 1L<<idesborda para valores de retorno superiores a 32, por lo que esto falla para el caso de prueba final.

FlipTack
fuente
1
Esto regresa 4cuando se prueba con 16cuando se supone que debe devolver 8. Además, aún puede jugar golf esta solución quitando los corchetes i<<=1+i%2;ya que sin {}s, el ciclo while solo ejecutará la siguiente línea
Kritixi Lithos
@KritixiLithos debería arreglarse ahora - lo siento, mi Java se ha oxidado ...
FlipTack
2

Mathematica, 30 bytes

2^(f=BitLength)[f@#-1]/. 2->4&

Explicación:

Dejar Nser el conjunto de enteros no negativos. Defina dos funciones en N, BitLengthy de la NextPowersiguiente manera:

BitLength(n) := min {x in N : 2^x - 1 >= n}
NextPower(n) := 2^(min {x in N : 2^x >= n})

Esta solución esencialmente calcula NextPower(BitLength(n))dado un entero n >= 0. Porque n > 0podemos ver eso NextPower(n) = 2^BitLength(n-1), entonces NextPower(BitLength(n)) = 2^BitLength(BitLength(n)-1).

Ahora el Mathematica BitLengthincorporado está de acuerdo con la definición que di n >= 0. Para n < 0, BitLength[n] == BitLength[BitNot[n]] == BitLength[-1-n], así BitLength[-1] == BitLength[0] == 0. Así obtenemos la respuesta deseada de 1for n==0.

Como saltamos directamente de bit a mordisco, tenemos que reemplazar las respuestas de 2con 4.

ngenisis
fuente
1
Muy bien construido! (Es una pena que el espacio sea necesario.)
Greg Martin
2

bash, 49 bytes 48 bytes

for((y=1;$[y==2|$1>=1<<y];$[y*=2])){ :;};echo $y

o

for((y=1;$[y==2|$1>=1<<y];)){ y=$[y*2];};echo $y

Guarde en un script y pase el número a probar como argumento.

Editar: Reemplazado || con |, que funciona porque los argumentos son siempre 0 o 1.

Nota: Esto funciona para enteros hasta el mayor entero positivo que su versión de bash puede manejar. Si tengo tiempo, lo modificaré para que funcione hasta 2 ^ 64-1 en versiones de bash que usan aritmética con signo de 32 bits.

Mientras tanto, aquí hay una solución de 64 bytes que funciona para números arbitrariamente grandes (en cualquier versión bash):

for((x=`dc<<<2o$1n|wc -c`;$[x==2||x&(x-1)];$[x++])){ :;};echo $x
Mitchell Spector
fuente
2

Apilado, 34 30 bytes

@n 1 2 6|>2\^,:n 2 log>keep 0#

o

{!1 2 6|>2\^,:n 2 log>keep 0#}

El primero toma entrada en los TOS y deja la salida en TOS; El segundo es una función. Pruébalo aquí!

Explicación

@n 1 2 6|>2\^,:n 2 log>keep 0#
@n                               set TOS to `n`
   1 2 6|>2\^,                   equiv. [1, ...2 ** range(2, 6)]
              :                  duplicate it
               n                 push `n`
                 2 log           log base-2
                      >          element-wise `>`
                       keep      keep only truthy values
                            0#   yield the first element

Aquí hay un ejemplo de ello trabajando en la respuesta :

> 8    (* input *)
(8)
> @n 1 2 6|>2\^,:n 2 log>keep 0#    (* function *)
(4)
>    (* output *)
(4)

Casos de prueba

> {!1 2 6|>2\^,:n 2 log>keep 0#} @:f
()
> (0 1 2 15 16 123 260 131313 34359750709) $f map
((1 1 4 4 8 8 16 32 64))
> 

O, como un programa completo:

{!1 2 6|>2\^,:n 2 log>keep 0#} @:f

(0 1 2 15 16 123 260 131313 34359750709) $f map

out
Conor O'Brien
fuente
2

Raqueta 45 bytes

(findf(λ(x)(>(expt 2 x)m))'(1 4 8 16 32 64))

Sin golf:

(define (f m)
  (findf (λ (x) (> (expt 2 x) m))          ; find first function
         '(1 4 8 16 32 64)))

Otras versiones:

(define (f1 m)
  (for/last ((i '(1 4 8 16 32 64))         ; using for loop, taking last item
             #:final (> (expt 2 i) m))     ; no further loops if this is true
    i))

y usando longitud de cadena:

(define (f2 m)
  (for/last
      ((i '(1 4 8 16 32 64))
       #:final (<= (string-length
                    (number->string m 2))  ; convert number to binary string
                   i))
    i))

Pruebas:

(f 0)
(f 1)
(f 2)
(f 15)
(f 16)
(f 123)
(f 260)
(f 131313)
(f 34359750709)

Salida:

1
1
4
4
8
8
16
32
64
rnso
fuente
1

Octava, 40 36 31 29 bytes

Función anónima simple. Se supone que el valor de entrada es un número entero; vea la advertencia al final.

@(a)(b=2.^[0 2:6])(a<2.^b)(1)

El código funciona de la siguiente manera:

  • Primero se crea y se guarda una matriz de las longitudes de bits permitidas (1,4,8,16,32,64) b.

  • A continuación, encontramos el número de bits necesarios para almacenar el número de entrada acomparándolo con el tamaño máximo de cada contenedor bpara ver cuáles son lo suficientemente grandes.

  • Luego usamos el vector índice resultante para extraer bnuevamente el tamaño del contenedor .

  • Finalmente, tomamos el primer elemento en la matriz resultante que será el contenedor más pequeño posible.

Puedes probarlo en línea aquí .

Simplemente ejecute el siguiente código y luego haga ans(x).


La única advertencia con esto es que la precisión doble se usa para constantes de forma predeterminada, lo que significa que solo funciona con números hasta el valor más alto representable por un flotante de precisión doble que es menor que 2 ^ 64.

Esto se puede solucionar asegurándose de que el número que se proporciona a la función es un número entero en lugar de un doble. Esto se puede conseguir llamando a la función, por ejemplo, con: ans(uint64(x)).

Tom Carpenter
fuente
1

PHP, 49 46 44 bytes

echo(2**ceil(log(log(1+$argn,2),2))-2?:2)+2;

Corre así:

echo 16 | php -R 'echo(2**ceil(log(log(1+$argv[1],2),2))-2?:2)+2;';echo

Explicación

echo                       # Output the result of the expression
  (
    2**                    # 2 to the power
      ceil(log(            # The ceiling of the power of 2 of bitsize
        log(1+$argn,2),    # Number of bits needed
        2
      ))
      - 2 ?:               # Subtract 2 (will be added back again)
      2;                   # If that results in 0, result in 2 (+2=4).
  ) + 2                    # Add 2.

Ajustes

  • Se ahorraron 3 bytes al deshacerse de la $r=tarea
  • Se guardaron 2 bytes al usar -Rpara poner a $argndisposición
aross
fuente
1

CJam , 18 bytes

2ri2b,2mLm]_({)}|#

Pruébalo en línea!

Explicación

2                   Push 2
 ri                 Read an integer from input
   2b,              Get the length of its binary representation
      2mLm]         Take the ceiling of the base-2 log of the length
           _(       Duplicate it and decrement it
             {)}|   Pop the top element, if it's 0, increment the next element
                     Effectively, if ceil(log2(input)) was 1, it's incremented to 2,
                     otherwise it stays the same.
                 #  Raise 2 to that power
Gato de negocios
fuente
0

C, 71 52 bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
Steadybox
fuente
¿Una entrada de (1<<15)+1o más no rompería esto debido al comportamiento firmado de long long? ¡El tipo que realmente quieres es el uint64_tque necesita, #include <stdint.h>que sigue siendo un perdedor en comparación unsigned long long! Los encabezados son la ruina del golf en c.
dmckee
@dmckee Supongo que podría romperlo, pero parece funcionar al menos en mi computadora. No he encontrado un ejemplo que no funcione. Pensé en usar unsigned long longo uint64_t, pero como parece funcionar, lo long longseguí.
Steadybox
0

QBIC , 27 bytes

:~a<2|_Xq]{~a<2^t|_Xt\t=t*2

Explicación

:        Get cmd line parameter N, call it 'a'
~a<2     IF 'a' is 0 or 1 (edge case)
|_Xq]    THEN quit, printing 1 ('q' is auto-initialised to 1). ']' is END-IF
{        DO - infinite loop
    2^t  't' is our current number of bits, QBIC sets t=4 at the start of the program.
         2^t gives the maximum number storable in t bytes.
 ~a<     IF the input fits within that number,
|_Xt     THEN quit printing this 't'
\t=t*2   ELSE jump to the next bracket (which are spaced a factor 2 apart, from 4 up)
         DO-loop is auto-closed by QBIC.
Steenbergh
fuente
0

Pyke, 13 bytes

7Zm@2-#2R^<)h

Pruébalo aquí!

7Zm@          -   [set_bit(0, i) for i in range(7)] <- create powers of 2
    2-        -  ^.remove(2)
      #    )h - filter(^, V)[0]
       2R^    -   2 ** i
          <   -  input < ^
Azul
fuente
0

PHP, 43 bytes

for(;1<<2**$i++<=$argn;);echo 2**$i-=$i!=2;

Corre con echo <number> | php -R '<code>'.

se repite $ihasta que 2**(2**$i)sea ​​más grande que la entrada. (Ajuste: en <<lugar de **eliminar a los padres)
Después del ciclo, $ i es uno demasiado alto; por lo que obtiene una disminución antes de calcular la salida
, pero no para $i==2.

Titus
fuente