52
\$\begingroup\$

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

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

71 Answers 71

30
\$\begingroup\$

05AB1E, 2 bytes

bg

Try it online!

\$\endgroup\$
  • 16
    \$\begingroup\$ Esoteric language won again... bg \$\endgroup\$ – devRicher Dec 27 '16 at 16:06
  • 20
    \$\begingroup\$ @devRicher I expect to be beaten by a 1 byte solution still, to be honest. \$\endgroup\$ – Magic Octopus Urn Dec 27 '16 at 16:08
  • 9
    \$\begingroup\$ At least this answer gets it's upvotes; it's not in the bg. \$\endgroup\$ – NoOneIsHere Dec 27 '16 at 21:59
  • 3
    \$\begingroup\$ bg in gaming means bad game :) \$\endgroup\$ – YoYoYonnY Dec 31 '16 at 21:10
  • 1
    \$\begingroup\$ @yoyoyonny or battleground haha. \$\endgroup\$ – Magic Octopus Urn Jan 2 '17 at 17:37
35
\$\begingroup\$

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>

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

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

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

Python, 14 bytes

int.bit_length

Try it online!

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

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.
\$\endgroup\$
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Johan Dec 27 '16 at 20:39
15
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ OP guarantees n>=1, so n?...:0 is not necessary. \$\endgroup\$ – Mad Physicist Dec 29 '16 at 21:55
  • 1
    \$\begingroup\$ @MadPhysicist well I do have to stop the recursion somewhere, don't I ;) \$\endgroup\$ – Quentin Dec 29 '16 at 21:56
  • \$\begingroup\$ OIC. Didn't read carefully, feel like a dumbass now. Neat answer either way. \$\endgroup\$ – Mad Physicist Dec 29 '16 at 21:59
  • \$\begingroup\$ @MadPhysicist no worries, thank you very much :) \$\endgroup\$ – Quentin Dec 29 '16 at 22:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Moreaki Jan 1 '17 at 13:10
14
\$\begingroup\$

Mathematica, 9 bytes

BitLength

Alternatively:

Floor@Log2@#+1&
#~IntegerLength~2&
\$\endgroup\$
14
\$\begingroup\$

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.

\$\endgroup\$
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oh wow, I thought about using a builtin but dropped the idea because I thought it was going to be too long... Well played. \$\endgroup\$ – Quentin Dec 28 '16 at 8:55
  • \$\begingroup\$ Lucky the OP specified n >= 1 :D \$\endgroup\$ – Matthieu M. Jan 2 '17 at 14:04
12
+300
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ I've used a similar numeric form (but called it Unary-Coded Decimal), which is pretty handy for arithmetic with Sed. \$\endgroup\$ – Toby Speight May 15 '18 at 15:02
11
\$\begingroup\$

Ruby, 19 16 bytes

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

Thanks Jordan for golfing off 3 bytes

\$\endgroup\$
  • \$\begingroup\$ You can save a byte with %: ->n{("%b"%n).size}. \$\endgroup\$ – Jordan Dec 28 '16 at 6:49
  • 3
    \$\begingroup\$ Wait, this is shorter: ->n{"%b"%n=~/$/}. \$\endgroup\$ – Jordan Dec 28 '16 at 6:51
10
\$\begingroup\$

Jolf, 2 bytes

lB

Just convert to binary and then find the length.

\$\endgroup\$
10
\$\begingroup\$

Julia 0.4, 14 bytes

!n=log2(2n)÷1

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Much more interesting than the other answers. +1 \$\endgroup\$ – Magic Octopus Urn Dec 27 '16 at 17:20
10
\$\begingroup\$

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>

\$\endgroup\$
  • 2
    \$\begingroup\$ The alternative a=>1+Math.log2(a)|0 is also 19 bytes. \$\endgroup\$ – Neil Dec 27 '16 at 18:24
  • 5
    \$\begingroup\$ @Neil 1+...|0 screams minus tilde! a=>-~Math.log2(a) is 18 \$\endgroup\$ – edc65 Dec 28 '16 at 12:37
  • \$\begingroup\$ @edc65 I count 17... but yes, I was sure I was missing something, thanks for pointing it out. \$\endgroup\$ – Neil Dec 28 '16 at 17:10
  • \$\begingroup\$ @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 \$\endgroup\$ – Bassdrop Cumberwubwubwub Dec 29 '16 at 10:10
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice choice of language, but it would be even cooler if you included an explanation. \$\endgroup\$ – NH. Dec 31 '16 at 13:37
  • \$\begingroup\$ @NH Thanks. I've added an explanation. \$\endgroup\$ – Mitchell Spector Dec 31 '16 at 18:37
9
\$\begingroup\$

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))
\$\endgroup\$
8
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Alternatively: hsl or .El, in which l computes the log base 2, and hs or .E compute ceiling. \$\endgroup\$ – RK. May 14 '18 at 11:29
8
\$\begingroup\$

Jelly, 2 bytes

BL

Converts to binary, finds length.

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have an extra space in there ...)+ 1)... -> ...)+1.... Also, I think you can return the value directly instead of printing it. \$\endgroup\$ – Loovjo Dec 27 '16 at 21:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Grax32 Dec 28 '16 at 18:35
6
\$\begingroup\$

C#, 32 bytes

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

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

\$\endgroup\$
4
\$\begingroup\$

Haskell, 20 bytes

succ.floor.logBase 2

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

\$\endgroup\$
4
\$\begingroup\$

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!

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

Jellyfish, 4 bytes

p#bi

Try it online!

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

\$\endgroup\$
3
\$\begingroup\$

CJam, 5 bytes

ri2b,

Try it online!

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

\$\endgroup\$
3
\$\begingroup\$

Octave, 19 bytes

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

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Pyke, 3 bytes

b2l

Try it here!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Dec 28 '16 at 9:24
  • \$\begingroup\$ If it is valid, it could be shortened a lot though: tio.run/nexus/retina#@6@nxaWixaWdEKdhqK1paB9jyKViGM@l9/@/saUhAA \$\endgroup\$ – Martin Ender Dec 28 '16 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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