Mittlere Bits: eine durchschnittliche Herausforderung

30

Bei einer Ganzzahl N> = 1 wird die mittlere Anzahl von Bits in einer Ganzzahl von 0 bis N - 1 ausgegeben

Spezifikation

  • Die Ausgabe kann als Summe der Anzahl der Bits in der Binärdarstellung jeder Ganzzahl von 0 bis N-1 geteilt durch N berechnet werden.
  • Die Binärdarstellung einer Ganzzahl hat in diesem Zusammenhang keine führenden Nullen, mit Ausnahme von Null, die in Binärdarstellung als 0 dargestellt wird.
  • Die Ausgabe sollte auf mindestens 7 signifikante Stellen genau sein.

Beispiel

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

Mittlere Anzahl von Bits = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Testfälle

Eingabe => Ausgabe

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

Leaderboard-Snippet

(von hier )

Code-Snippet anzeigen

Beachten Sie, dass die Summe (vor dem Teilen, um den Mittelwert zu ermitteln) eine Sequenz in OEIS ist .

code-golf math binary bitwise statistics Trichoplax
quelle
6
Netter Name, sehr punny .
25.
3
Für alle, die es nicht wissen, bin ich eher bereit, Lösungen mit einer Erklärung zu unterstützen
Trichoplax
4
Nicht genug Wortspiele, du brauchst ein bisschen mehr, um perfekt zu sein.
Clismique
1
Ich gehe davon aus, dass Sie mit "jeder Zahl" "jede ganze Zahl" meinen ?
Cyoce
@Cyoce ja, danke, dass du darauf hingewiesen hast - ich habe es bearbeitet, um es zu klären.
Trichoplax

Antworten:

13

Pyth, 6 Bytes

.Oml.B

Probieren Sie es hier online aus .

.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
quelle
Gemeinsamer erster Platz, aber Sie sind nicht in der Bestenliste aufgetaucht. Ich habe den Header geringfügig überarbeitet, um ihn zu korrigieren.
Trichoplax
9

Gelee, 6 Bytes

R’BFL÷

Probieren Sie es 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]
Undichte Nonne
quelle
7

Oktave, 29 Bytes

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

Erläuterung

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

Probelauf auf ideone .

Becherglas
quelle
6

Python 3, 43 Bytes

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

Verwendet die Formel auf der OEIS-Seite . Überraschenderweise ist eine benannte Funktion aufgrund der Zuordnung zu hier irgendwie günstiger x.

Alternativer Ansatz für 46 Bytes:

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

Leider ist das -~notwendig, da (0).bit_length()ist 0, aber selbst dann wäre es ein Byte zu lang.

Sp3000
quelle
6

Julia, 27 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Da *es sich bei Julia um eine Zeichenfolgenverkettung handelt, prodkann diese verwendet werden, um ein Array von Zeichenfolgen zu verketten. Optional wird als erstes Argument eine Funktion verwendet, die der zweiten zugeordnet wird, bevor das tatsächliche "Produkt" abgerufen prod(bin,0:n-1)wird. Dies ist auch die Zeichenfolge der binären Darstellung aller Ganzzahlen im gewünschten Bereich. Nimmt man die Länge mit endofund dividiert durch n, so ergibt sich der Mittelwert.

Dennis
quelle
5

Julia, 28 Bytes

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

Da bindie Zuordnung nicht automatisch über Arrays erfolgt, verwenden wir ceil(log2(n)), um die Anzahl der eingegebenen Bits zu ermitteln n-1. Das funktioniert gut, weil Julias a:bNotation an beiden Enden inklusive ist, also 2:nein Bereich von 2 bis n, aber wir berechnen wirklich die Anzahl der Bits für Zahlen im Bereich 1:n-1. Leider müssen wir aber noch einen draufstecken 2, um 0 zu machen.

Probieren Sie es online!

Sp3000
quelle
5

MATL, 9 Bytes

q:ZlksG/Q

Probieren Sie es online!

Geänderte Version mit allen Testfällen

Erläuterung

    % 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
quelle
Schnapp !! (Füller)
David
@ David Eigentlich war dein Recht. Das Duplizieren der Eingabe am Anfang funktioniert nicht für andere Werte ... Sie benötigen die G/Qam Ende.
Becher
5

MATL, 9 Bytes

:qBYszQG/

Probieren Sie es online!

Erläuterung

: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
Becherglas
quelle
5

Gelee, 8 Bytes

Nicht kürzer, aber interessanter Algorithmus und meine erste Jelly-Einreichung:

Rl2Ċ»1S÷

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

Gelee, 10 Bytes

BL©2*2_÷+®

Aus dem Vorschlag von Sp3000.

Probieren Sie es hier aus.

Jelly, 11 Bytes

æḟ2’Ḥ÷_BL$N

Nicht sehr kurz, aber ich brauche ein paar Tipps.

Probieren Sie es hier aus.

Verwenden Sie die gleiche Formel wie in der Antwort von Sp3000 . (Es ist nicht sehr schwer, es selbst zu bekommen, indem man den geometrischen Verlauf unterscheidet.)

jimmy23013
quelle
Schauen Sie sich meine Gelee-Antwort als Referenz an.
Undichte Nonne
@LeakyNun Es verwendet einen anderen Ansatz, von dem ich nicht glaube, dass er jemals kürzer sein würde als deiner. Aber das _BL$Nschien ziemlich lang ...
Jimmy23013
Ihr Code lautet also im Grunde "Floor to Nearest Potence von 2, minus 1, double, dividiert durch Eingabe, minus binäre Länge der Eingabe, negativ"?
Undichte Nonne
@LeakyNun Ja ..
Jimmy23013
3
Nur unwesentlich besser:BL©2*2_÷+®
Sp3000
4

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);}
Shaun Wild
quelle
Ich denke, Sie können die Schnittstelle loswerden und einfach eine Funktion oder Lambda erstellen. Sie können den Wert auch zurückgeben, anstatt ihn an stdout
Frozn,
Okay, ich werde es mit diesen Regeln umsetzen.
Shaun Wild
Ich denke, das sollte erlaubt sein. Da das OP nichts spezifiziert hat, gelten meiner Meinung nach Standard-E / A-Regeln .
Frozn
Ja, eine Funktion ist in Ordnung - Sie benötigen kein vollständiges Programm. Beachten Sie, dass die Bestenliste die Punktzahl in der ersten Zeile aufnimmt, sodass Ihre Punktzahl derzeit 135 statt 95
ergibt
@trichoplax Noch letzter Platz. Ich beschuldige Java persönlich ...
Shaun Wild
3

Python 3, 46 Bytes

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

Nenne es so

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

Ich musste die Kartenrevision zurücksetzen, da die Eingabe von 5 fehlgeschlagen ist

Keatinge
quelle
3

05AB1E, 9 7 Bytes

Code:

L<bJg¹/

Erläuterung:

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

Probieren Sie es online aus

Bearbeiten: 2 Bytes dank @Adnan gespeichert

Emigna
quelle
@Adnan: Danke!
Vergessen
3

C # 87 Bytes

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

Ich habe eine C # -Antwort geschrieben, weil ich keine gesehen habe. Dies ist mein erster Beitrag zu einem dieser Artikel. Bitte lassen Sie mich wissen, wenn ich etwas falsch mache.

raive
quelle
Willkommen bei Programming Puzzles und Code Golf. Dies ist eine großartige erste Antwort, +1. Könnten Sie ändern double, floatum ein Byte zu speichern, oder benötigen Sie die Genauigkeit?
wizzwizz4
2
@ wizzwizz4 Danke! Ich hatte den gleichen Gedanken, aber Average () gibt ein Double zurück. Wenn ich meinen Rückgabetyp in float ändere, muss ich das Double explizit umwandeln und 7 Bytes dazu gewinnen.
Raive
2

JavaScript (ES7), 38 32 Byte

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

Verwendung der Formel von @ sp3000 (vorherige Version war eine rekursive Lösung). ES6-Version für 34 Bytes:

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

Erklärung der Formel: Betrachten Sie den Fall von N = 55. Wenn wir die Binärzahlen schreiben (vertikal, um Platz zu sparen), erhalten wir:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

Die Größe dieses Rechtecks ​​ist nl , der Durchschnitt ist also nur l, aber wir müssen die Leerzeichen ausschließen. Jede Leerzeichenreihe ist doppelt so lang wie die vorherige, sodass die Summe 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 l - 2 beträgt .

Neil
quelle
2

J, 21 17 15 Bytes

17 bis 15 Bytes dank @Dennis.

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

Kann mir jemand beim Golfen helfen? ...

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
Undichte Nonne
quelle
Ich habe versucht , einen alternativen Ansatz, um die Liste der binären Ziffern stringifying und kam mit 25 Bytes: %~>:@#@([:":10#.[:#:i.)-]. Ihre Lösung sieht eher optimal aus.
Conor O'Brien
2

Perl 6 ,  34  32 Bytes

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

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

Erläuterung:

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

Prüfung:

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
quelle
2

Dyalog APL , 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
Adam
quelle
2

Clojure, 71 64 63 Bytes

Es sieht so aus, als wären die Verhältnisse in Ordnung. Welche Zahlenformate sind für die Ausgabe akzeptabel?

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

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

ungolfed (und zur leichteren Erklärung leicht umgeschrieben)

(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

alte Antwort, die verwendet wurde (float):

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

Ausgabe ist wie folgt:

  • n = 1 => 1,0
  • n = 7 => 2,142857
Kennzeichen
quelle
Die Frage, ob Brüche oder Verhältnisse akzeptabel sind, wurde zuvor nicht gestellt. Für diese Herausforderung akzeptiere ich jeden Konsens darüber, wie der Standard sein sollte .
Trichoplax
1

Minkolang 0,15 , 23 Bytes

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

Probieren Sie es hier aus!

Erläuterung

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.

Ziemlich direkte Implementierung.

El'endia Starman
quelle
1

JavaScript ES5, 55 Byte

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

Erläuterung

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
quelle
1

Hoon , 71 Bytes

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

... Ich bin mir ziemlich sicher, dass dies das erste Mal ist, dass ich Hoons Gleitkommakerne verwende. Tatsächlich handelt es sich um eine in Hoon geschriebene Implementierung, die an SoftFloat gesendet wird, da die einzigen Datentypen in Hoon Atome und Zellen sind.

Erstellen Sie eine Funktion, die ein Atom annimmt r. Erstellen Sie eine Liste aus [0 .. (r - 1)], mappen Sie die Liste mit dem binären Logarithmus der Zahl ab und falten Sie diese Liste mit ++add. Wandle sowohl die Ausgabe der Falte als auch rin @rq(Gleitkommazahlen mit vierfacher Genauigkeit) mit um++sun:rq und dividiere dann eine durch die andere.

Das Seltsamste an diesem Ausschnitt ist :.^rqdas Ende. a:bin Hoon bedeutet "bewerte a im Kontext von b". ++rqist der Kern, der wie eine Bibliothek die gesamte Implementierung mit vierfacher Genauigkeit enthält. Laufen (sun 5):rqist also das Gleiche wie Laufen(sun:rq 5) .

Glücklicherweise sind Kerne in Hoon wie Nistpuppen; Wenn Sie den Arm auswerten ++rq, um den Kern zu erhalten, fügt er auch die gesamte Stdlib hinzu, sodass Sie die Rolle und Drehung sowie das ganze lustige Zeug behalten können, anstatt nur mit den in definierten Armen zu stecken ++rq. Leider definiert rq neu ++add, um stattdessen Gleitkommazahl hinzuzufügen und nicht rin seinem Kontext zu haben..(der gesamte aktuelle Kontext) tut dies jedoch.

Bei der Auswertung eines Ausdrucks in einem Kontext sucht der Compiler zuerst nach der Gliedertiefe. In unserem Fall a:[. rq]würde man im gesamten aktuellen Kontext nachschauen, abevor man zum Nachschauen übergeht rq. Ich addwerde also die Funktion nachschlagen, die auf Atomen anstelle von Gleitkommazahlen funktioniert ... aber ich werde es auch tun div. Hoon hat auch eine Funktion, bei der bei Verwendung ^nameder erste gefundene Verweis ignoriert wird und nach dem zweiten gesucht wird.

Von da an wird einfach der syntatische Zucker a^bGleichheit verwendet, [a b]um unser Snippet sowohl mit unserem aktuellen Kontext als auch mit der Float-Bibliothek mit vierfacher Genauigkeit zu bewerten, wobei der atomare Div zugunsten von ignoriert wird ++div:rq.

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

Eigentlich 7 Bytes:

;r♂├Σl/

Probieren Sie es online!

Erläuterung:

;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

Ohne einen Fehler, den ich gerade entdeckt habe, würde diese Lösung für 6 Bytes funktionieren:

r♂├♂læ

æ ist der eingebaute mittlere Befehl.

Mego
quelle
Sind das nicht 10 Bytes? Ich habe bei bytesizematters.com nachgesehen.
m654
1
@ m654 Verwendet derzeit kein UTF-8, sondern CP437 (oder ähnliches).
Alex A.
@AlexA. Oh, das wusste ich nicht.
m654
1
@ m654 Bytesizematters verwendet eine vollständig erfundene Codierung, die in der Praxis nicht existiert (und nicht existieren kann ). Verwenden Sie für UTF-8 mothereff.in/byte-counter .
Dennis
@Dennis Danke für die Info, das werde ich mir merken.
m654
1

Vitsy, 26 Bytes

Dies ist ein erster Versuch, ich werde dies weiter ausbauen und später eine Erklärung hinzufügen.

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

Probieren Sie es online!

Addison Crump
quelle
1

PowerShell v2 +, 64 Byte

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

Sehr unkomplizierte Umsetzung der Spezifikation. Schleifen von 0bis $n-1mit |%{...}. Bei jeder Iteration geben wir [convert]unsere Eingabenummer $_in eine Stringbasis ein 2und nehmen ihre length. Wir akkumulieren das in $o. Nach den Schleifen teilen wir uns einfach$o/$n und belassen dies in der Pipeline, und die Ausgabe ist implizit.

Solange dies so ist, ist es tatsächlich kürzer als die Formel, die Sp & amp; andere verwenden, da [math]::Ceiling()und [math]::Log()lächerlich wortreich sind. Die Grundkonvertierung in PowerShell ist ein Glücksfall.

AdmBorkBork
quelle
1

Perl 5.10, 54 Bytes

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

Ziemlich unkompliziert. sprintf"%b"ist eine einfache Möglichkeit, in Perl eine Zahl in Binärform auszugeben, ohne zusätzliche Bibliotheken zu verwenden.

Probieren Sie es online!

Paul Picard
quelle
1

CJam, 13 12 11 Bytes

Ein Byte wurde dank @ Sp3000 gespeichert, ein weiteres dank @ jimmy23013

rd_,2fbs,\/

Probieren Sie es online!

Erläuterung

Einfach. Wendet die Definition an.

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
quelle
1

Jolf, 10 Bytes

/uΜr0xdlBH

Probieren Sie es hier aus!

Erläuterung

/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
quelle
1

Schnell, 72 Bytes

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
John McDowall
quelle
2
Sie müssen die Funktion nicht aufrufen, es ist in Ordnung, sie als definierte Funktion zu belassen. Schöner erster Beitrag.
26.
1

J, 15 Bytes

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

Dies ist ein monadisches Verb, das wie folgt verwendet wird:

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

Probieren Sie es hier aus!

Erläuterung

Ich habe die Herausforderungsspezifikation ziemlich wörtlich umgesetzt. Es gibt andere Ansätze, aber alle erwiesen sich als länger.

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