For any positive 32-bit integer (1 ≤ n ≤ 0xFFFFFFFF) output the number of bits needed to represent that integer.

Test cases

| 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

So f(16) would print or return 5

This is . Shortest code in bytes wins

share|improve this question
2  
This is the ceiling of the base-2 logarithm. – orlp Dec 27 at 16:51
18  
@orlp It actually is floor(log2(num))+1 – Kritixi Lithos Dec 27 at 16:52
2  
@KritixiLithos Right. – orlp Dec 27 at 18:46
2  
Nevermind, just realized that the distinct is important when num is a power of two. – Brian J Dec 27 at 20:22
8  
This is a trivial challenge with a lot of trivial solutions. There are however some non-trivial solutions too. To voters: Please read the first sentence of this meta post before upvoting builtin functions. (humbly taken from this comment) – Kritixi Lithos Dec 28 at 8:23

54 Answers 54

up vote 22 down vote accepted

05AB1E, 2 bytes

bg

Try it online!

share|improve this answer
13  
Esoteric language won again... bg – devRicher Dec 27 at 16:06
17  
@devRicher I expect to be beaten by a 1 byte solution still, to be honest. – carusocomputing Dec 27 at 16:08
8  
At least this answer gets it's upvotes; it's not in the bg. – SeeOneRhino Dec 27 at 21:59
    
bg in gaming means bad game :) – YoYoYonnY 1 hour ago

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>

share|improve this answer
    
This is one of the few non-trivial solution here. Nice tactic! – Kritixi Lithos Dec 27 at 19:01
1  
Should it be n>>>1 to support n > 0x7FFFFFFF? – Arnauld Dec 27 at 22:56
    
@Arnauld Hmm, didn't know >> failed on n that high. Thanks. – ETHproductions Dec 28 at 0:41
    
Nice, my first attempt was f=(a,b=1)=>a>1?f(a>>1,++b):b – Bassdrop Cumberwubwubwub Dec 28 at 9:58

x86 Assembly, 4 bytes

Assuming Constant in EBX:

bsr eax,ebx
inc eax

EAX contains the number of bits necessary for Constant.

Bytes: ☼¢├@

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

share|improve this answer
2  
Could you please include a hexdump of the actual 8 byte compiled x86 Assembly code? – Loovjo Dec 27 at 19:37
    
Did so. And thank you, because I realized I made a mistake. I added an "inc eax" to fit the rules. I lost a byte. :( – z0rberg's Dec 27 at 19:58
    
Oh wow you changed my post to proper formatting. Thanks for correcting it! – z0rberg's Dec 27 at 20:03
1  
By the way, Assembly submissions can assume that the input is already stored in a specific register, so I think you could shave off a few bytes that way. – Loovjo Dec 27 at 20:03
    
Oh that's nice! Well, then it's down to four! – z0rberg's Dec 27 at 20:06

Mathematica, 9 bytes

BitLength

Alternatively:

Floor@Log2@#+1&
#~IntegerLength~2&
share|improve this answer

Python, 14 bytes

int.bit_length

Try it online!

share|improve this answer
    
It works in Python 2, too. – vaultah Dec 27 at 16:13
1  
It does indeed. Forgot Python 2‘s int was 64 bits wide, not 32 bits. – Dennis Dec 27 at 16:17
    
Python 3's bit_length is bit_length(). – dfernan Dec 28 at 19:36
2  
@dfernan This is not a function call; it's a function. If n is an int, int.bit_length(n) and n.bit_length() do exactly the same. – Dennis Dec 28 at 19:43
2  
@dfernan int.bit_length(n) is a function call, and thus a snippet that assumes the input is stored in a variable. This is not allowed by our rules, so appending (n) would make this answer invalid. However, int.bit_length evaluates to a function and can be saved in a variable for later use. This is allowed by default. – Dennis 2 days ago

C, 31 bytes

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

... Then I thought about recursion. From obscure to obvious, and with one fourth of the length dropped off.

See it live on Coliru


C, 43 bytes

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

Calling f with an unsigned value (e.g. f(42u)) will "return" its bit length. Even works for 0u !

Ungolfed and explained: (backslashes omitted)

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

See it live on Coliru

share|improve this answer
    
OP guarantees n>=1, so n?...:0 is not necessary. – Mad Physicist 2 days ago
    
@MadPhysicist well I do have to stop the recursion somewhere, don't I ;) – Quentin 2 days ago
    
OIC. Didn't read carefully, feel like a dumbass now. Neat answer either way. – Mad Physicist 2 days ago
    
@MadPhysicist no worries, thank you very much :) – Quentin 2 days ago

Perl 6, 7 bytes

*.msb+1

Try it

Explanation:

* makes it become a WhateverCode lambda, and indicates where to put the input

.msb on an Int returns the index of the most significant bit (0 based)

+1 is combined into the lambda, and adds one to the eventual result of calling .msb.

share|improve this answer

Labyrinth, 13 12 bytes

 ?
_:
2/#(!@

Try it online!

Explanation

The program simply repeatedly divides the input by 2 until it's zero. The number of steps are kept track of by duplicating the value at each step. Once it's reduced to zero we print the stack depth (minus 1).

The program starts at the ? which reads the input. The main loop is then the 2x2 block below, going counter-clockwise:

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

Once the value is zero after a full iteration, the linear bit at the end is executed:

#   Push stack depth.
(   Decrement.
!   Print.
@   Terminate.
share|improve this answer
3  
This solution is complete - it takes input and provides the answer, and does not utilise any existing function for this specific purpose - it calculates the answer manually. To me this is more in the spirit of the game than most other answers. – Johan Dec 27 at 20:39

C preprocessor macro (with gcc extensions), 26

#define f 32-__builtin_clz

Uses GCC's count-leading-zeros builtin.

Call this as a function, e.g. f(100).

Try it online.

share|improve this answer
    
Oh wow, I thought about using a builtin but dropped the idea because I thought it was going to be too long... Well played. – Quentin Dec 28 at 8:55

JavaScript ES6, 19 bytes

a=>32-Math.clz32(a)

Math.clz32 returns the number of leading zero bits in the 32-bit binary representation of a number. So to get the amount of bits needed, all we need to do is substract that number from 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>

share|improve this answer
1  
The alternative a=>1+Math.log2(a)|0 is also 19 bytes. – Neil Dec 27 at 18:24
4  
@Neil 1+...|0 screams minus tilde! a=>-~Math.log2(a) is 18 – edc65 Dec 28 at 12:37
    
@edc65 I count 17... but yes, I was sure I was missing something, thanks for pointing it out. – Neil Dec 28 at 17:10
    
@Neil Feel free to post it as a seperate answer. It uses a different method than my answer so it would feel unfair to use yours for a reduced byte count – Bassdrop Cumberwubwubwub 2 days ago

Ruby, 19 16 bytes

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

Thanks Jordan for golfing off 3 bytes

share|improve this answer
    
+1 for brilliance – DepressedDaniel Dec 28 at 3:01
    
You can save a byte with %: ->n{("%b"%n).size}. – Jordan Dec 28 at 6:49
3  
Wait, this is shorter: ->n{"%b"%n=~/$/}. – Jordan Dec 28 at 6:51

Jolf, 2 bytes

lB

Just convert to binary and then find the length.

share|improve this answer

bash / Unix tools, 16 bytes

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

Save this in a script, and pass the input as an argument. The number of bits required to represent that number in binary will be printed.

Here's an explanation:

dc is a stack-based calculator. Its input, parsed into tokens, is:

2 — Push 2 on the stack.

o — Pop a value off the stack (which is 2) and make it the output base (so output is now in binary).

The value of the argument to the bash program ($1) — Push that argument on the stack.

n — Pop a value off the stack (which is the input number) and print it (in binary, because that's the output base) with no trailing newline.

So the dc command prints the number in binary.

The output of dc is piped to the command wc with the -c option, which prints the number of characters in its input.

The end result is to print the number of digits in the binary representation of the argument.

share|improve this answer
    
Nice choice of language, but it would be even cooler if you included an explanation. – NH. 9 hours ago
    
@NH Thanks. I've added an explanation. – Mitchell Spector 4 hours ago

Pyth, 3 bytes

l.B

Test suite available here.

Explanation

l.BQ    Q is implicitly appended
   Q    eval(input)
 .B     convert Q to binary string
l       len(.B(Q))
share|improve this answer

Jelly, 2 bytes

BL

Converts to binary, finds length.

share|improve this answer

Julia 0.4, 14 bytes

!n=log2(2n)÷1

Try it online!

share|improve this answer
2  
Much more interesting than the other answers. +1 – carusocomputing Dec 27 at 17:20

Excel, 17 Bytes

Takes input from cell A1

=LEN(DEC2BIN(A1))

or

=INT(LOG(A1,2)+1)

or

=INT(LOG(2*A1,2))
share|improve this answer

C#, 63 45 31 bytes

Saved 18 bytes, thanks to Loovjo, and TuukkaX

Saved 14 bytes, thanks to Grax

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

It uses, that a decimal number n has ⌊log2(n)⌋+1 bits, which is described on this page:

Number of Bits in a Specific Decimal Integer

A positive integer n has b bits when 2^(b-1) ≤ n ≤ 2^b – 1. For example:

  • 29 has 5 bits because 16 ≤ 29 ≤ 31, or 2^4 ≤ 29 ≤ 2^5 – 1
  • 123 has 7 bits because 64 ≤ 123 ≤ 127, or 2^6 ≤ 123 ≤ 2^7 – 1
  • 967 has 10 bits because 512 ≤ 967 ≤ 1023, or 2^9 ≤ 967 ≤ 2^10 – 1

For larger numbers, you could consult a table of powers of two to find the consecutive powers that contain your number.

To see why this works, think of the binary representations of the integers 2^4 through 2^5 – 1, for example. They are 10000 through 11111, all possible 5-bit values.

Using Logarithms

The above method can be stated another way: the number of bits is the exponent of the smallest power of two greater than your number. You can state that mathematically as:

bspec = ⌊log2(n)⌋ + 1

That formula has three parts:

  • log2(n) means the logarithm in base 2 of n, which is the exponent to which 2 is raised to get n. For example, log2(123) ≈ 6.9425145. The presence of a fractional part means n is between powers of two.

  • ⌊x⌋ is the floor of x, which is the integer part of x. For example, ⌊6.9425145⌋ = 6. You can think of ⌊log2(n)⌋ as the exponent of the highest power of two in the binary representation of n.

  • +1 takes the exponent to the next higher power of two. You can think of this step as accounting for the 2^0th place of your binary number, which then gives you its total number of bits. For our example, that’s 6 + 1 = 7. You might be tempted to use the ceiling function — ⌈x⌉, which is the smallest integer greater than or equal to x — to compute the number of bits as such:

bspec = ⌈log2(n)⌉

However, this fails when n is a power of two.

share|improve this answer
    
You have an extra space in there ...)+ 1)... -> ...)+1.... Also, I think you can return the value directly instead of printing it. – Loovjo Dec 27 at 21:05
    
You can return the number instead of printing it, which means you don't need the curly brackets anymore nor Console.Write. Also, there is an useless whitespace at + 1 :) – TuukkaX Dec 27 at 21:08
    
You can drop it down to 31 by doing b=>1+(int)System.Math.Log(b,2); The int conversion provides the same output as Math.Floor and you don't need the using statement if you only reference System once. – Grax Dec 28 at 18:35

Haskell, 20 bytes

succ.floor.logBase 2

Composes a function that takes logarithm base 2, floors, and adds 1.

share|improve this answer

C#, 32 bytes

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

Converts the parameter to a binary string and returns the length of the string.

share|improve this answer

Befunge-93, 23 21 Bytes

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

Befunge is a 2D grid-based language (although I'm only using one line).

&                      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

Try it online!

share|improve this answer
    
I think you can save a couple of bytes on your stack length calculation with something like this: 1>+#<\#1_ – James Holderness 2 days ago
    
@JamesHolderness Thanks, I figured it could be shortened since it had so many hash/spaces, but I couldn't quite get it. – JayDepp 2 days ago

Jellyfish, 4 bytes

p#bi

Try it online!

Print (p), the length (#) of the binary representation (b) of the input (i).

share|improve this answer

Retina,  44  23 bytes

Requires too much memory to run for large input values. Converts to unary, then repeatedly divides by 2, counting how many times until it hits zero. Byte count assumes ISO 8859-1 encoding.

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

Try it online

share|improve this answer
    
I'm not sure this is valid. This isn't a case of "it requires more memory than you'll probably have" but "it requires more memory than Retina itself can handle". In particular, the initial conversion to unary will fail for inputs of order 2^30 and above, due to limitations in Retina's implementation. – Martin Ender Dec 28 at 9:24
    
If it is valid, it could be shortened a lot though: tio.run/nexus/retina#@6@nxaWixaWdEKdhqK1paB9jyKViGM@l9/@/saU‌​hAA – Martin Ender Dec 28 at 9:28

CJam, 5 bytes

ri2b,

Try it online!

Read input (r), convert to integer (i), get binary representation (2b), get length (,).

share|improve this answer

Octave, 19 bytes

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

Anonymous function that adds 1, computes binary logarithm and rounds up.

Try it online!

share|improve this answer

QBIC, 18 bytes

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

That's incredible Mike! But how does it work?

:        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]
share|improve this answer

Pyke, 3 bytes

b2l

Try it here!

share|improve this answer

Perl, 21 bytes

21 bytes, (ab)use the fact that $= must be an integer

say$==1+log(<>)/log 2

25 bytes, naïve implementation

say length sprintf"%b",<>

28 23 byte version without whitespaces

$-++while$_>>=1;say++$-

1while($i//=<>)>=1<<++$_;say


Usage

$ echo 128 | perl -E '$-++while$_>>=1;say++$-'
8
$ echo 128 | perl -E 'say length sprintf"%b",<>'
8
share|improve this answer
1  
Nice use of forcing the cast, but I think you can use 0| or $-= instead of $#_= for -1 byte! – Dom Hastings Dec 28 at 12:58
    
@DomHastings yes, you're right. Thanks for the tip! – Zaid Dec 28 at 13:03

APL, 6 bytes

1+⌊2⍟⍵

Omega is the right argument, which is replaced with the number in question.

Try it online!

share|improve this answer
    
As it is, this would require curly brackets to make it a function. However, you can make it a function train with ⌊1+2⍟⊢. (link) – Dennis Dec 27 at 16:41

Julia, 16 bytes

n->endof(bin(n))

Anonymous function.

share|improve this answer
    
endof is shorter than length. – Dennis Dec 27 at 16:24
    
@Dennis oh, thanks! – Easterly Irk Dec 27 at 16:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.