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\$
  • 6
    \$\begingroup\$ Nice name, very punny. \$\endgroup\$ – Rɪᴋᴇʀ May 25 '16 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 '16 at 2:48
  • 4
    \$\begingroup\$ Not enough puns, you need a bit more for this to be perfect. \$\endgroup\$ – Qwerp-Derp May 25 '16 at 7:12
  • 1
    \$\begingroup\$ I'm assuming that by "each number" you mean "each integer"? \$\endgroup\$ – Cyoce May 28 '16 at 19:45
  • \$\begingroup\$ @Cyoce yes, thank you for pointing that out - I've edited to clarify. \$\endgroup\$ – trichoplax May 28 '16 at 22:41

42 Answers 42

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\$
  • \$\begingroup\$ Good idea to add cumulatively... You can save 1 byte using "@F" instead of $F[0]! \$\endgroup\$ – Dom Hastings Feb 7 '18 at 8:32

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.