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

2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice use of forcing the cast, but I think you can use 0| or $-= instead of $#_= for -1 byte! \$\endgroup\$ – Dom Hastings Dec 28 '16 at 12:58
  • \$\begingroup\$ @DomHastings yes, you're right. Thanks for the tip! \$\endgroup\$ – Zaid Dec 28 '16 at 13:03
2
\$\begingroup\$

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.

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

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

\$\endgroup\$
  • \$\begingroup\$ I always forget that lambda syntax is so forgiving, when Java in general is more rigid. \$\endgroup\$ – user18932 Dec 29 '16 at 19:11
  • \$\begingroup\$ I've linked your answer in mine, as I feel guilty for just cheating with builtins :) \$\endgroup\$ – FlipTack Dec 29 '16 at 19:20
  • 1
    \$\begingroup\$ @FlipTack don't feel guilty, built-ins are not cheating (unless specified otherwise). Our answers are separate solutions so they are not duplicates either. \$\endgroup\$ – user18932 Dec 29 '16 at 19:23
  • 2
    \$\begingroup\$ @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") \$\endgroup\$ – FlipTack Dec 31 '16 at 16:01
  • 2
    \$\begingroup\$ Hello from the future! Increment b (or halve v) in the loop body to save 1 byte! \$\endgroup\$ – Jakob Aug 23 '17 at 1:48
2
\$\begingroup\$

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.

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

Japt, 2 bytes

¢l

¢ converts the input into a base-2 string

l returns the length

Thanks ETHproductions for shaving off 3 bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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...) \$\endgroup\$ – ETHproductions Dec 31 '16 at 12:49
2
\$\begingroup\$

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

28 bytes

<?=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]
\$\endgroup\$
  • \$\begingroup\$ It would appear you no longer need the log(x,2) or floor ... +1 explanations \$\endgroup\$ – Taylor Scott Dec 29 '16 at 12:21
  • 1
    \$\begingroup\$ OK, seems like a display bug (see my edit) \$\endgroup\$ – Crypto Dec 30 '16 at 6:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Titus Feb 7 '17 at 19:18
1
\$\begingroup\$

APL, 6 bytes

1+⌊2⍟⍵

Omega is the right argument, which is replaced with the number in question.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Dennis Dec 27 '16 at 16:41
1
\$\begingroup\$

Julia, 16 bytes

n->endof(bin(n))

Anonymous function.

\$\endgroup\$
  • \$\begingroup\$ endof is shorter than length. \$\endgroup\$ – Dennis Dec 27 '16 at 16:24
1
\$\begingroup\$

Pyth - 3 bytes

Alternative 3 byte answer. Takes floor(log2(n))+1

hsl

Test Suite.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ "ZSS" is not an explanation of ~ to anyone who didn't already know. \$\endgroup\$ – WGroleau Dec 28 '16 at 5:32
  • \$\begingroup\$ Sorry, Added a bit of detail. \$\endgroup\$ – ATaco Dec 28 '16 at 5:36
1
\$\begingroup\$

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

Python 2, 28 Bytes

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Matlab, 21 Bytes

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

Yay for anonymous functions!

Example usage:

c(6)

ans = 

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

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!

\$\endgroup\$
1
\$\begingroup\$

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
   1+        NB. Add 1

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ It's just #@#: \$\endgroup\$ – Aky Jan 1 '17 at 20:29
1
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Taylor Scott Jul 22 '17 at 18:00
  • \$\begingroup\$ @TaylorScott Thanks, I'll consider doing that in the future. \$\endgroup\$ – ericw31415 Jul 23 '17 at 1:01
1
\$\begingroup\$

Javascript, 23 bytes

x=>x.toString(2).length

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

\$\endgroup\$
1
\$\begingroup\$

TI-Basic, 8 bytes

1+int(logBASE(Ans,2
\$\endgroup\$
1
\$\begingroup\$

Perl, 19 bytes

$_=0|1+(log)/log 2

The score includes 1 byte for the -p switch the program requires.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Some mad golfing skills here... just when I thought there was no more room for improvement in my answer :) \$\endgroup\$ – Zaid Jan 1 '17 at 15:25
1
\$\begingroup\$

Ruby, 19 bytes

->i{i.to_s(2).size}
\$\endgroup\$
1
\$\begingroup\$

SmileBASIC, 20 bytes

INPUT N?LEN(BIN$(N))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You could save a few bytes by just using import. \$\endgroup\$ – Zacharý Jul 19 '17 at 21:58
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – briantist Feb 5 '17 at 5:44
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 39 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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;
} 
\$\endgroup\$
  • \$\begingroup\$ You can shave off some bytes by removing "n!=0" since n evaluates as true if nonzero. \$\endgroup\$ – NoSeatbelts Feb 22 '17 at 3:22
  • \$\begingroup\$ 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. \$\endgroup\$ – NoSeatbelts Feb 22 '17 at 3:29
1
\$\begingroup\$

Dodos, 60 bytes

	' S ' g
g
	S dab
	g S ' dab f
f
	f ' '
	S dab
'
	dip
S
	dot

Try it online!

(S computes the sum, S ' dab f divides by 2)

\$\endgroup\$

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.