# In how many bits do I fit

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

• This is the ceiling of the base-2 logarithm.
– orlp
Dec 27, 2016 at 16:51
• @orlp It actually is floor(log2(num))+1 Dec 27, 2016 at 16:52
• @KritixiLithos Right.
– orlp
Dec 27, 2016 at 18:46
• Nevermind, just realized that the distinct is important when num is a power of two. Dec 27, 2016 at 20:22
• 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) Dec 28, 2016 at 8:23

# 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

• 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. Dec 28, 2016 at 9:24
• If it is valid, it could be shortened a lot though: tio.run/nexus/retina#@6@nxaWixaWdEKdhqK1paB9jyKViGM@l9/@/saUhAA Dec 28, 2016 at 9:28

# 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

• Nice use of forcing the cast, but I think you can use 0| or $-= instead of $#_= for -1 byte! Dec 28, 2016 at 12:58
• @DomHastings yes, you're right. Thanks for the tip!
– Zaid
Dec 28, 2016 at 13:03

## JavaScript (ES6), 17 bytes

f=
a=>-~Math.log2(a)
<input type=number min=0 oninput=o.textContent=f(this.value)><div>Bits: <span id=o>

Saved 2 bytes thanks to @edc65.

# Java 8, 43 41

v->{int b=0;for(;v>0;++b,v/=2);return b;}


Counts the bits the old fashioned way and returns the count. Lambda fits into a LongFunction<Integer>.

• I always forget that lambda syntax is so forgiving, when Java in general is more rigid.
– user18932
Dec 29, 2016 at 19:11
• I've linked your answer in mine, as I feel guilty for just cheating with builtins :) Dec 29, 2016 at 19:20
• @FlipTack don't feel guilty, built-ins are not cheating (unless specified otherwise). Our answers are separate solutions so they are not duplicates either.
– user18932
Dec 29, 2016 at 19:23
• @ericw31415 lambda expressions, functional literals, etc. are all allowed. only if the post specifies "full program" must you include the boilerplate (and the default is "programs or functions") Dec 31, 2016 at 16:01
• Hello from the future! Increment b (or halve v) in the loop body to save 1 byte! Aug 23, 2017 at 1:48

# Actually, 2 bytes

├l


Try it online!

Explanation:

├l
├   binary representation (without leading zeroes)
l  length


Since Actually uses arbitrary-width integers, this will work for any input, so long as there is enough memory and time.

### Japt, 2 bytes

¢l


¢ converts the input into a base-2 string

l returns the length

Thanks ETHproductions for shaving off 3 bytes.

• Awesome, thanks! ¢ is a shortcut for Us2) (see the Unicode Shortcuts section of the docs), which allows you to just do ¢l for 2 bytes. (I should add an implicit U at the beginning of every program...) Dec 31, 2016 at 12:49

# PHP, 21 bytes

<?=-~log($argv[1],2);  • log(x,2) Computes log2(x) • ~ is the binary negation operator that also cast to int • - take opposite ### 28 bytes <?=strlen(decbin($argv[1]));

• decbin convert to binary
• strlen takes length

<?=floor(log($argv[1],2))+1;  • log(x,2) compute log2(x) • floor ... +1 takes floor plus 1 ### 32 bytes (Thanks Titus) for(;2**++$i<=$argv[1];);echo$i;

• 2**$n compute 2^n ie. pow(2,n) until superior to$argv[1]
• It would appear you no longer need the log(x,2) or floor ... +1 explanations Dec 29, 2016 at 12:21
• OK, seems like a display bug (see my edit) Dec 30, 2016 at 6:50
• Your looping solution fails for powers of 2 (1,2,4,8 etc.); fix with <= instead of <. And for(;2**++$i<=$argv[1];);echo$i; is two bytes shorter. Feb 7, 2017 at 19:18 # APL, 6 bytes 1+⌊2⍟⍵ Omega is the right argument, which is replaced with the number in question. Try it online! • 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) Dec 27, 2016 at 16:41 # Julia, 16 bytes n->endof(bin(n))  Anonymous function. • endof is shorter than length. Dec 27, 2016 at 16:24 # Pyth - 3 bytes Alternative 3 byte answer. Takes floor(log2(n))+1 hsl  # RProgN, 4 Bytes. ~2BL  ## Explained ~2BL # ~ # Zero Space Segment, The rest of this code is interpreted as if it were a bunch of characters separated by spaces. 2B # Convert implicit input to Base 2 L # Get the length of that, and implicitly output.  Try it online! • "ZSS" is not an explanation of ~ to anyone who didn't already know. Dec 28, 2016 at 5:32 • Sorry, Added a bit of detail. Dec 28, 2016 at 5:36 ## awk, 32 bytes Iterate 2's exponent and see when it's greater than given value. Return the value in exit: {for(;++i<=32;)if(2^i>$0)exit i}


Run it:

$echo 4294967295| awk '{for(;++i<=32;)if(2^i>$0)exit i}'
$echo$?
32


# C, 27 bytes

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


Inspired by the answer by Quentin. Uses an unsigned literal to avoid overflow when using 32-bit integers. Might be able to cut the unsigned part if int is 64-bit, but it's more interesting this way.

# C, 47 39 bytes

int L(uint32_t X){return X?1+L(X/2):0;}


Not using a library function. The algorithm counts the number of bits needed by shifting right (or the equivalent divide by 2) until 0.

# Matlab, 21 Bytes

c=@(x)nnz(dec2bin(x))


Yay for anonymous functions!

Example usage:

c(6)

ans =

3


# Julia, 15 bytes

n->ndigits(n,2)


This is an anonymous function that wraps Julia's built-in ndigits function that counts the number of digits of the input in the given base. Here we're giving it a base of 2.

Try it online!

# J, 11 bytes

2&(1+<.@^.)


This is a monadic verb that accepts input on the right.

2&(    @^.)  NB. Base 2 logarithm of the input
<.      NB. Floor


Could likely be improved using # (tally) and #: (binary representation) but I haven't figured that part out yet.

Try it online!

• It's just #@#:
– Aky
Jan 1, 2017 at 20:29

# ForceLang, 88 bytes

Noncompeting, requires the latest interpreter release, which postdates the question. (The ln implementation used previously was too inaccurate with large values)

set i math.ln io.readnum()
set j math.ln 2
set k math.floor i.mult j.pow -1
io.write k+1


## VBScript, 45 bytes

Sub l(n)
WScript.Echo Log(n)/Log(2)+1
End Sub


See result by adding l(whatever the number is) to the end of the file. Run with cscript.exe if you want the result in a command window.

• You may consider adding a <!-- language-all: lang-vbs --> flag to this and all of your future VBS answers, so that they may have syntax highlighting Jul 22, 2017 at 18:00
• @TaylorScott Thanks, I'll consider doing that in the future. Jul 23, 2017 at 1:01

### Javascript, 23 bytes

x=>x.toString(2).length


f=x=>x.toString(2).length
document.write(f(341)) // 9

# TI-Basic, 8 bytes

1+int(logBASE(Ans,2


# Perl, 19 bytes

$_=0|1+(log)/log 2  The score includes 1 byte for the -p switch the program requires. Try it online! • Some mad golfing skills here... just when I thought there was no more room for improvement in my answer :) – Zaid Jan 1, 2017 at 15:25 ## Ruby, 19 bytes ->i{i.to_s(2).size}  # SmileBASIC, 20 bytes INPUT N?LEN(BIN$(N))


# Python 2, 39 bytes

lambda x:__import__('math').frexp(x)[1]


Not even kind of the shortest, but it showcases a neat function that could be useful elsewhere!

frexp(n) represents n as n = m * 2**e with 0.5 <= abs(m) < 1 and then returns the tuple (m, e) as output. For positive integers, e is exactly the number of bits required to represent the number.

• You could save a few bytes by just using import. Jul 19, 2017 at 21:58

## Powershell, 66 48 bytes

-18 bytes thanks to @briantist

function l {[math]::floor([math]::log($args[0])/[math]::log(2))+1}  ($m=[math])::floor(m::log($args[0])/m::log(2))+1  Doing anything in Powershell is complicated, but it's better than Batch! In just Batch, this challenge isn't even possible (no decimal numbers=no logarithms). • Our respective PowerShell solutions use different methods, but yours can still be shortened by getting rid of function l { } because it's completely superfluous for the challenges here; $args[0] counts for args passed to the script itself. You could also do ($m=[math])::log($args[0]) and then replace the other 2 instances of [math] with $m, like $m::floor. Feb 5, 2017 at 5:44

## Lithp, 30 bytes

 #N::((length(to-string N 2)))


Pretty simple. Convert the number to binary (to-string N 2) and return the length of the string.

Try it online!

## Alternate entry (no binary builtin), 38 bytes

 #N::((if(!= 0 N)((+ 1(x(>> N 1))))0))


Try it online!

Recursively shifts right by 1 each time the function is called, until we get to 0. This is an unsigned shift, so can support the full range of 0x0 - 0xFFFFFFFF. The Lithp >> operator is equivalent to Javascript's >>> operator.

# Common Lisp, 39 bytes

(defun f(i)(length(format nil "~B" i)))


Try it online!

# Python 2, 22 bytes

lambda n:len(bin(n))-2


Try it online!

# C, 39 36 bytes

f(n,*p){*p=0;while(n){n/=2;(*p)++;}}


Ungolfed version:

 void f(long int n, int *p)
{
*p=0;
while(n!=0)
{
n/=2;
(*p)++;
}
}


The main() function that accepts number from stdin, would look like this:

   int main()
{
int b=0
long int num;
scanf("%ld",&num);
f(num,&b);
printf("%d\n",b);
return 0;
}



## Alternative:

f(long n){i=0;while(n!=0){n/=2;i++;}return i;}


Ungolfed version:

int f(int n)
{
int i=0;

while(n!=0)
{
n/=2;
i++;

}
return i;
}


• You can shave off some bytes by removing "n!=0" since n evaluates as true if nonzero. Feb 22, 2017 at 3:22
• This is also invalid, won't compile. This, however, will. p;f(n){p=0;while(n)n/=2,++p;} works with only 29 bytes. p;f(n){for(p=0;n;n/=2)++p;} works with only 27. Feb 22, 2017 at 3:29