Mean bits: an average challenge

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


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

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

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!

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


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


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!

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!

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}


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.

Pyke, 8 bytes

Qmb2slQ/


Try it here!

J, 22 bytes

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

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


r x|x<1=0|1<2=1+r(x/2)
f n=(sum(r<$>[0..n-1])+1)/n  PHP, 48 bytes a direct port of Sp3000´s answer <?=(2-2**$x=strlen(decbin($n=$argv[1]))-2)/$n+$x

Perl 5, 44 43 + 2 (-pa) = 45 bytes
$\+=(length sprintf'%b',$_)/"@F"while$_--}{  Try it online! • Good idea to add cumulatively... You can save 1 byte using "@F" instead of $F[0]! – Dom Hastings Feb 7 '18 at 8:32