[Question]
  [
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](https://codegolf.meta.stackexchange.com/questions/5139/leaderboard-snippet))
```
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](http://oeis.org/A083652).
  
[Answer]
# Pyth, 6 bytes
```
.Oml.B
```
[Try it online here](http://pyth.herokuapp.com/?code=.Oml.B&test_suite=1&test_suite_input=1%0A2%0A3%0A4%0A5%0A6%0A7&debug=0).
```
.Oml.BdUQ              Filling in implict vars
.O                     Average of list
 m   UQ                Map over [0..input)
  l                    Length of
   .B                  Binary string representation of int
    d                  Lambda var
```
[Answer]
# Jelly, 6 bytes
```
R’BFL÷
```
[Try it online!](http://jelly.tryitonline.net/#code=UuKAmUJGTMO3&input=&args=Nw)
```
R’BFL÷  Main monadic chain. Argument: n
R       yield [1, 2, ..., n]
 ’      decrement; yield [0, 1, ..., n-1]
  B     convert to binary; yield [[0], [1], [1,0], [1,1], ...]
   F    flatten list; yield [0, 1, 1, 0, 1, 1, ...]
    L   length of list
     ÷  divide [by n]
```
[Answer]
# Octave, 29 bytes
```
@(n)1+sum(fix(log2(1:n-1)))/n
```
**Explanation**
```
              log2(1:n-1)       % log2 of numbers in range [1..n-1]
                                % why no 0? because log2(0) = -Inf  :/
          fix(           )      % floor (more or less, for positive numbers)
      sum(                )     % sum... wait, didn't we miss a +1 somewhere?
                                % and what about that missing 0?
                           /n   % divide by n for the mean
    1+                          % and add (1/n) for each of the n bit lengths 
                                % (including 0!)
```
Sample run on [ideone](http://ideone.com/3i9BsB).
[Answer]
# Python 3, 43 bytes
```
def f(n):x=len(bin(n))-2;return(2-2**x)/n+x
```
Makes use of the formula on the [OEIS page](http://oeis.org/A083652). Surprisingly, a named function is somehow cheaper here because of the assignment to `x`.
Alternative approach for 46 bytes:
```
lambda n:-~sum(map(int.bit_length,range(n)))/n
```
Unfortunately, the `-~` is necessary since `(0).bit_length()` is `0`, but even then it'd be a byte too long.
[Answer]
# Julia, 27 bytes
```
n->endof(prod(bin,0:n-1))/n
```
[Try it online!](http://julia.tryitonline.net/#code=Zj1uLT5lbmRvZihwcm9kKGJpbiwwOm4tMSkpL24KCmZvciBuIGluIDE6NwogICAgcHJpbnRsbihuLCAiID0-ICIsIGYobikpCmVuZA&input=)
### How it works
Since `*` is string concatenation in Julia, `prod` can be used to concatenate an array of strings. It optionally takes a function as first argument that it maps over the second one before taking the actual "product", so `prod(bin,0:n-1)` is the string of the binary representation of all integers in the desired range. Taking the length with `endof` and dividing by **n** yields the mean.
[Answer]
## Julia, 28 bytes
```
n->mean(ceil(log2([2;2:n])))
```
Since `bin` doesn't automatically map over arrays, we're using `ceil(log2(n))` to get the number of bits in `n-1`. This works out nicely because Julia's `a:b` notation is inclusive on both ends, so `2:n` is a range from 2 to `n`, but we're really calculating the number of bits for numbers in the range `1:n-1`. Unfortunately though, we need to tack on an extra `2` to account for 0.
[Try it online!](http://julia.tryitonline.net/#code=Zj1uLT5tZWFuKGNlaWwobG9nMihbMjsyOm5dKSkpCnByaW50bG4oZigxMjM0NTYpKQ&input=)
[Answer]
# MATL, 9 bytes
```
q:ZlksG/Q
```
[**Try it Online!**](http://matl.tryitonline.net/#code=cTpabGtzRy9R&input=Ng)
[Modified version with all test cases](http://matl.tryitonline.net/#code=YGl0cTpabGtzdy9RRFRd&input=MQoyCjMKNAo1CjYKNw)
**Explanation**
```
    % Implicitly grab input (N)
q:  % Create array from 1:N-1
Zl  % Compute log2 for each element of the array
k   % Round down to the nearest integer
s   % Sum all values in the array
G   % Explicitly grab input again
/   % Divide by the input
Q   % Add 1 to account for 0 in [0, ... N - 1]
    % Implicitly display the result
```
[Answer]
# MATL, 9 bytes
```
:qBYszQG/
```
[Try it online!](http://matl.tryitonline.net/#code=OnFCWXN6UUcv&input=Nw)
**Explanation**
```
:qBYszQG/
:               % take vector [1..n]
 q              % decrement by 1 to get [0..n-1]
  B             % convert from decimal to binary
   Ys           % cumulative sum (fills in 0's after first 1)
     z          % number of nonzero elements
      Q         % increment by 1 to account for zero
       G        % paste original input (n)
        /       % divide for the mean
```
[Answer]
# Jelly, 8 bytes
Not shorter, but interesting algorithm, and my first Jelly submission:
```
Rl2Ċ»1S÷
R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
```
[Answer]
# Jelly, 10 bytes
```
BL©2*2_÷+®
```
From Sp3000's suggestion.
[Try it here.](http://jelly.tryitonline.net/#code=QkzCqTIqMl_DtyvCrg&input=&args=Nw)
# Jelly, 11 bytes
```
æḟ2’Ḥ÷_BL$N
```
Not very short but I need some tips.
[Try it here.](http://jelly.tryitonline.net/#code=w6bhuJ8y4oCZ4bikw7dfQkwkTg&input=&args=Nw)
Using the same formula as in [Sp3000's answer](https://codegolf.stackexchange.com/a/80594/25180). (It's not very hard to get it yourself, by differentiating geometric progression.)
[Answer]
# Java, ~~135~~ ~~95~~ 90 bytes
```
float a(int n){int i=0,t=0;for(;i<n;)t+=Integer.toString(i++,2).length();return t/(n+0f);}
```
[Answer]
# Python 3, 46 Bytes
```
lambda x:sum(len(bin(i))-2for i in range(x))/x
```
Call it like
```
f = lambda x: sum(len(bin(i))-2for i in range(x))/x
print(f(6))
# 2.0
```
*I had to revert the map revision because it failed for input of 5*
[Answer]
# J, ~~21~~ ~~17~~ 15 bytes
From 17 bytes to 15 bytes thanks to @Dennis.
```
+/@:%~#@#:"0@i.
```
Can anyone help me golf this?...
### Ungolfed version
```
range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
```
[Answer]
## 05AB1E, ~~9~~ 7 bytes
**Code:**
```
L<bJg¹/
```
**Explanation:**
```
L<         # range from 0..input-1
  b        # convert numbers to binary
   J       # join list of binary numbers into a string
    g      # get length of string (number of bits)
     ¹/    # divide by input
```
[Try it online](http://05ab1e.tryitonline.net/#code=TDxiSmfCuS8&input=Nw)
Edit: saved 2 bytes thanks to @Adnan
[Answer]
## Clojure, ~~71~~ ~~64~~ 63 bytes
It looks like ratios are ok according to [Which number formats are acceptable in output?](http://meta.codegolf.stackexchange.com/questions/9263/which-number-formats-are-acceptable-in-output)
`(fn[n](/(inc(apply +(map #(.bitLength(bigint %))(range n))))n))`
* n=1 => 1
* n=7 => 15/7
ungolfed (and slightly rewritten for ease of explanation)
```
(fn [n]
 (->
  (->>
   (range n)                      ;;Get numbers from 0 to N
   (map #(.bitLength (bigint %))) ;;Cast numbers to BigInt so bitLength can be used
   (apply +)                      ;;Sum the results of the mapping
   (inc))                         ;;Increment by 1 since bitLength of 0 is 0
  (/ n)))                         ;;Divide the sum by N
```
### old answer that used (float):
`(fn[n](float(/(inc(apply +(map #(..(bigint %)bitLength)(range n))))n)))`
output is like:
* n=1 => 1.0
* n=7 => 2.142857
[Answer]
# C#, 87 bytes
```
double f(int n){return Enumerable.Range(0,n).Average(i=>Convert.ToString(i,2).Length);}
```
I wrote a C# answer because I didn't see one. This is my first post to one of these, so please let me know if I'm doing anything wrong.
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `r`, 5 bytes
```
ʁbfL/
```
[Try it Online!](https://lyxal.pythonanywhere.com?flags=r&code=%CA%81bfL%2F&inputs=6&header=&footer=)
```
ʁ     # 0...a
 b    # Turn each into base 2
  f   # Flatten
   L  # Get the length
    / # Divide by the input
```
[Answer]
## JavaScript (ES7), ~~38~~ 32 bytes
```
n=>(l=-~Math.log2(n))-(2**l-2)/n
```
Using @sp3000's formula (previous version was a recursive solution). ES6 version for 34 bytes:
```
n=>(l=-~Math.log2(n))-((1<<l)-2)/n
```
Explanation of formula: Consider the case of N=55. If we write the binary numbers (vertically to save space), we get:
```
                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010
```
The size of this rectangle is *nl* so the average is just *l* but we need to exclude the blanks. Each row of blanks is twice as long as the previous so the total is 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2l - 2.
[Answer]
# [Perl 6](http://perl6.org), ~~34~~ 32 bytes
```
{$_ R/[+] map *.base(2).chars,^$_}
```
```
{$_ R/[+] map {(.msb||0)+1},^$_}
```
### Explanation:
```
{ 
  $_  # the input
  R/  # divides ( ｢$a R/ $b｣ is the same as ｢$b / $a｣ )
  [+] # the sum of:
  map
    {
      (
       .msb # the most significant digit (0 based)
       || 0 # which returns Nil for ｢0.msb｣ so use 0 instead
            # should be ｢(.msb//0)｣ but the highlighting gets it wrong
            # it still works because it has the same end result 
      ) 
      + 1   # make it 1 based
    },
    ^$_ # ｢0 ..^ $_｣ all the numbers up to the input, excluding the input
}
```
### Test:
```
use v6.c;
# give it a name
my &mean-bits = {$_ R/[+] map {(.msb||0)+1},^$_}
for 1..7 {
  say .&mean-bits
}
say '';
say mean-bits(7).perl;
say mean-bits(7).base-repeating(10);
```
```
1
1
1.333333
1.5
1.8
2
2.142857
<15/7>
(2. 142857)
```
[Answer]
# [Dyalog APL](http://goo.gl/9KrKoM), 14 bytes
```
(+/1⌈(⌈2⍟⍳))÷⊢
range ← ⍳
log   ← ⍟
log2  ← 2 log range
ceil  ← ⌈
bits  ← ceil log2
max   ← ⌈
fix0  ← 1 max bits
sum   ← +/
total ← sum fix0
self  ← ⊢
div   ← ÷
mean  ← sum div self
```
[Answer]
## [Minkolang 0.15](https://github.com/elendiastarman/Minkolang), 23 bytes
```
n$z1z[i1+2l$M$Y+]kz$:N.
```
[Try it here!](http://play.starmaninnovations.com/minkolang/?code=n%24z1z%5Bi1%2B2l%24M%24Y%2B%5Dz%24%3AN%2E&input=6)
### Explanation
```
n$z                       Take number from input and store it in register (n)
   1                      Push 1 onto the stack
    z[                    For loop that repeats n times
      i1+                 Loop counter + 1
         2l$M             log_2
             $Y           Ceiling
               +          Add top two elements of stack
                ]         Close for loop
                 z$:      Float divide by n
                    N.    Output as number and stop.
```
Pretty straightfoward implementation.
[Answer]
# JavaScript ES5, 55 bytes
```
n=>eval(`for(o=0,p=n;n--;o+=n.toString(2).length/p);o`)
```
## Explanation
```
n =>   // anonymous function w/ arg `n`
  for( // loop
      o=0,  // initalize bit counter to zero
      p=n   // copy the input
    ;n-- // will decrease input every iteration, will decrease until it's zero
    ;o+=    // add to the bitcounter
        n.toString(2)  // the binary representation of the current itearations's
                     .length // length
        /p   // divided by input copy (to avergage)
   );o       // return o variable  
```
[Answer]
## [Hoon](https://github.com/urbit/urbit), 71 bytes
```
|=
r/@
(^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
```
...I'm pretty sure this is actually the first time I've used Hoon's floating point cores. It's actually an implementation written in Hoon that jets out to SoftFloat, since the only data types in Hoon are atoms and cells.
Create a function that takes an atom, `r`. Create a list from [0..(r - 1)], map over the list taking the binary logarithm of the number, then fold over that list with `++add`. Convert both the output of the fold and `r` to `@rq` (quad-precision floating point numbers) with `++sun:rq`, and then divide one by the other.
The oddest thing in this snippet is the `:.^rq` at the end. `a:b` in Hoon means "evaluate a in the context of b". `++rq` is the core that contains the entire quad-precision implementation, like a library. So running `(sun 5):rq` is the same thing as doing `(sun:rq 5)`.
Luckily, cores in Hoon are like nesting dolls; when you evaluate the arm `++rq` to get the core, it adds the entire stdlib to it as well, so you get to keep roll and turn and gulf and all that fun stuff instead of being stuck with *only* the arms defined in `++rq`. Unluckily, rq redefines `++add` to be floating-point add instead, along with not having `r` in its context. `.` (the entire current context) does, however.
When evaluating an expression in a context, the compiler looks for the limb depth-first. In our case of `a:[. rq]` it would look in the entire current context for `a` before moving on to looking in `rq`. So `add` will look up the function that works on atoms instead of floating-point numbers...but so will `div`. Hoon also has a feature where using `^name` will ignore the first found reference, and look for the second.
From there, it's simply using the syntatic sugar of `a^b` being equal to `[a b]` to evaluate our snippet with both our current context and the quad-precision float library, ignoring the atomic div in favor of `++div:rq`.
```
> %.  7
  |=
  r/@
  (^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
.~~~2.1428571428571428571428571428571428
```
[Answer]
## Actually, 7 bytes:
```
;r♂├Σl/
```
[Try it online!](http://actually.tryitonline.net/#code=O3LimYLilJzOo2wv&input=NQ)
Explanation:
```
;r♂├Σl/
;        duplicate input
 r       push range(0, n) ([0, n-1])
  ♂├     map binary representation
    Σ    sum (concatenate strings)
     l/  divide length of string (total # of bits) by n
```
If it weren't for a bug that I just discovered, this solution would work for 6 bytes:
```
r♂├♂læ
```
`æ` is the builtin mean command.
[Answer]
# Vitsy, 26 bytes
This is a first attempt, I'll golf this down more and add an explanation later.
```
0vVV1HV1-\[2L_1+v+v]v1+V/N
```
[Try it online!](http://vitsy.tryitonline.net/#code=MHZWVjFIVjEtXFsyTF8xK3Yrdl12MStWL04&input=&args=Nw)
[Answer]
## PowerShell v2+, 64 bytes
```
param($n)0..($n-1)|%{$o+=[convert]::ToString($_,2).Length};$o/$n
```
Very straightforward implementation of the spec. Loops from `0` to `$n-1` with `|%{...}`. Each iteration, we `[convert]` our input number `$_` to a string base`2` and take its `length`. We accumulate that in `$o`. After the loops, we simply divide `$o/$n`, leaving that on the pipeline, and output is implicit.
As long as this is, it's actually shorter than the formula that Sp & others are using, since `[math]::Ceiling()` and `[math]::Log()` are ridiculously wordy. Base conversion in PowerShell is yucky.
[Answer]
## Perl 5.10, 54 bytes
```
for(1..<>){$u+=length sprintf"%b",$_;$n++}$u/=$n;say$u
```
Pretty much straightforward. `sprintf"%b"` is a neat way to output a number in binary in Perl without using additional libraries.
[Try it online!](https://ideone.com/P8XRsE)
[Answer]
# CJam, ~~13~~ ~~12~~ 11 bytes
*One byte saved thanks to @Sp3000, and another thanks to @jimmy23013*
```
rd_,2fbs,\/
```
[**Try it online!**](http://cjam.tryitonline.net/#code=cmRfLDJmYnMsXC8&input=Nw)
### Explanation
Straightforward. Applies the definition.
```
rd      e# read input and convert to double 
_       e# duplicate 
,       e# range from 0 to input minus 1
2fb     e# convert each element of the array to binary 
s       e# convert to string. This flattens the array
,       e# length of array 
\       e# swap 
/       e# divide 
```
[Answer]
# Jolf, 10 bytes
```
/uΜr0xdlBH
```
[Try it here!](http://conorobrien-foxx.github.io/Jolf/#code=L3XOnHIweGRsQkg&input=NQ)
## Explanation
```
/uΜr0xdlBH
  Μr0x      map range 0..x
      dlBH  over lengths of binary elements
/u          divide sum of this
            by implicit input (x)
```
[Answer]
# Swift, 72 bytes
```
func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
```
]