Para qualquer número inteiro positivo de 32 bits ( 1 ≤ n ≤ 0xFFFFFFFF), o número de bits necessário para representar esse número inteiro.

Casos de teste

| 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

Então f(16), imprimiria ou retornaria5

Isso é código-golfe . O menor código em bytes ganha

05AB1E , 2 bytes

bg

Experimente online!

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>

Montagem x86, 4 bytes

Assumindo constante em EBX:

bsr eax,ebx
inc eax

EAX contém o número de bits necessários para Constant.

Bytes: ☼¢├@

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

Python , 14 bytes

int.bit_length

Experimente online!

Labirinto , 13 12 bytes

 ?
_:
2/#(!@

Experimente online!

Explicação

O programa simplesmente divide repetidamente a entrada por 2 até que seja zero. O número de etapas é monitorado duplicando o valor em cada etapa. Depois de reduzido a zero, imprimimos a profundidade da pilha (menos 1).

O programa inicia no ?qual lê a entrada. O loop principal é o bloco 2x2 abaixo, no sentido anti-horário:

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

Quando o valor é zero após uma iteração completa, o bit linear no final é executado:

#   Push stack depth.
(   Decrement.
!   Print.
@   Terminate.

C, 31 bytes

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

... Então pensei em recursão. De obscuro para óbvio, e com um quarto do comprimento caiu.

Veja ao vivo em Coliru

C, 43 bytes

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

Chamar fcom um valor não assinado (por exemplo f(42u)) "retornará" seu tamanho de bit. Até funciona 0u!

Ungolfed e explicado: (barras invertidas omitidas)

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

Veja ao vivo em Coliru

Mathematica, 9 bytes

BitLength

Alternativamente:

Floor@Log2@#+1&
#~IntegerLength~2&

Perl 6 , 7 bytes

*.msb+1

Tente

Explicação:

* torna-o um lambda WhateverCode e indica onde colocar a entrada

.msb em um Int retorna o índice do bit mais significativo (baseado em 0)

+1é combinado no lambda e adiciona um ao resultado final da chamada .msb.

Macro do pré-processador C (com extensões gcc), 26

#define f 32-__builtin_clz

Usa o built -in-zeros da contagem do GCC .

Chame isso como uma função, por exemplo f(100).

Experimente online .

Retina , 56 37 bytes

Esta solução funciona com todos os valores de entrada necessários.

O maior problema que Retina enfrenta nesse desafio é o fato de suas seqüências terem um comprimento máximo de 2 ^ 30 caracteres, portanto, a maneira usual de lidar com números (representação unária) não funciona com valores maiores que 2 ^ 30.

Para resolver esse problema, adotei uma abordagem diferente, mantendo uma espécie de representação decimal dos números, mas onde cada dígito é escrito em unário (chamarei essa representação de digitunário ). Por exemplo, o número 341seria escrito como 111#1111#1#num dígito. Com essa representação, agora podemos trabalhar com números de até 2^30/10dígitos (~ cem milhões de dígitos). É menos prático que o padrão unário para aritmética arbitrária, mas com um pouco de esforço, poderíamos realizar qualquer tipo de operação.

OBSERVAÇÃO: em teoria, o digitunary poderia usar qualquer outra base (por exemplo, o binário 110estaria 1#1##na base 2 do digitunary), mas, como o Retina possui builtins para converter entre decimal e unário e nenhuma maneira direta de lidar com outras bases, o decimal é provavelmente a base mais gerenciável.

O algoritmo que usei faz divisões inteiras sucessivas por dois até chegarmos a zero, o número de divisões que criamos é o número de bits necessários para representar esse número.

Então, como é que vamos dividir por dois em dois dígitos? Aqui está o trecho de Retina que faz isso:

(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

Essa substituição é suficiente para dividir um número digitunário por 2; basta remover 0,5s possíveis do final, se o número original for ímpar.

Então, aqui está o código completo, continuamos dividindo por dois até que ainda haja dígitos no número e colocamos um literal nna frente da string a cada iteração: o número de nno final é o 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

Experimente online!

Grande refatoração com muitas boas idéias que jogaram cerca de um terço do comprimento, tudo graças a Martin Ender!

A idéia principal é usar _como símbolo unário: dessa maneira, podemos usar dígitos regulares em nossa string, desde que os convertamos de volta para _s quando necessário: isso permite salvar muitos bytes na divisão e na inserção de múltiplos dígitos.

Aqui está o 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

Experimente online!

Ruby, 19 16 bytes

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

Obrigado Jordan por jogar fora 3 bytes

Jolf, 2 bytes

lB

Basta converter em binário e, em seguida, encontre o comprimento.

Julia 0.4 , 14 bytes

!n=log2(2n)÷1

Experimente online!

JavaScript ES6, 19 bytes

a=>32-Math.clz32(a)

Math.clz32retorna o número de zero bits à esquerda na representação binária de 32 bits de um número. Então, para obter a quantidade de bits necessária, tudo o que precisamos fazer é subtrair esse 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>

ferramentas bash / Unix, 16 bytes

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

Salve isso em um script e passe a entrada como argumento. O número de bits necessários para representar esse número em binário será impresso.

Aqui está uma explicação:

dc é uma calculadora baseada em pilha. Sua entrada, analisada em tokens, é:

2 - Pressione 2 na pilha.

o - Retire um valor da pilha (que é 2) e torne-o a base de saída (para que a saída agora seja binária).

O valor do argumento para o programa bash ($ 1) - Empurre esse argumento na pilha.

n - Retire um valor da pilha (que é o número de entrada) e imprima-o (em binário, porque essa é a base de saída) sem nova linha final.

Portanto, o comando dc imprime o número em binário.

A saída de dc é canalizada para o comando wc com a opção -c, que imprime o número de caracteres em sua entrada.

O resultado final é imprimir o número de dígitos na representação binária do argumento.

Planilhas Google, 15 bytes

Leva a entrada da célula A1e sai para a célula que contém a fórmula

=Len(Dec2Bin(A1

ou

=Int(1+Log(A1,2

ou

=Int(Log(2*A1,2

Excel, 17 bytes

O mesmo que acima, mas formatado para o MS Excel

=Len(Dec2Bin(A1))

ou

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

ou

=Int(Log(2*A1,2))

Pitão, 3 bytes

l.B

Conjunto de testes disponível aqui.

Explicação

l.BQ    Q is implicitly appended
   Q    eval(input)
 .B     convert Q to binary string
l       len(.B(Q))

Geléia, 2 bytes

BL

Converte em binário, encontra comprimento.

C #, 63 45 31 bytes

Economizou 18 bytes, graças a Loovjo e TuukkaX

Economizou 14 bytes, graças ao Grax

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

Ele usa que um número decimal n tem ⌊log2 (n) ⌋ + 1 bits, descrito nesta página:

Número de bits em um número inteiro decimal específico

Um número inteiro positivo n tem b bits quando 2 ^ (b-1) ≤ n ≤ 2 ^ b - 1. Por exemplo:

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

Para números maiores, você pode consultar uma tabela de potências de dois para encontrar as potências consecutivas que contêm seu número.

Para ver por que isso funciona, pense nas representações binárias dos números inteiros 2 ^ 4 a 2 ^ 5 - 1, por exemplo. São de 10000 a 11111, todos os valores possíveis de 5 bits.

Usando logaritmos

O método acima pode ser dito de outra maneira: o número de bits é o expoente da menor potência de dois maior que o seu número. Você pode declarar isso matematicamente como:

bspec = log2 (n) + 1

Essa fórmula tem três partes:

• log2 (n) significa o logaritmo na base 2 de n, que é o expoente ao qual 2 é elevado para obter n. Por exemplo, log2 (123) ≈ 6.9425145. A presença de uma parte fracionária significa que n está entre potências de dois.

• ⌊X⌋ é o piso de x, que é a parte inteira de x. Por exemplo, .96.9425145⌋ = 6. Você pode pensar em 2log2 (n) ⌋ como o expoente da potência mais alta de dois na representação binária de n.

• +1 leva o expoente para a próxima potência mais alta de dois. Você pode pensar nesta etapa como responsável pelo 2 ° 0 ° lugar do seu número binário, o que lhe dá o número total de bits. Para o nosso exemplo, isso é 6 + 1 = 7. Você pode tentar usar a função de teto - ⌈x⌈, que é o menor número inteiro maior que ou igual a x - para calcular o número de bits da seguinte forma:

bspec = log2 (n)

No entanto, isso falha quando n é uma potência de dois.

C #, 32 bytes

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

Converte o parâmetro em uma string binária e retorna o comprimento da string.

Haskell, 20 bytes

succ.floor.logBase 2

Compõe uma função que usa o logaritmo base 2, pisos e adiciona 1.

Befunge-93 , 23 21 bytes

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

Befunge é uma linguagem baseada em grade 2D (embora eu esteja usando apenas uma linha).

&                      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

Experimente online!

Água-viva , 4 bytes

p#bi

Experimente online!

Print ( p), o comprimento ( #) da representação binária ( b) da entrada ( i).

CJam , 5 bytes

ri2b,

Experimente online!

Leia input ( r), converta para número inteiro ( i), obtenha representação binária ( 2b), obtenha comprimento ( ,).

Oitava , 19 bytes

@(x)ceil(log2(x+1))

Função anônima que adiciona 1, calcula o logaritmo binário e arredonda para cima.

Experimente online!

QBIC , 18 bytes

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

Mike incrível! Mas como isso 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]

Java 8, 34 27 bytes

Pela primeira vez, o Java tem alguns recursos úteis! Agora, só precisamos de nomes mais curtos ...

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

Experimente online!

Obviamente, você pode fazer isso sem os recursos internos ( consulte a resposta do Snowman ), mas para obter uma contagem maior de bytes.

Oitava, 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'))

Oitava tem duas funções para converter números decimais em números binários.

dec2binconverte um número em uma sequência de caracteres 1e 0(valores ASCII 48e 49). O comprimento da string será igual ao número necessário de bits, a menos que especificado de outra forma. Uma vez que os caracteres 1e 0são diferentes de zero, podemos usar nnzpara encontrar o número de elementos como este: @(x)nnz(dec2bin(x)). São 19 bytes, por isso está relacionado à outra resposta oitava de Luis Mendo .

Podemos fazer melhor usando de2bi?

de2bié uma função que retorna os números binários como um vetor com os números 1e 0como números inteiros, não caracteres. de2bié obviamente dois bytes menor que dec2bin, mas não podemos mais usar nnz. Nós podemos usar nnzse quer adicionar 1a todos os elementos, ou torna-lo em um vetor lógico com apenas truevalores. @(x)nnz(de2bi(x)+1)e @(x)nnz(de2bi(x)<2)são ambos 19 bytes. Usar numeltambém nos dará 19 bytes @(x)numel(de2bi(x)),.

rowsé um byte menor que numel, mas de2biretorna um vetor horizontal; portanto, ele deve ser transposto. @(x)rows(de2bi(x)')acontece que também tem 19 bytes.

Pyke, 3 bytes

b2l

Experimente aqui!

Retina ,  44  23 bytes

Requer muita memória para executar para grandes valores de entrada. Converte em unário, depois divide repetidamente por 2, contando quantas vezes até atingir zero. A contagem de bytes assume a codificação ISO 8859-1.

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

Experimente online