¿En cuántos pedazos encajo?

52

Para cualquier 1 ≤ n ≤ 0xFFFFFFFFsalida positiva de entero de 32 bits ( ), el número de bits necesarios para representar ese entero.

Casos de prueba

| n    | n in binary | bits needed |
|----------------------------------|
| 1    | 1           | 1           |
| 2    | 10          | 2           |
| 3    | 11          | 2           |
| 4    | 100         | 3           |
| 7    | 111         | 3           |
| 8    | 1000        | 4           |
| 15   | 1111        | 4           |
| 16   | 10000       | 5           |
| 128  | 10000000    | 8           |
| 341  | 101010101   | 9           |

4294967295 => 11111111111111111111111111111111 => 32

Entonces f(16)imprimiría o devolvería5

Este es el . El código más corto en bytes gana

Bassdrop Cumberwubwubwub
fuente
2
Este es el techo del logaritmo de base 2.
orlp
23
@orlp Realmente lo esfloor(log2(num))+1
Kritixi Lithos
2
@KritixiLithos Derecha.
orlp
3
No importa, acabo de darme cuenta de que lo distinto es importante cuando numes un poder de dos.
Brian J
11
Este es un desafío trivial con muchas soluciones triviales. Sin embargo, también hay algunas soluciones no triviales. A los votantes: Lea la primera oración de esta meta publicación antes de votar a favor de las funciones integradas. (humildemente tomado de este comentario )
Kritixi Lithos

Respuestas:

30

05AB1E , 2 bytes

bg

Pruébalo en línea!

Urna de pulpo mágico
fuente
16
El lenguaje esotérico volvió a ganar ...bg
devRicher
20
@devRicher Espero ser derrotado por una solución de 1 byte, para ser honesto.
Urna mágica del pulpo
99
Al menos esta respuesta obtiene sus votos positivos; no está en el bg.
NoOneIsHere
3
bgen juegos significa bad game:)
YoYoYonnY
1
@yoyoyonny o campo de batalla jaja.
Magic Octopus Urn
35

JavaScript (ES6), 18 bytes

f=n=>n&&1+f(n>>>1)
<input type=number min=0 step=1 value=8 oninput="O.value=f(this.value)">
<input id=O value=4 disabled>

ETHproducciones
fuente
Esta es una de las pocas soluciones no triviales aquí. Buena táctica!
Kritixi Lithos
1
¿Debería ser n>>>1para apoyar n > 0x7FFFFFFF?
Arnauld
@Arnauld Hmm, no sabía que >>falló en nesa altura. Gracias.
ETHproductions
f=(a,b=1)=>a>1?f(a>>1,++b):b
Bien
28

Asamblea x86, 4 bytes

Suponiendo constante en EBX:

bsr eax,ebx
inc eax

EAX contiene el número de bits necesarios para Constant.

Bytes: ☼¢├@

Hexadecimal: ['0xf', '0xbd', '0xc3', '0x40']

de z0rberg
fuente
2
¿Podría incluir un hexdump del código de ensamblado x86 compilado de 8 bytes real?
Loovjo
También lo hizo. Y gracias, porque me di cuenta de que cometí un error. Agregué un "inc eax" para cumplir con las reglas. Perdí un byte. :(
z0rberg's
Oh, wow, cambiaste mi publicación al formato correcto. Gracias por corregirlo!
z0rberg's
2
Por cierto, los envíos de la Asamblea pueden suponer que la entrada ya está almacenada en un registro específico , por lo que creo que podría reducir algunos bytes de esa manera.
Loovjo
1
¿Es habitual contar los envíos de ensamblados como el número de bytes del código de máquina compilado en lugar del código fuente del lenguaje ensamblador?
sonríe el
18

Python , 14 bytes

int.bit_length

Pruébalo en línea!

Dennis
fuente
También funciona en Python 2.
vaultah
1
De hecho lo hace. Olvidé que el int. De Python 2 tenía 64 bits de ancho, no 32 bits.
Dennis
Python 3 bit_lengthes bit_length().
dfernan
2
@dfernan Esto no es una llamada de función; Es una función. Si n es un int , int.bit_length(n)y n.bit_length()haz exactamente lo mismo.
Dennis
2
@dfernan int.bit_length(n)es una llamada de función y, por lo tanto, un fragmento que supone que la entrada se almacena en una variable. Esto es no permitido por las reglas, por lo que añadiendo (n)haría que este no válida respuesta. Sin embargo, se int.bit_lengthevalúa como una función y se puede guardar en una variable para su uso posterior. Esto está permitido por defecto.
Dennis
15

Laberinto , 13 12 bytes

 ?
_:
2/#(!@

Pruébalo en línea!

Explicación

El programa simplemente divide repetidamente la entrada por 2 hasta que sea cero. Se realiza un seguimiento del número de pasos duplicando el valor en cada paso. Una vez que se reduce a cero, imprimimos la profundidad de la pila (menos 1).

El programa comienza en el ?que lee la entrada. El bucle principal es el bloque de 2x2 a continuación, en sentido antihorario:

:   Duplicate current value.
_2  Push 2.
/   Divide.

Una vez que el valor es cero después de una iteración completa, se ejecuta el bit lineal al final:

#   Push stack depth.
(   Decrement.
!   Print.
@   Terminate.
Martin Ender
fuente
55
Esta solución está completa: toma datos y proporciona la respuesta, y no utiliza ninguna función existente para este propósito específico: calcula la respuesta manualmente. Para mí, esto está más en el espíritu del juego que la mayoría de las otras respuestas.
Johan
15

C, 31 bytes

f(long n){return n?1+f(n/2):0;}

... Entonces pensé en la recursividad. De oscuro a obvio, y con un cuarto de la longitud cayó.

Véalo en vivo en Coliru


C, 43 bytes

c;
#define f(v)({for(c=0;v>=1l<<c;++c);c;})

Llamar fcon un valor sin signo (por ejemplo f(42u)) "devolverá" su longitud de bits. Incluso funciona para 0u!

Ungolfed y explicó: (se omiten las barras invertidas)

c;
#define f(v)
    ({ // GCC statement-expression

        // Increment c until (1 << c) >= v, i.e
        // that's enough bits to contain v.
        // Note the `l` to force long
        // arithmetic that won't overflow.
        for(c = 0; v >= 1l << c; ++c)
            ; // Empty for body

        c; // Return value
    })

Véalo en vivo en Coliru

Quentin
fuente
OP garantiza n> = 1, por n?...:0lo que no es necesario.
Físico loco
1
@MadPhysicist, bueno, tengo que detener la recurrencia en alguna parte, ¿no?)
Quentin
OIC No leí con cuidado, me siento como un idiota ahora. Respuesta ordenada de cualquier manera.
Físico loco
@MadPhysicist no se preocupe, muchas gracias :)
Quentin
Para la solución no recursiva que asume expresiones de declaración gcc, creo que también podría haber estado inclinado a utilizar el #define f(n) ({64-__builtin_clzl(n);})enfoque.
Moreaki
14

Mathematica, 9 bytes

BitLength

Alternativamente:

Floor@Log2@#+1&
#~IntegerLength~2&
Martin Ender
fuente
14

Perl 6 , 7 bytes

*.msb+1

Intentalo

Explicación:

* hace que se convierta en un lambda WhateverCode e indica dónde colocar la entrada

.msb en un Int devuelve el índice del bit más significativo (basado en 0)

+1se combina en el lambda y agrega uno al resultado final de la llamada .msb.

Brad Gilbert b2gills
fuente
13

Macro de preprocesador C (con extensiones gcc), 26

#define f 32-__builtin_clz

Utiliza la función de recuento de ceros principales de GCC incorporada .

Llame a esto como una función, por ejemplo f(100).

Pruébalo en línea .

Trauma digital
fuente
Oh wow, pensé en usar un builtin incorporado pero descarté la idea porque pensé que iba a ser demasiado largo ... Bien jugado.
Quentin
Lucky, el OP especificó n> = 1: D
Matthieu M.
12

Retina , 56 37 bytes

Esta solución funciona con todos los valores de entrada requeridos.

El mayor problema que enfrenta Retina en este desafío es el hecho de que sus cadenas tienen una longitud máxima de 2 ^ 30 caracteres, por lo que la forma habitual de tratar con números (representación unaria) no funciona con valores mayores de 2 ^ 30.

Para resolver este problema, adopté un enfoque diferente, manteniendo una especie de representación decimal de números, pero donde cada dígito está escrito en unario (llamaré a esta representación digitalunaria ). Por ejemplo, el número 341se escribiría como 111#1111#1#en digitunary. Con esta representación ahora podemos trabajar con números de hasta 2^30/10dígitos (~ cien millones de dígitos). Es menos práctico que el unario estándar para la aritmética arbitraria, pero con un poco de esfuerzo podríamos hacer cualquier tipo de operaciones.

NOTA: digitunary en teoría podría usar cualquier otra base (por ejemplo, el binario 110estaría 1#1##en base 2 digitunary), pero dado que Retina tiene incorporados para convertir entre decimal y unary y no hay una forma directa de tratar con otras bases, el decimal es probablemente la base más manejable.

El algoritmo que utilicé es hacer divisiones enteras sucesivas por dos hasta que lleguemos a cero, el número de divisiones que hicimos es el número de bits necesarios para representar este número.

Entonces, ¿cómo dividimos por dos en dígitosunarios? Aquí está el fragmento de Retina que lo hace:

(1*)(1?)\1#        We divide one digit, the first group captures the result, the second group captures the remainder
$1#$2$2$2$2$2      The result is put in place of the old number, the remainder passes to the next digit (so it is multiplied by 10) and is divided by two there -> 5 times the remainder goes to the next digit

Este reemplazo es suficiente para dividir un número digital numérico por 2, solo necesitamos eliminar posibles .5s del final si el número original era impar.

Entonces, aquí está el código completo, seguimos dividiendo por dos hasta que todavía hay dígitos en el número, y ponemos un literal nfrente a la cadena en cada iteración: el número nal final es el resultado.

.                  |
$*1#               Convert to digitunary
{`^(.*1)           Loop:|
n$1                    add an 'n'
(1*)(1?)\1#            |
$1#$2$2$2$2$2          divide by 2
)`#1*$                 |
#                      erase leftovers
n                  Return the number of 'n's in the string

Pruébalo en línea!


Solución actualizada, 37 bytes

Gran refactorización con muchas buenas ideas que jugaron alrededor de un tercio de la longitud, ¡todo gracias a Martin Ender!

La idea principal es usar _como nuestro símbolo unario: de esta manera podemos usar dígitos regulares en nuestra cadena, siempre y cuando los convertimos de nuevo a _s cuando sea necesario: esto nos permite guardar muchos bytes en la división y en la inserción de múltiples dígitos

Aquí está el código:

<empty line>    |
#               put a # before each digit and at the end of the string 
{`\d            Loop:|
$*_                 Replace each digit with the corrisponding number of _
1`_                 |
n_                  Add an 'n' before the first _
__                  |
1                   Division by 2 (two _s become a 1)
_#                  |
#5                  Wherever there is a remainder, add 5 to the next digit
}`5$                |
                    Remove the final 5 you get when you divide odd numbers
n               Return the number of 'n's in the string

Pruébalo en línea!

León
fuente
1
He usado una forma numérica similar (pero la llamé Decimal codificado en unario ), que es bastante útil para la aritmética con Sed.
Toby Speight
11

Ruby, 19 16 bytes

->n{"%b"%n=~/$/}

Gracias Jordan por jugar golf 3 bytes

Alexis Andersen
fuente
Puede guardar un byte con %: ->n{("%b"%n).size}.
Jordania
3
Espera, esto es más corto: ->n{"%b"%n=~/$/}.
Jordania
10

Jolf, 2 bytes

lB

Simplemente convierta a binario y luego encuentre la longitud.

Rɪᴋᴇʀ
fuente
10

JavaScript ES6, 19 bytes

a=>32-Math.clz32(a)

Math.clz32devuelve el número de cero bits iniciales en la representación binaria de 32 bits de un número. Entonces, para obtener la cantidad de bits necesarios, todo lo que tenemos que hacer es restar ese número de 32

f=
  a=>32-Math.clz32(a)
  
pre {
    display: inline;
}
<input id=x type="number" oninput="y.innerHTML = f(x.value)" value=128><br>
<pre>Bits needed: <pre id=y>8</pre></pre>

Bassdrop Cumberwubwubwub
fuente
2
La alternativa a=>1+Math.log2(a)|0también es de 19 bytes.
Neil
55
@Neil 1+...|0grita menos tilde ! a=>-~Math.log2(a)es 18
edc65
@ edc65 cuento 17 ... pero sí, estaba seguro de que me faltaba algo, gracias por señalarlo.
Neil
@Neil Siéntase libre de publicarlo como una respuesta separada. Se utiliza un método diferente que mi respuesta por lo que se siente injusto utilizar el suyo para una cuenta de bytes reducida
Bassdrop Cumberwubwubwub
10

herramientas bash / Unix, 16 bytes

dc<<<2o$1n|wc -c

Guarde esto en un script y pase la entrada como argumento. Se imprimirá el número de bits necesarios para representar ese número en binario.

Aquí hay una explicación:

dc es una calculadora basada en pila. Su entrada, analizada en tokens, es:

2 - Empuje 2 en la pila.

o: saca un valor de la pila (que es 2) y conviértelo en la base de salida (de modo que la salida ahora está en binario).

El valor del argumento para el programa bash ($ 1): inserta ese argumento en la pila.

n: extraiga un valor de la pila (que es el número de entrada) e imprímalo (en binario, porque esa es la base de salida) sin nueva línea final.

Entonces el comando dc imprime el número en binario.

La salida de dc se canaliza al comando wc con la opción -c, que imprime el número de caracteres en su entrada.

El resultado final es imprimir el número de dígitos en la representación binaria del argumento.

Mitchell Spector
fuente
Buena elección de idioma, pero sería aún mejor si incluyeras una explicación.
NH.
@NH Gracias. He añadido una explicación.
Mitchell Spector
9

Hojas de cálculo de Google, 15 bytes

Toma la entrada de la celda A1y las salidas a la celda que contiene la fórmula

=Len(Dec2Bin(A1

o

=Int(1+Log(A1,2

o

=Int(Log(2*A1,2

Excel, 17 bytes

Igual que el anterior pero formateado para MS Excel

=Len(Dec2Bin(A1))

o

=Int(1+Log(A1,2))

o

=Int(Log(2*A1,2))
Taylor Scott
fuente
8

Pyth, 3 bytes

l.B

Conjunto de pruebas disponible aquí.

Explicación

l.BQ    Q is implicitly appended
   Q    eval(input)
 .B     convert Q to binary string
l       len(.B(Q))
Mike Bufardeci
fuente
Alternativamente: hslo .El, en el que lcalcula la base de registro 2, y / hso .Ecalcula el techo.
RK.
8

Jalea, 2 bytes

BL

Convierte a binario, encuentra longitud.

Rɪᴋᴇʀ
fuente
8

C #, 63 45 31 bytes

Guardado 18 bytes, gracias a Loovjo y TuukkaX

Guardado 14 bytes, gracias a Grax

 b=>1+(int)System.Math.Log(b,2);

Utiliza que un número decimal n tiene ⌊log2 (n) ⌋ + 1 bits, que se describe en esta página:

Número de bits en un entero decimal específico

Un entero positivo n tiene b bits cuando 2 ^ (b-1) ≤ n ≤ 2 ^ b - 1. Por ejemplo:

  • 29 tiene 5 bits porque 16 ≤ 29 ≤ 31, o 2 ^ 4 ≤ 29 ≤ 2 ^ 5 - 1
  • 123 tiene 7 bits porque 64 ≤ 123 ≤ 127, o 2 ^ 6 ≤ 123 ≤ 2 ^ 7 - 1
  • 967 tiene 10 bits porque 512 ≤ 967 ≤ 1023, o 2 ^ 9 ≤ 967 ≤ 2 ^ 10 - 1

Para números más grandes, puede consultar una tabla de potencias de dos para encontrar las potencias consecutivas que contienen su número.

Para ver por qué esto funciona, piense en las representaciones binarias de los enteros 2 ^ 4 a 2 ^ 5 - 1, por ejemplo. Son de 10000 a 11111, todos los valores posibles de 5 bits.

Usando logaritmos

El método anterior se puede establecer de otra manera: el número de bits es el exponente de la potencia más pequeña de dos mayor que su número. Puede afirmar eso matemáticamente como:

bspec = ⌊log2 (n) ⌋ + 1

Esa fórmula tiene tres partes:

  • log2 (n) significa el logaritmo en la base 2 de n, que es el exponente al que se eleva 2 para obtener n. Por ejemplo, log2 (123) ≈ 6.9425145. La presencia de una parte fraccional significa que n está entre potencias de dos.

  • ⌊X⌋ es el piso de x, que es la parte entera de x. Por ejemplo, ⌊6.9425145⌋ = 6. Puedes pensar en ⌊log2 (n) ⌋ como el exponente de la potencia más alta de dos en la representación binaria de n.

  • +1 lleva el exponente a la siguiente potencia más alta de dos. Puede pensar en este paso como el 2 ° 0 lugar de su número binario, que luego le da su número total de bits. Para nuestro ejemplo, eso es 6 + 1 = 7. Podría estar tentado a usar la función de techo - ceilingx⌉, que es el entero más pequeño mayor o igual a x - para calcular el número de bits como tal:

bspec = ⌈log2 (n) ⌉

Sin embargo, esto falla cuando n es una potencia de dos.

Horváth Dávid
fuente
Tienes un espacio extra allí ...)+ 1)...-> ...)+1.... Además, creo que puede devolver el valor directamente en lugar de imprimirlo.
Loovjo
Puede bajarlo a 31 haciendo b=>1+(int)System.Math.Log(b,2); La conversión int proporciona el mismo resultado que Math.Floor y no necesita la declaración de uso si solo hace referencia al Sistema una vez.
Grax32
6

C #, 32 bytes

n=>Convert.ToString(n,2).Length;

Convierte el parámetro en una cadena binaria y devuelve la longitud de la cadena.

Yytsi
fuente
4

Haskell, 20 bytes

succ.floor.logBase 2

Compone una función que toma el logaritmo base 2, pisos y agrega 1.

Pomo de la puerta
fuente
4

Befunge-93 , 23 21 Bytes

&>2# /# :_1>+#<\#1_.@

Befunge es un lenguaje de cuadrícula 2D (aunque solo estoy usando una línea).

&                      take integer input
 >2# /# :_             until the top of the stack is zero, halve and duplicate it
          1>+#<\#1_    find the length of the stack
                   .@  output that length as an integer and terminate the program

Pruébalo en línea!

JayDepp
fuente
@JamesHolderness Gracias, pensé que podría acortarse ya que tenía tantos hash / espacios, pero no pude conseguirlo.
JayDepp
17 bytes
Jo King
3

CJam , 5 bytes

ri2b,

Pruébalo en línea!

Lea input ( r), convierta a entero ( i), obtenga representación binaria ( 2b), obtenga length ( ,).

Martin Ender
fuente
3

QBIC , 18 bytes

:{~2^q>a|_Xq\q=q+1

¡Eso es increíble Mike! pero como funciona?

:        Read input as integer 'a'
{        Start an infinite DO-LOOP
~2^q>a   If 2 to the power of q (which is 1 by default) is greater than a
|_Xq     Then quit, printing q
\q=q+1   Else, increment q
[LOOP is closed implicitly by QBIC]
Steenbergh
fuente
3

Java 8, 34 27 bytes

¡Por una vez, Java tiene algunas funciones útiles! Ahora, solo necesitamos algunos nombres más cortos ...

x->x.toString(x,2).length()

Pruébalo en línea!

Por supuesto, puede hacer esto sin construir ( ver la respuesta de Snowman ), pero para un conteo de bytes más alto.

FlipTack
fuente
3

Octava, 19 bytes

@(x)nnz(dec2bin(x))    % or
@(x)nnz(de2bi(x)+1)    % or
@(x)nnz(de2bi(x)<2)    % or
@(x)numel(de2bi(x))    % or
@(x)rows(de2bi(x'))

Octave tiene dos funciones para convertir números decimales en números binarios.

dec2binconvierte un número en una cadena de caracteres 1y 0(valores ASCII 48y 49). La longitud de la cadena será igual al número necesario de bits, a menos que se especifique lo contrario. Dado que los personajes 1y 0no son cero, podemos usar nnzpara encontrar el número de elementos de este tipo: @(x)nnz(dec2bin(x)). Esto es de 19 bytes, por lo que está relacionado con la otra respuesta Octave de Luis Mendo .

¿Podemos hacerlo mejor usando de2bi?

de2bies una función que devuelve los números binarios como un vector con los números 1y 0como enteros, no como caracteres. de2biobviamente es dos bytes más corto que dec2bin, pero ya no podemos usarlo nnz. Nosotros podemos utilizar nnzsi bien añadimos 1a todos los elementos, o lo hace en un vector lógico con sólo truevalores. @(x)nnz(de2bi(x)+1)y @(x)nnz(de2bi(x)<2)son ambos de 19 bytes. Utilizando numeltambién nos dará 19 bytes, @(x)numel(de2bi(x)).

rowses un byte más corto que numel, pero de2bidevuelve un vector horizontal, por lo que debe transponerse. @(x)rows(de2bi(x)')Resulta que también son 19 bytes.

Stewie Griffin
fuente
2

Retina ,  44  23 bytes

Requiere demasiada memoria para ejecutarse para valores de entrada grandes. Se convierte en unario, luego se divide repetidamente por 2, contando cuántas veces hasta llegar a cero. El recuento de bytes asume la codificación ISO 8859-1.

.*
$*
+`^(1+)1?\1
$1_
.

Pruébalo en línea

mbomb007
fuente
1
No estoy seguro de que esto sea válido. Este no es un caso de "requiere más memoria de la que probablemente tenga", sino "requiere más memoria de la que Retina puede manejar". En particular, la conversión inicial a unario fallará para las entradas de orden 2 ^ 30 y superiores, debido a limitaciones en la implementación de Retina.
Martin Ender
Si es válido, podría acortarse mucho: tio.run/nexus/retina#@6@nxaWixaWdEKdhqK1paB9jyKViGM@l9/@/saUhAA
Martin Ender