Bit berarti: tantangan rata-rata

30

Dengan bilangan bulat N> = 1, hasilkan jumlah rata-rata bit dalam bilangan bulat dari 0 hingga N - 1

Spesifikasi

  • Output dapat dihitung sebagai jumlah dari jumlah bit dalam representasi biner dari setiap integer dari 0 hingga N-1, dibagi dengan N.
  • Representasi biner dari integer tidak memiliki nol terkemuka dalam konteks ini, dengan pengecualian nol, yang direpresentasikan sebagai 0 dalam biner.
  • Outputnya harus akurat setidaknya 7 angka signifikan.

Contoh

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

Jumlah rata-rata bit = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Uji kasus

Input => output

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

Cuplikan Papan

(dari sini )

Tampilkan cuplikan kode

Perhatikan bahwa jumlah (sebelum membagi untuk menemukan rata-rata) adalah urutan pada OEIS .

code-golf math binary bitwise statistics trichoplax
sumber
6
Nama yang bagus, sangat lemah .
Rɪᴋᴇʀ
3
Bagi siapa pun yang tidak tahu, saya lebih cenderung memilih solusi dengan penjelasan
trichoplax
4
Tidak cukup permainan kata-kata, Anda perlu sedikit lebih banyak untuk ini menjadi sempurna.
clismique
1
Saya mengasumsikan bahwa dengan "setiap angka" yang Anda maksud "setiap bilangan bulat "?
Cyoce
@ Ayo ya, terima kasih telah menunjukkan itu - Saya telah mengedit untuk menjelaskan.
trichoplax

Jawaban:

13

Pyth, 6 byte

.Oml.B

Cobalah online di sini .

.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
Maltysen
sumber
Bergabung di tempat pertama tetapi Anda tidak muncul di papan peringkat - Saya telah melakukan sedikit perubahan pada tajuk untuk memperbaikinya.
trichoplax
9

Jelly, 6 byte

R’BFL÷

Cobalah online!

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]
Biarawati Bocor
sumber
7

Oktaf, 29 byte

@(n)1+sum(fix(log2(1:n-1)))/n

Penjelasan

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

Sampel dijalankan pada ideone .

gelas kimia
sumber
6

Python 3, 43 byte

def f(n):x=len(bin(n))-2;return(2-2**x)/n+x

Manfaatkan rumus ini pada halaman OEIS . Anehnya, fungsi bernama entah bagaimana lebih murah di sini karena tugas untuk x.

Pendekatan alternatif untuk 46 byte:

lambda n:-~sum(map(int.bit_length,range(n)))/n

Sayangnya, -~itu perlu karena (0).bit_length()itu 0, tetapi bahkan kemudian itu akan menjadi byte yang terlalu lama.

Sp3000
sumber
6

Julia, 27 byte

n->endof(prod(bin,0:n-1))/n

Cobalah online!

Bagaimana itu bekerja

Karena *ini adalah rangkaian string dalam Julia, proddapat digunakan untuk menggabungkan serangkaian string. Secara opsional mengambil fungsi sebagai argumen pertama yang dipetakan di atas yang kedua sebelum mengambil "produk" yang sebenarnya, demikian prod(bin,0:n-1)juga string representasi biner dari semua bilangan bulat dalam rentang yang diinginkan. Mengambil panjang dengan endofdan membaginya dengan n menghasilkan rata-rata.

Dennis
sumber
5

Julia, 28 byte

n->mean(ceil(log2([2;2:n])))

Karena bintidak secara otomatis memetakan di atas array, kami menggunakan ceil(log2(n))untuk mendapatkan jumlah bit n-1. Ini berfungsi dengan baik karena a:bnotasi Julia inklusif pada kedua ujungnya, sehingga 2:nrentang dari 2 hingga n, tetapi kami benar-benar menghitung jumlah bit untuk angka dalam rentang 1:n-1. Sayangnya, kita perlu menambah ekstra2 akun untuk 0.

Cobalah online!

Sp3000
sumber
5

MATL, 9 byte

q:ZlksG/Q

Cobalah secara Online!

Versi modifikasi dengan semua kasus uji

Penjelasan

    % 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
Suever
sumber
Jepret!! (pengisi)
David
@ David Sebenarnya, milikmu benar. Menggandakan input di awal tidak bekerja untuk nilai-nilai lain ... Anda perlu G/Qdi akhir.
Gelas
5

MATL, 9 byte

:qBYszQG/

Cobalah online!

Penjelasan

: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
gelas kimia
sumber
5

Jelly, 8 byte

Tidak lebih pendek, tetapi algoritma yang menarik, dan pengiriman Jelly pertama saya:

Rl2Ċ»1S÷

R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
Adm
sumber
4

Jelly, 10 byte

BL©2*2_÷+®

Dari saran Sp3000.

Coba di sini.

Jelly, 11 byte

æḟ2’Ḥ÷_BL$N

Tidak terlalu pendek tapi saya butuh beberapa tips.

Coba di sini.

Menggunakan rumus yang sama seperti pada jawaban Sp3000 . (Tidak terlalu sulit untuk mendapatkannya sendiri, dengan membedakan perkembangan geometrik.)

jimmy23013
sumber
Lihatlah jawaban Jelly saya untuk referensi Anda.
Bocor Biarawati
@ LeakyNun Menggunakan pendekatan yang berbeda, yang menurut saya tidak akan pernah lebih pendek dari milik Anda. Tapi _BL$Nsepertinya cukup lama ...
jimmy23013
Jadi pada dasarnya, kode Anda adalah "lantai ke kekuatan terdekat 2, minus 1, ganda, dibagi dengan input, minus panjang input biner, negatif"?
Leaky Nun
@ LeakyNun Ya ..
jimmy23013
3
Hanya sedikit lebih baik:BL©2*2_÷+®
Sp3000
4

Java, 135 95 90 byte

float a(int n){int i=0,t=0;for(;i<n;)t+=Integer.toString(i++,2).length();return t/(n+0f);}
Shaun Wild
sumber
Saya pikir Anda dapat menyingkirkan antarmuka dan hanya membuat suatu fungsi atau lambda. Anda juga dapat mengembalikan nilai alih-alih mencetaknya ke stdout
Frozn
Oke, saya akan menerapkan kembali dengan aturan itu.
Shaun Wild
Saya pikir itu harus diizinkan. Karena OP tidak menentukan apa pun, saya pikir aturan I / O standar berlaku.
Frozn
Ya suatu fungsi baik-baik saja - Anda tidak perlu program lengkap. Perhatikan bahwa papan mengambil skor di baris pertama, jadi skor Anda saat ini menunjukkan 135 bukannya 95.
trichoplax
@trichoplax Masih tempat terakhir. Saya menyalahkan Jawa secara pribadi ...
Shaun Wild
3

Python 3, 46 Bytes

lambda x:sum(len(bin(i))-2for i in range(x))/x

Sebut saja seperti

f = lambda x: sum(len(bin(i))-2for i in range(x))/x
print(f(6))
# 2.0

Saya harus mengembalikan revisi peta karena gagal untuk input 5

Keatinge
sumber
3

05AB1E, 9 7 byte

Kode:

L<bJg¹/

Penjelasan:

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

Cobalah online

Sunting: disimpan 2 byte berkat @Adnan

Emigna
sumber
@ Adnan: Terima kasih! Lupa tentang J.
Emigna
3

C #, 87 byte

double f(int n){return Enumerable.Range(0,n).Average(i=>Convert.ToString(i,2).Length);}

Saya menulis jawaban C # karena saya tidak melihatnya. Ini adalah posting pertama saya ke salah satu dari ini, jadi tolong beri tahu saya jika saya melakukan sesuatu yang salah.

raive
sumber
Selamat datang di Programming Puzzles and Code Golf. Ini adalah jawaban pertama yang bagus, +1. Bisakah Anda mengubah doubleke floatuntuk menghemat satu byte, atau apakah Anda membutuhkan ketelitian?
wizzwizz4
2
@ wizzwizz4 Terima kasih! Saya memiliki pemikiran yang sama, tetapi Average () mengembalikan dua kali lipat. Jika saya mengubah tipe pengembalian saya menjadi float maka saya harus secara eksplisit melemparkan ganda dan mendapatkan 7 byte itu.
raive
2

JavaScript (ES7), 38 32 byte

n=>(l=-~Math.log2(n))-(2**l-2)/n

Menggunakan rumus @ sp3000 (versi sebelumnya adalah solusi rekursif). Versi ES6 untuk 34 byte:

n=>(l=-~Math.log2(n))-((1<<l)-2)/n

Penjelasan rumus: Pertimbangkan kasus N = 55. Jika kita menulis angka biner (secara vertikal untuk menghemat ruang), kita mendapatkan:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

Ukuran persegi panjang ini adalah nl jadi rata-rata hanya l tetapi kita perlu mengecualikan yang kosong. Setiap baris kosong dua kali lebih panjang dari sebelumnya sehingga totalnya adalah 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 l - 2.

Neil
sumber
2

J, 21 17 15 byte

Dari 17 byte hingga 15 byte, terima kasih kepada @Dennis.

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

Adakah yang bisa membantu saya bermain golf ini? ...

Versi tidak disatukan

range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
Biarawati Bocor
sumber
Saya mencoba pendekatan alternatif, oleh stringifying daftar angka biner, dan keluar dengan 25 bytes: %~>:@#@([:":10#.[:#:i.)-]. Solusi Anda terlihat agak optimal.
Conor O'Brien
2

Perl 6 ,  34  32 byte

{$_ R/[+] map *.base(2).chars,^$_}

{$_ R/[+] map {(.msb||0)+1},^$_}

Penjelasan:

{ 
  $_  # 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
}

Uji:

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)
Brad Gilbert b2gills
sumber
2

Dyalog APL , 14 byte

(+/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
Adm
sumber
2

Clojure, 71 64 63 byte

Sepertinya rasio ok menurut format angka mana yang dapat diterima dalam output?

(fn[n](/(inc(apply +(map #(.bitLength(bigint %))(range n))))n))

  • n = 1 => 1
  • n = 7 => 15/7

ungolfed (dan sedikit ditulis ulang untuk memudahkan penjelasan)

(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

jawaban lama yang digunakan (float):

(fn[n](float(/(inc(apply +(map #(..(bigint %)bitLength)(range n))))n)))

output seperti:

  • n = 1 => 1.0
  • n = 7 => 2.142857
menandai
sumber
Pertanyaan apakah fraksi atau rasio dapat diterima belum diajukan sebelumnya. Untuk tantangan ini saya akan menerima konsensus apa pun yang dicapai tentang apa yang seharusnya menjadi default .
trichoplax
1

Minkolang 0,15 , 23 byte

n$z1z[i1+2l$M$Y+]kz$:N.

Coba di sini!

Penjelasan

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.

Implementasi yang cukup jujur.

El'endia Starman
sumber
1

JavaScript ES5, 55 byte

n=>eval(`for(o=0,p=n;n--;o+=n.toString(2).length/p);o`)

Penjelasan

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
Downgoat
sumber
1

Hoon , 71 byte

|=
r/@
(^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq

... Aku cukup yakin ini sebenarnya pertama kalinya aku menggunakan core floating point Hoon. Sebenarnya ini adalah implementasi yang ditulis dalam Hoon yang diluncurkan ke SoftFloat, karena satu-satunya tipe data di Hoon adalah atom dan sel.

Buat fungsi yang mengambil atom r,. Buat daftar dari [0 .. (r - 1)], petakan daftar itu dengan mengambil logaritma biner dari angka tersebut, lalu lipatlah daftar itu dengan ++add. Konversikan output dari lipatan dan rke @rq(angka floating point presisi quad) dengan++sun:rq , dan kemudian bagi satu dengan yang lainnya.

Hal paling aneh dalam cuplikan ini adalah :.^rqdi bagian akhir. a:bdalam Hoon berarti "mengevaluasi a dalam konteks b". ++rqadalah inti yang berisi seluruh implementasi quad-precision, seperti perpustakaan. Jadi berlari (sun 5):rqadalah hal yang sama dengan melakukan (sun:rq 5).

Untungnya, inti di Hoon seperti boneka bersarang; ketika Anda mengevaluasi lengan ++rquntuk mendapatkan inti, itu menambahkan seluruh stdlib juga, sehingga Anda bisa terus berguling-guling dan teluk serta semua hal yang menyenangkan alih-alih terjebak hanya dengan lengan yang ditentukan ++rq. Sayangnya, rq mengubah ++addmenjadi floating-point sebagai gantinya, bersama dengan tidak memiliki rdalam konteksnya..(seluruh konteks saat ini), bagaimanapun.

Saat mengevaluasi ekspresi dalam konteks, kompiler mencari kedalaman ekstremitas-pertama. Dalam kasus kami a:[. rq]akan melihat dalam seluruh konteks saat ini untuk asebelum pindah ke melihat rq. Jadi addakan mencari fungsi yang bekerja pada atom, bukan angka floating-point ... tapi begitu juga div. Hoon juga memiliki fitur di mana menggunakan ^nameakan mengabaikan referensi yang ditemukan pertama, dan mencari yang kedua.

Dari sana, itu hanya menggunakan gula sintaksis a^byang setara dengan [a b]untuk mengevaluasi potongan kita dengan konteks kita saat ini dan perpustakaan float presisi-quad, mengabaikan div atom yang mendukung ++div:rq.

> %.  7
  |=
  r/@
  (^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
.~~~2.1428571428571428571428571428571428
Pengaturan rendering
sumber
1

Sebenarnya, 7 byte:

;r♂├Σl/

Cobalah online!

Penjelasan:

;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

Jika bukan karena bug yang baru saja saya temukan, solusi ini akan bekerja selama 6 byte:

r♂├♂læ

æ adalah perintah mean builtin.

Mego
sumber
Bukankah ini 10 byte? Saya memeriksa di bytesizematters.com.
m654
1
@ m654 Sebenarnya tidak menggunakan UTF-8, ia menggunakan CP437 (atau sesuatu seperti itu).
Alex A.
@AlexA. Oh, tidak tahu itu.
m654
1
@ m654 Bytesizematters menggunakan penyandian yang dibuat sepenuhnya yang tidak (dan tidak bisa ) ada dalam praktek. Untuk UTF-8, gunakan mothereff.in/byte-counter .
Dennis
@ Dennis Terima kasih atas informasinya, saya akan mengingatnya.
m654
1

Vitsy, 26 byte

Ini adalah upaya pertama, saya akan menurunkan ini lagi dan menambahkan penjelasan nanti.

0vVV1HV1-\[2L_1+v+v]v1+V/N

Cobalah online!

Addison Crump
sumber
1

PowerShell v2 +, 64 byte

param($n)0..($n-1)|%{$o+=[convert]::ToString($_,2).Length};$o/$n

Implementasi spec yang sangat mudah. Loop dari 0ke $n-1dengan |%{...}. Setiap iterasi, [convert]kami memasukkan nomor input kami $_ke basis string 2dan mengambilnya length. Kami mengakumulasikannya di $o. Setelah loop, kami hanya membagi $o/$n, meninggalkan yang ada di dalam pipa, dan output tersirat.

Selama ini, sebenarnya lebih pendek dari formula yang digunakan Sp & lain-lain, karena [math]::Ceiling()dan [math]::Log()sangat bertele-tele. Konversi basis di PowerShell adalah yucky.

AdmBorkBork
sumber
1

Perl 5.10, 54 byte

for(1..<>){$u+=length sprintf"%b",$_;$n++}$u/=$n;say$u

Cukup mudah. sprintf"%b"adalah cara yang rapi untuk menghasilkan angka dalam biner di Perl tanpa menggunakan pustaka tambahan.

Cobalah online!

Paul Picard
sumber
1

CJam, 13 12 11 byte

Satu byte disimpan berkat @ Sp3000, dan satu byte lagi berkat @ jimmy23013

rd_,2fbs,\/

Cobalah online!

Penjelasan

Mudah. Terapkan definisi.

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
Luis Mendo
sumber
1

Jolf, 10 byte

/uΜr0xdlBH

Coba di sini!

Penjelasan

/uΜr0xdlBH
  Μr0x      map range 0..x
      dlBH  over lengths of binary elements
/u          divide sum of this
            by implicit input (x)
Conor O'Brien
sumber
1

Cepat, 72 byte

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
John McDowall
sumber
2
Anda tidak perlu memanggil fungsi tersebut, membiarkannya sebagai fungsi yang didefinisikan tidak apa-apa. Posting pertama yang bagus.
Rɪᴋᴇʀ
1

J, 15 byte

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

Ini adalah kata kerja monadik, digunakan sebagai berikut:

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

Coba di sini!

Penjelasan

Saya mengimplementasikan spec tantangan secara harfiah. Ada pendekatan lain, tetapi semuanya ternyata lebih lama.

%~[:+/#@#:"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.
Zgarb
sumber