30
\$\begingroup\$

Given an integer N >= 1, output the mean number of bits in an integer from 0 to N - 1

Specification

  • The output can be calculated as the sum of the number of bits in the binary representation of each integer from 0 to N-1, divided by N.
  • The binary representation of an integer has no leading zeroes in this context, with the exception of zero, which is represented as 0 in binary.
  • The output should be accurate to at least 7 significant figures.

Example

N = 6

0: 0   : 1 bit
1: 1   : 1 bit
2: 10  : 2 bits
3: 11  : 2 bits
4: 100 : 3 bits
5: 101 : 3 bits

Mean number of bits = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Test cases

Input => output

1 => 1
2 => 1
3 => 1.3333333
4 => 1.5
5 => 1.8
6 => 2
7 => 2.1428571

Leaderboard Snippet

(from here)

var QUESTION_ID=80586,OVERRIDE_USER=20283;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:400px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Note that the sum (before dividing to find the mean) is a sequence on OEIS.

\$\endgroup\$
5
  • 6
    \$\begingroup\$ Nice name, very punny. \$\endgroup\$
    – Riker
    May 25, 2016 at 2:04
  • 3
    \$\begingroup\$ For anyone who doesn't know, I'm more likely to upvote solutions with an explanation \$\endgroup\$
    – trichoplax
    May 25, 2016 at 2:48
  • 4
    \$\begingroup\$ Not enough puns, you need a bit more for this to be perfect. \$\endgroup\$
    – clismique
    May 25, 2016 at 7:12
  • 1
    \$\begingroup\$ I'm assuming that by "each number" you mean "each integer"? \$\endgroup\$
    – Cyoce
    May 28, 2016 at 19:45
  • \$\begingroup\$ @Cyoce yes, thank you for pointing that out - I've edited to clarify. \$\endgroup\$
    – trichoplax
    May 28, 2016 at 22:41

43 Answers 43

1
2
1
\$\begingroup\$

J, 15 bytes

%~[:+/#@#:"0@i.

This is a monadic verb, used as follows:

   f =: %~[:+/#@#:"0@i.
   f 7
2.14286

Try it here!

Explanation

I implemented the challenge spec pretty literally. There are other approaches, but all turned out to be longer.

%~[:+/#@#:"0@i.  Input is y
             i.  Range from 0 to y-1.
          "0@    For each number in this range:
      #@           Compute the length of
        #:         its base-2 representation.
  [:+/           Take the sum of the lengths, and
%~               divide by y.
\$\endgroup\$
1
\$\begingroup\$

AWK, 59 bytes

{for(s=1;++n<$0;s+=int(log(n*2)/log(2)));printf"%.8g",s/$0}

Since AWK only does base-10 logs, I had to convert to base-2 and I chose to multiply the argument by 2 rather than add 1 to the result. It's the same byte-count, but I like it. :)

Try it online!

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

K4, 16 bytes

Solution:

(1+#,/2\:'!x)%x:

Example:

(1+#,/2\:'!x)%x:5
1.8
(1+#,/2\:'!x)%x:6
2f
(1+#,/2\:'!x)%x:7
2.142857

Explanation:

Convert each number to binary, sum up the bits, add 1 for 0, divide by input.

(1+#,/2\:'!x)%x: / the solution
              x: / store input as x
(           )%   / divide left by right
          !x     / range 0..x-1
      2\:'       / convert each (') to bits (2\:)
    ,/           / flatten result
   #             / count length of list
 1+              / add one (as 0 contains 0 bits!)

Extra:

Precision is determined by the P system setting. Default is 7, max is 17

\P 7
(1+#,/2\:'!x)%x:7
2.142857

\P 12
(1+#,/2\:'!x)%x:7
2.14285714286

\P 17
(1+#,/2\:'!x)%x:7
2.1428571428571428
\$\endgroup\$
1
\$\begingroup\$

Japt, 6 bytes

o¤xÊ/U

Try it


Explanation

           :Implicit input of integer U
o          :Range [0,U)
 ¤         :Convert each to a base-2 string
   Ê       :Get length of each
  x        :Reduce by addition
    /U     :Divide by U
           :Implicit output of result
\$\endgroup\$
1
\$\begingroup\$

Pyt, 8 bytes

⁻řļ⌊⁺Á1µ

Explanation:

                Implicit input (N)
⁻               Decrement by 1 (N-1)
 ř              Push [1,2,...,N-1]
  ļ             element-wise log base 2 of [1,2,...,N-1]
   ⌊⁺           element-wise floor and increment
     Á          Push contents of array onto stack
      1         Push 1
       µ        Get mean of stack
                Implicit output

Try it online!

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

R, 51 bytes

Takes input from stdin. Uses the OEIS formula and then divides by n.

(2+ceiling(log2(n<-scan()))*n-2^ceiling(log2(n)))/n

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 44 34 bytes

Now starring the formula used by @Sp3000

->x{(2.0-2**b=x.to_s(2).size)/x+b}

Old version:

->x{r=0.0;x.times{|i|r+=i.to_s(2).size};r/x}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 28 bytes

(Tr@⌈Log2@Range@#⌉+1)/#&

or

Tr@⌈Log2@Range@#⌉/#+1/#&

In either case, it's an unnamed function which takes N as an input and returns an exact (rational) result for the mean.

\$\endgroup\$
0
\$\begingroup\$

Pyke, 8 bytes

Qmb2slQ/

Try it here!

\$\endgroup\$
0
\$\begingroup\$

J, 22 bytes

[:(+/%#)[:([:##:)"0 i. Usage:

    bin =: [:(+/%#)[:([:##:)"0 i.
    bin 7
2.14286
\$\endgroup\$
0
\$\begingroup\$

Haskell, 50 bytes

r x|x<1=0|1<2=1+r(x/2)
f n=(sum(r<$>[0..n-1])+1)/n
\$\endgroup\$
0
\$\begingroup\$

PHP, 48 bytes

a direct port of Sp3000´s answer

<?=(2-2**$x=strlen(decbin($n=$argv[1]))-2)/$n+$x
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 44 43 + 2 (-pa) = 45 bytes

-1 thanks to @DomHastings

$\+=(length sprintf'%b',$_)/"@F"while$_--}{

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Good idea to add cumulatively... You can save 1 byte using "@F" instead of $F[0]! \$\endgroup\$ Feb 7, 2018 at 8:32
1
2

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.