In how many bits do I fit

Question

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 code-golf. Shortest code in bytes wins

Answer 1

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>

Answer 2

05AB1E, 2 bytes

bg

Try it online!

Answer 3

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

Answer 4

Python, 14 bytes

int.bit_length

Try it online!

Answer 5

Mathematica, 9 bytes

BitLength

Alternatively:

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

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

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!

Answer 11

Ruby, 19 16 bytes

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

Thanks Jordan for golfing off 3 bytes

Answer 12

Jolf, 2 bytes

lB

Just convert to binary and then find the length.

Answer 13

Julia 0.4, 14 bytes

!n=log2(2n)÷1

Try it online!

Answer 14

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>

Answer 15

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.

Answer 16

Google Sheets, 15 Bytes

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

Answer 17

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

Answer 18

Jelly, 2 bytes

BL

Converts to binary, finds length.

Answer 19

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.

Answer 20

C#, 32 bytes

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

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

Answer 21

Haskell, 20 bytes

succ.floor.logBase 2

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

Answer 22

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!

Answer 23

Jellyfish, 4 bytes

p#bi

Try it online!

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

Answer 24

CJam, 5 bytes

ri2b,

Try it online!

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

Answer 25

Octave, 19 bytes

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

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

Try it online!

Answer 26

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]

Answer 27

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.

Answer 28

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.

Answer 29

Pyke, 3 bytes

b2l

Try it here!

Answer 30

Python 2, 28 Bytes

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