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\$ – user41805 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\$ – user41805 Dec 28 '16 at 8:23

71 Answers 71

1 2
3
0
\$\begingroup\$

68020 assembler, 2 4 bytes (I think)

BFFFO D0, D1
INC D1

The BFFFO instruction finds the position of the first set bit in parameter 1, and stores the result in parameter 2. I think it is a 2-byte instruction. Unfortunately, it is indexed from 0, not 1. Hence you need an INC on D1 afterwards.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Pushy, 11 bytes

0{${h}2/;}#

Try it online!

This works by continually doing x = x // 2 until x = 0, and counting the number of divisions taken:

0            \ Push a 0 (initial counter)
 {$     ;    \ While input > 0:
   {h}       \  Increment counter
      2/     \  Floordiv input by 2
         }#  \ Output final counter
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PowerShell v3+, 37 34 bytes

param($n)(1..32|?{!($n-shr$_)})[0]

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Taking input as param($n) is 3 bytes shorter -- param($n)(1..32|?{!($n-shr$_)})[0] \$\endgroup\$ – AdmBorkBork Jan 3 '17 at 17:12
  • \$\begingroup\$ @TimmyD so it is! Can't believe I missed that. \$\endgroup\$ – briantist Jan 3 '17 at 17:14
0
\$\begingroup\$

Groovy, 32 bytes

{Long.toBinaryString(it).size()}

This is an unnamed closure.

Try it here !

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

MATL, 2 bytes

Bn

The shortest solution in MATL seems to be just direct, by measuring the length of the binary representation (as a vector). Other options are ZlkQ, which takes the base-2 logarithm, floors it and adds 1, or YBn which converts the input to a binary string and finds the length.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

J, 4 bytes

#&#:

Explanation:

#      NB. Counts length of bit list
&      NB. Connects # and #:
#:     NB. Creates list of bits
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

K/Kona, 4 bytes

#2\:

\: gets the representation of right-hand in base left-hand - in this case, base 2 of the input. # then just counts this

k)2\:341 
1 0 1 0 1 0 1 0 1
k)#2\:341
9
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 2, 22 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Whitespace, 70 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][N
S S N
_Create_Label_LOOP][S N
S _Duplicate][N
T   S S N
_If_0_jump_to_Label_PRINT][S S S T  S N
_Push_2][T  S T S _Integer_division][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S S _Add][S N
T   _Swap_top_two][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_PRINT][S N
N
_Discard_top][T N
S T _Print_integer]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer i = STDIN as integer
Integer r = 0
Start LOOP:
  if i is 0:
    Call function PRINT_AND_EXIT
  i = i integer-divided by 2
  r = r + 1
  Go to next iteration of LOOP

function PRINT_AND_EXIT:
  Print r as integer
  Exit with error

Example run (n=16):

Command   Explanation                 Stack       HEAP     STDIN   STDOUT  STDERR

SSSN      Push 0                      [0]
SNS       Duplicate top (0)           [0,0]
SNS       Duplicate top (0)           [0,0,0]
TNTT      Read STDIN as integer       [0,0]       {0:16}   16
TTT       Retrieve                    [0,16]      {0:16}
NSSN      Create Label_LOOP           [0,16]      {0:16}
 SNS      Duplicate top (16)          [0,16,16]   {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [0,16]      {0:16}
 SSSTSN   Push 2                      [0,16,2]    {0:16}
 TSTS     Integer-divide (16/2)       [0,8]       {0:16}
 SNT      Swap top two                [8,0]       {0:16}
 SSSTN    Push 1                      [8,0,1]     {0:16}
 TSSS     Add (0+1)                   [8,1]       {0:16}
 SNT      Swap top two                [1,8]       {0:16}
 NSNN     Jump to Label_LOOP          [1,8]       {0:16}
 
 SNS      Duplicate top (8)           [1,8,8]     {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [1,8]       {0:16}
 SSSTSN   Push 2                      [1,8,2]     {0:16}
 TSTS     Integer-divide (8/2)        [1,4]       {0:16}
 SNT      Swap top two                [4,1]       {0:16}
 SSSTN    Push 1                      [4,1,1]     {0:16}
 TSSS     Add (1+1)                   [4,2]       {0:16}
 SNT      Swap top two                [2,4]       {0:16}
 NSNN     Jump to Label_LOOP          [2,4]       {0:16}
 
 SNS      Duplicate top (4)           [2,4,4]     {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [2,4]       {0:16}
 SSSTSN   Push 2                      [2,4,2]     {0:16}
 TSTS     Integer-divide (4/2)        [2,2]       {0:16}
 SNT      Swap top two                [2,2]       {0:16}
 SSSTN    Push 1                      [2,2,1]     {0:16}
 TSSS     Add (2+1)                   [2,3]       {0:16}
 SNT      Swap top two                [3,2]       {0:16}
 NSNN     Jump to Label_LOOP          [3,2]       {0:16}

 SNS      Duplicate top (2)           [3,2,2]     {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [3,2]       {0:16}
 SSSTSN   Push 2                      [3,2,2]     {0:16}
 TSTS     Integer-divide (2/2)        [3,1]       {0:16}
 SNT      Swap top two                [1,3]       {0:16}
 SSSTN    Push 1                      [1,3,1]     {0:16}
 TSSS     Add (3+1)                   [1,4]       {0:16}
 SNT      Swap top two                [4,1]       {0:16}
 NSNN     Jump to Label_LOOP          [4,1]       {0:16}

 SNS      Duplicate top (1)           [4,1,1]     {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [4,1]       {0:16}
 SSSTSN   Push 2                      [4,1,2]     {0:16}
 TSTS     Integer-divide (1/2)        [4,0]       {0:16}
 SNT      Swap top two                [0,4]       {0:16}
 SSSTN    Push 1                      [0,4,1]     {0:16}
 TSSS     Add (4+1)                   [0,5]       {0:16}
 SNT      Swap top two                [5,0]       {0:16}
 NSNN     Jump to Label_LOOP          [5,0]       {0:16}

 SNS      Duplicate top (0)           [5,0,0]     {0:16}
 NTSSN    If 0: Jump to Label_PRINT   [5,0]       {0:16}
NSSSN     Create Label_PRINT          [5,0]       {0:16}
 SNN      Discard top                 [5]         {0:16}
 TNST     Print as integer            []          {0:16}           5
                                                                            error

Program stops with an error: No exit found.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Befunge-98 (PyFunge), 19 16 bytes, Thanks to @JoKing

&#\<_$.@j3:/2\+1

Try it online!

19 bytes:

&0#;1+\2/:!3j@.$_\;

Try it online!

5 bytes shorter than Befunge-93 :)

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Brain-Flak, 48 bytes

({<({<(({}[()]))>{()(<{}({}[()])>)}{}}{})>()}{})

Try it online!

Readable version:

({< # Start a loop

  #devide by two:
  ({<(({}[()]))>{()(<{}({}[()])>)}{}}{})

>()} # Count interations
{} # pop the zero
) # push the result
| improve this answer | |
\$\endgroup\$
1 2
3

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.