Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 2 days ago
16  
@orlp It actually is floor(log2(num))+1 – Kritixi Lithos 2 days ago
2  
@KritixiLithos Right. – orlp 2 days ago
2  
Nevermind, just realized that the distinct is important when num is a power of two. – Brian J 2 days ago
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 2 days ago

49 Answers 49

up vote 19 down vote accepted

05AB1E, 2 bytes

bg

Try it online!

share|improve this answer
9  
Esoteric language won again... bg – devRicher 2 days ago
15  
@devRicher I expect to be beaten by a 1 byte solution still, to be honest. – carusocomputing 2 days ago
4  
At least this answer gets it's upvotes; it's not in the bg. – SeeOneRhino 2 days 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 2 days ago
1  
Should it be n>>>1 to support n > 0x7FFFFFFF? – Arnauld 2 days ago
    
@Arnauld Hmm, didn't know >> failed on n that high. Thanks. – ETHproductions 2 days ago
    
Nice, my first attempt was f=(a,b=1)=>a>1?f(a>>1,++b):b – Bassdrop Cumberwubwubwub yesterday

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 2 days ago
    
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 2 days ago
    
Oh wow you changed my post to proper formatting. Thanks for correcting it! – z0rberg's 2 days ago
    
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 2 days ago
    
Oh that's nice! Well, then it's down to four! – z0rberg's 2 days ago

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 2 days ago
1  
It does indeed. Forgot Python 2‘s int was 64 bits wide, not 32 bits. – Dennis 2 days ago
    
Python 3's bit_length is bit_length(). – dfernan yesterday
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 yesterday
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 21 hours 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 10 hours ago
    
@MadPhysicist well I do have to stop the recursion somewhere, don't I ;) – Quentin 10 hours ago
    
OIC. Didn't read carefully, feel like a dumbass now. Neat answer either way. – Mad Physicist 10 hours ago
    
@MadPhysicist no worries, thank you very much :) – Quentin 10 hours 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

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 2 days ago
4  
@Neil 1+...|0 screams minus tilde! a=>-~Math.log2(a) is 18 – edc65 yesterday
    
@edc65 I count 17... but yes, I was sure I was missing something, thanks for pointing it out. – Neil yesterday
    
@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 22 hours ago

Jolf, 2 bytes

lB

Just convert to binary and then find the length.

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 2 days ago

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 yesterday

Ruby, 19 16 bytes

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

Thanks Jordan for golfing off 3 bytes

share|improve this answer
    
+1 for brilliance – DepressedDaniel 2 days ago
    
You can save a byte with %: ->n{("%b"%n).size}. – Jordan 2 days ago
3  
Wait, this is shorter: ->n{"%b"%n=~/$/}. – Jordan 2 days 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

bash / Unix tools, 16 bytes

dc<<<2o$1n|wc -c
share|improve this answer

Jelly, 2 bytes

BL

Converts to binary, finds length.

share|improve this answer

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

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 2 days ago

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 2 days ago
    
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 2 days ago
    
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 yesterday

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 yesterday
    
@JamesHolderness Thanks, I figured it could be shortened since it had so many hash/spaces, but I couldn't quite get it. – JayDepp yesterday

Haskell, 20 bytes

succ.floor.logBase 2

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

share|improve this answer

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 yesterday
    
If it is valid, it could be shortened a lot though: tio.run/nexus/retina#@6@nxaWixaWdEKdhqK1paB9jyKViGM@l9/@/saU‌​hAA – Martin Ender yesterday

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 yesterday
    
@DomHastings yes, you're right. Thanks for the tip! – Zaid yesterday

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 2 days ago

Julia, 16 bytes

n->endof(bin(n))

Anonymous function.

share|improve this answer
    
endof is shorter than length. – Dennis 2 days ago
    
@Dennis oh, thanks! – Easterly Irk 2 days ago

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.