# 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)

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

Qmb2slQ/

Try it here!

# J, 22 bytes

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

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

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
$\+=(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