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

# 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>

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

# 05AB1E, 2 bytes

bg


Try it online!

• Esoteric language won again... bg Commented Dec 27, 2016 at 16:06
• @devRicher I expect to be beaten by a 1 byte solution still, to be honest. Commented Dec 27, 2016 at 16:08
• At least this answer gets it's upvotes; it's not in the bg. Commented Dec 27, 2016 at 21:59
• bg in gaming means bad game :)
– yyny
Commented Dec 31, 2016 at 21:10
• @yoyoyonny or battleground haha. Commented Jan 2, 2017 at 17:37

# 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']

• Could you please include a hexdump of the actual 8 byte compiled x86 Assembly code? Commented Dec 27, 2016 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. :( Commented Dec 27, 2016 at 19:58
• Oh wow you changed my post to proper formatting. Thanks for correcting it! Commented Dec 27, 2016 at 20:03
• 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. Commented Dec 27, 2016 at 20:03
• Is it customary to count assembly submissions as the number of bytes of the compiled machine code rather than the assembly language source code?
– smls
Commented Jan 17, 2017 at 18:17

# Python, 14 bytes

int.bit_length


Try it online!

• It works in Python 2, too. Commented Dec 27, 2016 at 16:13
• It does indeed. Forgot Python 2‘s int was 64 bits wide, not 32 bits. Commented Dec 27, 2016 at 16:17
• Python 3's bit_length is bit_length(). Commented Dec 28, 2016 at 19:36
• @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. Commented Dec 28, 2016 at 19:43
• @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. Commented Dec 29, 2016 at 10:57

## Mathematica, 9 bytes

BitLength


Alternatively:

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


## 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.

• 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. Commented Dec 27, 2016 at 20:39

# 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

• OP guarantees n>=1, so n?...:0 is not necessary. Commented Dec 29, 2016 at 21:55
• @MadPhysicist well I do have to stop the recursion somewhere, don't I ;) Commented Dec 29, 2016 at 21:56
• OIC. Didn't read carefully, feel like a dumbass now. Neat answer either way. Commented Dec 29, 2016 at 21:59
• @MadPhysicist no worries, thank you very much :) Commented Dec 29, 2016 at 22:03
• For the non-recursive solution assuming gcc statement expressions, I reckon you might have been inclined to use the #define f(n) ({64-__builtin_clzl(n);}) approach as well. Commented Jan 1, 2017 at 13:10

# 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.

# C preprocessor macro (with gcc extensions), 26

#define f 32-__builtin_clz


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

• Oh wow, I thought about using a builtin but dropped the idea because I thought it was going to be too long... Well played. Commented Dec 28, 2016 at 8:55
• Lucky the OP specified n >= 1 :D Commented Jan 2, 2017 at 14:04

# Retina, 56 37 bytes

This solution works with all the required input values.

The biggest problem Retina faces in this challenge is the fact that its strings have a maximum length of 2^30 characters, so the usual way of dealing with numbers (unary representation) doesn't work with values greater than 2^30.

In order to solve this problem I adopted a different approach, keeping a sort of decimal representation of numbers, but where each digit is written in unary (I'll call this representation digitunary). For example the number 341 would be written as 111#1111#1# in digitunary. With this representation we can now work with numbers of up to 2^30/10 digits (~ a hundred million digits). It is less practical than standard unary for arbitrary arithmetic, but with a bit of effort we could do any kind of operations.

NOTE: digitunary in theory could use any other base (e.g. binary 110 would be 1#1## in base 2 digitunary), but since Retina has builtins to convert between decimal and unary and no direct way to deal with other bases, decimal is probably the most manageable base.

The algorithm I used is making successive integer divisions by two until we reach zero, the number of divisions we made is the number of bits needed to represent this number.

So, how do we divide by two in digitunary? Here's the Retina snippet that does it:

(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


This replacement is enough to divide a digitunary number by 2, we just need to remove possible .5s from the end if the original number was odd.

So, here's the full code, we keep dividing by two until there are still digits in the number, and put a literal n in front of the string at each iteration: the number of n at the end is the result.

.                  |
$*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  Try it online! Updated solution, 37 bytes Big refactoring with many good ideas that golfed about a third of the length, all thanks to Martin Ender! The main idea is to use _ as our unary symbol: in this way we can use regular digits in our string, as long as we convert them back to _s when it is needed: this lets us save many bytes on division and on insertion of multiple digits. Here's the 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  Try it online! • I've used a similar numeric form (but called it Unary-Coded Decimal), which is pretty handy for arithmetic with Sed. Commented May 15, 2018 at 15:02 # Ruby, 19 16 bytes ->n{"%b"%n=~/$/}


Thanks Jordan for golfing off 3 bytes

• You can save a byte with %: ->n{("%b"%n).size}. Commented Dec 28, 2016 at 6:49
• Wait, this is shorter: ->n{"%b"%n=~/$/}. Commented Dec 28, 2016 at 6:51 # Jolf, 2 bytes lB  Just convert to binary and then find the length. # Julia 0.4, 14 bytes !n=log2(2n)÷1  Try it online! • Much more interesting than the other answers. +1 Commented Dec 27, 2016 at 17:20 # 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> • The alternative a=>1+Math.log2(a)|0 is also 19 bytes. – Neil Commented Dec 27, 2016 at 18:24 • @Neil 1+...|0 screams minus tilde! a=>-~Math.log2(a) is 18 Commented Dec 28, 2016 at 12:37 • @edc65 I count 17... but yes, I was sure I was missing something, thanks for pointing it out. – Neil Commented Dec 28, 2016 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 Commented Dec 29, 2016 at 10:10 # 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.

• Nice choice of language, but it would be even cooler if you included an explanation.
– NH.
Commented Dec 31, 2016 at 13:37
• @NH Thanks. I've added an explanation. Commented Dec 31, 2016 at 18:37

Takes input from cell A1 and outputs to the cell that holds the formula

=Len(Dec2Bin(A1


or

=Int(1+Log(A1,2


or

=Int(Log(2*A1,2


# Excel, 17 Bytes

Same as above but formatted for MS Excel

=Len(Dec2Bin(A1))


or

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


or

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


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

• Alternatively: hsl or .El, in which l computes the log base 2, and hs or .E compute ceiling.
– RK.
Commented May 14, 2018 at 11:29

# Jelly, 2 bytes

BL


Converts to binary, finds length.

# C#, 6345 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.

• You have an extra space in there ...)+ 1)... -> ...)+1.... Also, I think you can return the value directly instead of printing it. Commented Dec 27, 2016 at 21:05
• 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. Commented Dec 28, 2016 at 18:35

# C#, 32 bytes

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


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

succ.floor.logBase 2


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

# 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!

• @JamesHolderness Thanks, I figured it could be shortened since it had so many hash/spaces, but I couldn't quite get it. Commented Dec 29, 2016 at 3:59
• 17 bytes
– Jo King
Commented May 16, 2018 at 3:41

## Jellyfish, 4 bytes

p#bi


Try it online!

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

## CJam, 5 bytes

ri2b,


Try it online!

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

# Octave, 19 bytes

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


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

Try it online!

• Well, I tried ;-) Commented Jan 17, 2017 at 18:14

## 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]


# Java 8, 34 27 bytes

For once, Java has some useful builtins! Now, we just need some shorter names...

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


Try it online!

Of course, you can do this without builtins (see Snowman's answer), but for a higher byte count.

# Octave, 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'))


Octave has two functions for converting decimal numbers to binary numbers.

dec2bin converts a number into a string of the characters 1 and 0 (ASCII-values 48 and 49). The length of the string will be equal to the necessary number of bits, unless specified otherwise. Since the characters 1 and 0 are non-zero, we can use nnz to find the number of elements like this: @(x)nnz(dec2bin(x)). This is 19 bytes, so it's tied with Luis Mendo's other Octave answer.

Can we do better using de2bi?

de2bi is a function that returns the binary numbers as a vector with the numbers 1 and 0 as integers, not characters. de2bi is obviously two bytes shorter than dec2bin, but we can no longer use nnz. We can use nnz if we either add 1 to all elements, or makes it into a logical vector with only true values. @(x)nnz(de2bi(x)+1) and @(x)nnz(de2bi(x)<2) are both 19 bytes. Using numel will also give us 19 bytes, @(x)numel(de2bi(x)).

rows is one byte shorter than numel, but de2bi returns a horizontal vector, so it must be transposed. @(x)rows(de2bi(x)') just so happens to be 19 bytes too.

## Pyke, 3 bytes

b2l


Try it here!

# Python 2, 28 Bytes

def f(a):print len(bin(a))-2

• lambda a:len(bin(a))-2` Commented Dec 28, 2016 at 11:03