Pour tout entier positif sur 32 bits ( 1 ≤ n ≤ 0xFFFFFFFF), indiquez le nombre de bits nécessaires pour représenter cet entier.

Cas de test

| 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

Donc f(16), imprimer ou retourner5

C'est du code-golf . Le code le plus court en octets gagne

05AB1E , 2 octets

bg

Essayez-le en ligne!

JavaScript (ES6), 18 octets

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>

Assemblage x86, 4 octets

En supposant Constant dans EBX:

bsr eax,ebx
inc eax

EAX contient le nombre de bits nécessaires pour Constant.

Octets: ☼¢├@

Hexadécimal: ['0xf', '0xbd', '0xc3', '0x40']

Python , 14 octets

int.bit_length

Essayez-le en ligne!

Labyrinth , 13 à 12 octets

 ?
_:
2/#(!@

Essayez-le en ligne!

Explication

Le programme divise simplement l’entrée par 2 jusqu’à zéro. Le nombre d'étapes est maintenu en dupliquant la valeur à chaque étape. Une fois réduit à zéro, nous imprimons la profondeur de la pile (moins 1).

Le programme commence par le ?qui lit l'entrée. La boucle principale est alors le bloc 2x2 ci-dessous, en sens antihoraire:

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

Une fois que la valeur est zéro après une itération complète, le bit linéaire à la fin est exécuté:

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

C, 31 octets

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

... Puis j'ai pensé à la récursivité. D'obscur à évident, et avec un quart de la longueur déposée.

Voir en direct sur Coliru

C, 43 octets

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

Appeler favec une valeur non signée (par exemple f(42u)) "retournera" sa longueur en bits. Même travaille pour 0u!

Non golfé et expliqué: (barres obliques inverses omises)

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

Voir en direct sur Coliru

Mathematica, 9 octets

BitLength

Alternativement:

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

Perl 6 , 7 octets

*.msb+1

L'essayer

Explication:

* le fait devenir un lambda WhateverCode, et indique où mettre l'entrée

.msb sur un Int retourne l'index du bit le plus significatif (basé sur 0)

+1est combiné dans le lambda, et ajoute un au résultat final de l'appel .msb.

Macro de préprocesseur C (avec extensions gcc), 26

#define f 32-__builtin_clz

Utilise le nombre de zéros de compte intégrés de GCC .

Appelez cela comme une fonction, par exemple f(100).

Essayez-le en ligne .

Retina , 56 37 bytes

Cette solution fonctionne avec toutes les valeurs d'entrée requises.

Le problème le plus important auquel Retina est confrontée dans ce défi est le fait que ses chaînes ont une longueur maximale de 2 ^ 30 caractères. Par conséquent, la manière habituelle de traiter les nombres (représentation unaire) ne fonctionne pas avec des valeurs supérieures à 2 ^ 30.

Afin de résoudre ce problème, j’ai adopté une approche différente en conservant une sorte de représentation décimale des nombres, mais où chaque chiffre est écrit en unaire (je vais appeler cette représentation numérique ). Par exemple, le nombre 341serait écrit comme 111#1111#1#dans digitunary. Avec cette représentation, nous pouvons maintenant travailler avec des nombres allant jusqu'à un 2^30/10chiffre (environ cent millions de chiffres). C'est moins pratique que le unaire classique pour l'arithmétique arbitraire, mais avec un peu d'effort, nous pourrions faire n'importe quel type d'opération.

REMARQUE: digitunary pourrait théoriquement utiliser n'importe quelle autre base (par exemple binaire 110serait 1#1##en base 2 digitunary), mais puisque Retina a été conçu pour effectuer la conversion entre décimales et unaires et qu'il n'existe aucun moyen direct de traiter d'autres bases, la décimale est probablement la base la plus facile à gérer.

L'algorithme que j'ai utilisé consiste à faire des divisions entières successives par deux jusqu'à atteindre zéro, le nombre de divisions que nous avons fait est le nombre de bits nécessaires pour représenter ce nombre.

Alors, comment divisons-nous par deux en numérique? Voici l'extrait de la rétine qui le fait:

(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

Ce remplacement est suffisant pour diviser un nombre numérique par 2, il suffit d’enlever les .5 possibles à la fin si le nombre initial était impair.

Donc, voici le code complet, nous continuons à diviser par deux jusqu'à ce qu'il y ait encore des chiffres dans le nombre, et mettons un littéral ndevant la chaîne à chaque itération: le nombre nà la fin est le résultat.

.                  |
$*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

Essayez-le en ligne!

Grand refactoring avec beaucoup de bonnes idées qui ont golfé environ un tiers de la longueur, tout cela grâce à Martin Ender!

L’idée principale est d’utiliser _comme symbole unaire: de cette manière, nous pouvons utiliser des chiffres normaux dans notre chaîne, à condition de les reconvertir en _s lorsque cela est nécessaire: cela nous permet d’économiser de nombreux octets lors de la division et de l’insertion de multiples. chiffres.

Voici le code:

<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

Essayez-le en ligne!

Ruby, 19 16 octets

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

Merci Jordan pour le golf 3 octets

Jolf, 2 octets

lB

Il suffit de convertir en binaire, puis de trouver la longueur.

Julia 0.4 , 14 octets

!n=log2(2n)÷1

Essayez-le en ligne!

JavaScript ES6, 19 octets

a=>32-Math.clz32(a)

Math.clz32renvoie le nombre de bits zéro dans la représentation binaire 32 bits d'un nombre. Donc, pour obtenir le nombre de bits nécessaires, il suffit de soustraire ce nombre 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>

Outils bash / Unix, 16 octets

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

Enregistrez ceci dans un script et transmettez l'entrée sous forme d'argument. Le nombre de bits requis pour représenter ce nombre en binaire sera imprimé.

Voici une explication:

dc est une calculatrice basée sur des piles. Son entrée, analysée en jetons, est la suivante:

2 - Poussez 2 sur la pile.

o - Extrait une valeur de la pile (qui est 2) et en fait la base de sortie (la sortie est maintenant en binaire).

La valeur de l'argument du programme bash ($ 1) - Envoie cet argument dans la pile.

n - Extrait une valeur de la pile (qui est le numéro d'entrée) et l'affiche (en binaire, car c'est la base de sortie) sans fin de nouvelle ligne.

Donc, la commande dc affiche le nombre en binaire.

La sortie de dc est transmise à la commande wc avec l’option -c, qui affiche le nombre de caractères de son entrée.

Le résultat final consiste à imprimer le nombre de chiffres dans la représentation binaire de l'argument.

Google Sheets, 15 octets

Prend les entrées de la cellule A1et les sorties dans la cellule qui contient la formule

=Len(Dec2Bin(A1

ou

=Int(1+Log(A1,2

ou

=Int(Log(2*A1,2

Excel, 17 octets

Comme ci-dessus mais formaté pour MS Excel

=Len(Dec2Bin(A1))

ou

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

ou

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

Pyth, 3 octets

l.B

Suite de test disponible ici.

Explication

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

Gelée, 2 octets

BL

Convertit en binaire, trouve la longueur.

C #, 63 45 31 octets

Sauvegardé 18 octets, grâce à Loovjo et TuukkaX

14 octets sauvés, merci à Grax

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

Il utilise, qu'un nombre décimal n a ⌊log2 (n) ⌋ + 1 bits, ce qui est décrit sur cette page:

Nombre de bits dans un entier décimal spécifique

Un entier positif n a b bits lorsque 2 ^ (b-1) ≤ n ≤ 2 ^ b - 1. Par exemple:

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

Pour des nombres plus importants, vous pouvez consulter une table des pouvoirs de deux pour trouver les pouvoirs consécutifs contenant votre numéro.

Pour voir pourquoi cela fonctionne, pensez aux représentations binaires des entiers 2 ^ 4 à 2 ^ 5 - 1, par exemple. Ils sont compris entre 10000 et 11111, toutes les valeurs possibles sur 5 bits.

Utilisation de logarithmes

La méthode ci-dessus peut être énoncée d'une autre manière: le nombre de bits est l'exposant de la plus petite puissance de deux supérieure à votre nombre. Vous pouvez indiquer cela mathématiquement:

bspec = ⌊log2 (n) + 1

Cette formule comporte trois parties:

• log2 (n) signifie le logarithme en base 2 de n, qui est l'exposant auquel 2 est élevé pour obtenir n. Par exemple, log2 (123) ≈ 6.9425145. La présence d'une partie fractionnaire signifie que n est compris entre deux puissances.

• ⌊X⌋ est le plancher de x, qui est la partie entière de x. Par exemple, .96.9425145⌋ = 6. Vous pouvez considérer ⌊log2 (n) ⌋ comme l'exposant de la plus grande puissance de deux dans la représentation binaire de n.

• +1 prend l'exposant à la puissance immédiatement supérieure de deux. Vous pouvez considérer cette étape comme une comptabilisation de la 2 ^ 0e place de votre nombre binaire, qui vous donne ensuite son nombre total de bits. Pour notre exemple, 6 + 1 = 7. Vous pourriez être tenté d'utiliser la fonction de plafond - x⌉, qui est le plus petit entier supérieur ou égal à x - pour calculer le nombre de bits en tant que tel:

bspec = ⌈log2 (n) ⌉

Cependant, cela échoue lorsque n est une puissance de deux.

C #, 32 octets

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

Convertit le paramètre en chaîne binaire et renvoie la longueur de la chaîne.

Haskell, 20 octets

succ.floor.logBase 2

Compose une fonction qui prend en logarithme 2, étages et ajoute 1.

Befunge-93 , 23 à 21 octets

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

Befunge est un langage basé sur une grille 2D (bien que je n’utilise qu’une seule ligne).

&                      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

Essayez-le en ligne!

Méduse , 4 octets

p#bi

Essayez-le en ligne!

Print ( p), la longueur ( #) de la représentation binaire ( b) de l'entrée ( i).

CJam , 5 octets

ri2b,

Essayez-le en ligne!

Lire input ( r), convertir en integer ( i), obtenir une représentation binaire ( 2b), obtenir length ( ,).

Octave , 19 octets

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

Fonction anonyme qui ajoute 1, calcule le logarithme binaire et arrondit.

Essayez-le en ligne!

QBIC , 18 octets

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

C'est incroyable Mike! Mais comment ça fonctionne?

:        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 octets

Pour une fois, Java a quelques fonctions utiles! Maintenant, nous avons juste besoin de noms plus courts ...

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

Essayez-le en ligne!

Bien sûr, vous pouvez le faire sans fonctions intégrées ( voir la réponse de Snowman ), mais pour un nombre d'octets plus élevé.

Octave, 19 octets

@(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 a deux fonctions pour convertir les nombres décimaux en nombres binaires.

dec2binconvertit un nombre en une chaîne de caractères 1et 0(valeurs ASCII 48et 49). La longueur de la chaîne sera égale au nombre de bits nécessaire, sauf indication contraire. Étant donné que les caractères 1et ne 0sont pas nuls, nous pouvons utiliser nnzpour trouver le nombre d'éléments comme celui - ci: @(x)nnz(dec2bin(x)). C'est 19 octets, donc c'est à égalité avec l'autre réponse Octave de Luis Mendo .

Pouvons-nous mieux utiliser de2bi?

de2biest une fonction qui renvoie les nombres binaires sous forme de vecteur avec les nombres 1et 0sous forme d’entiers, pas de caractères. de2biest évidemment deux octets plus court que dec2bin, mais nous ne pouvons plus utiliser nnz. Nous pouvons utiliser nnzsi nous ajoutons 1tous les éléments ou si nous en faisons un vecteur logique avec uniquement des truevaleurs. @(x)nnz(de2bi(x)+1)et @(x)nnz(de2bi(x)<2)sont tous deux 19 octets. En utilisantnumel également nous donner 19 octets, @(x)numel(de2bi(x)).

rowsest un octet plus court que numel, mais de2birenvoie un vecteur horizontal, il doit donc être transposé. @(x)rows(de2bi(x)')Il se trouve qu’il s’agit également de 19 octets.

Pyke, 3 octets

b2l

Essayez-le ici!

Retina ,  44  23 octets

Nécessite trop de mémoire pour pouvoir exécuter des valeurs d’entrée importantes. Convertit en unaire, puis divise à plusieurs reprises par 2, en comptant combien de fois jusqu'à atteindre zéro. Le nombre d'octets suppose un codage ISO 8859-1.

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

Essayez-le en ligne