Bits médios: um desafio médio

30

Dado um número inteiro N> = 1, imprima o número médio de bits em um número inteiro de 0 a N - 1

Especificação

  • A saída pode ser calculada como a soma do número de bits na representação binária de cada número inteiro de 0 a N-1, dividido por N.
  • A representação binária de um número inteiro não possui zeros à esquerda nesse contexto, com exceção de zero, que é representado como 0 em binário.
  • A saída deve ter precisão de pelo menos 7 números significativos.

Exemplo

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

Número médio de bits = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Casos de teste

Entrada => saída

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

Snippet de cabeçalho

( daqui )

Mostrar snippet de código

Observe que a soma (antes de dividir para encontrar a média) é uma sequência no OEIS .

code-golf math binary bitwise statistics Trichoplax
fonte
6
Nome bonito , muito pequeno .
Rɪᴋᴇʀ
3
Para quem não sabe, eu sou mais propensos a upvote soluções com uma explicação
Trichoplax
4
Não há trocadilhos suficientes, você precisa de um pouco mais para que isso seja perfeito.
Clismique 25/05
1
Estou assumindo que com "cada número" você quer dizer "cada número inteiro "?
Cyoce 28/05
@ Cyoce sim, obrigado por apontar isso - eu editei para esclarecer.
Trichoplax # 28/16

Respostas:

13

Pitão, 6 bytes

.Oml.B

Experimente online aqui .

.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
fonte
Juntar o primeiro lugar, mas você não estava aparecendo na tabela de classificação - fiz uma pequena edição no cabeçalho para corrigi-lo.
Trichoplax
9

Gelatina, 6 bytes

R’BFL÷

Experimente 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]
Freira Furada
fonte
7

Oitava, 29 bytes

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

Explicação

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

Amostra executada em ideone .

taça
fonte
6

Python 3, 43 bytes

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

Faz uso da fórmula no página OEIS . Surpreendentemente, uma função nomeada é de alguma forma mais barata aqui por causa da atribuição a x.

Abordagem alternativa para 46 bytes:

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

Infelizmente, o -~necessário é que (0).bit_length()é 0, mas mesmo assim seria um byte muito longo.

Sp3000
fonte
6

Julia, 27 bytes

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

Experimente online!

Como funciona

Como a *concatenação de strings em Julia, prodpode ser usada para concatenar uma matriz de strings. Opcionalmente, ele assume uma função como primeiro argumento que mapeia sobre o segundo antes de obter o "produto" real, assim prod(bin,0:n-1)como a cadeia de caracteres da representação binária de todos os números inteiros no intervalo desejado. Tomando o comprimento com endofe dividindo por n, obtém-se a média.

Dennis
fonte
5

Julia, 28 bytes

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

Como binnão mapeia automaticamente as matrizes, estamos usando ceil(log2(n))o número de bits n-1. Isso funciona bem porque a a:bnotação de Julia é inclusiva nas duas extremidades, assim 2:ncomo um intervalo de 2 a n, mas estamos realmente calculando o número de bits para números no intervalo 1:n-1. Infelizmente, porém, precisamos acrescentar um extra 2para responder por 0.

Experimente online!

Sp3000
fonte
5

MATL, 9 bytes

q:ZlksG/Q

Experimente Online!

Versão modificada com todos os casos de teste

Explicação

    % 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
fonte
Snap !! (filler)
David
@ David Na verdade, o seu estava correto. Duplicar a entrada no início não funciona para outros valores ... você precisa G/Qno final.
beaker
5

MATL, 9 bytes

:qBYszQG/

Experimente online!

Explicação

: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
taça
fonte
5

Geléia, 8 bytes

Algoritmo não mais curto, mas interessante, e meu primeiro envio Jelly:

Rl2Ċ»1S÷

R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
Adão
fonte
4

Gelatina, 10 bytes

BL©2*2_÷+®

Por sugestão do Sp3000.

Experimente aqui.

Gelatina, 11 bytes

æḟ2’Ḥ÷_BL$N

Não é muito curto, mas preciso de algumas dicas.

Experimente aqui.

Usando a mesma fórmula da resposta do Sp3000 . (Não é muito difícil obtê-lo, diferenciando a progressão geométrica.)

jimmy23013
fonte
Veja a minha resposta Jelly para sua referência.
Freira vazando
@LeakyNun Está usando uma abordagem diferente, que eu acho que nunca seria mais curta que a sua. Mas o _BL$Npareceu bastante longo ...
jimmy23013 25/05
Então, basicamente, seu código é "chegar à potência mais próxima de 2, menos 1, duplo, dividir por entrada, menos o comprimento binário da entrada, negativo"?
Freira vazando
@LeakyNun Yes ..
jimmy23013 de
3
Apenas marginalmente melhor:BL©2*2_÷+®
Sp3000 25/05
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
fonte
Eu acho que você pode se livrar da interface e simplesmente criar uma função ou lambda. Além disso, você pode devolver o valor em vez de imprimi-lo na saída padrão
Frozn
Ok, eu vou implementar com essas regras.
Shaun Wild
Eu acho que deveria ser permitido. Como o OP não especificou nada, acho que as regras de E / S padrão se aplicam.
Frozn 25/05
Sim, uma função está correta - você não precisa de um programa completo. Note-se que as picaretas leaderboard o placar na primeira linha, assim que sua pontuação atualmente mostra como 135 em vez de 95.
Trichoplax
@trichoplax Ainda último lugar. Eu culpo Java pessoalmente ...
Shaun selvagem
3

Python 3, 46 bytes

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

Chame como

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

Eu tive que reverter a revisão do mapa porque ela falhou na entrada de 5

Keatinge
fonte
3

05AB1E, 9 7 bytes

Código:

L<bJg¹/

Explicação:

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

Experimente online

Edit: salvou 2 bytes graças a @Adnan

Emigna
fonte
@ Adnan: Obrigado! Esqueci J.
Emigna 25/05
3

C #, 87 bytes

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

Eu escrevi uma resposta em C # porque não vi nenhuma. Este é o meu primeiro post em um deles, então, deixe-me saber se estou fazendo algo errado.

atacar
fonte
Bem-vindo à programação de quebra-cabeças e código de golfe. Esta é uma ótima primeira resposta, +1. Você pode mudar doublepara floatsalvar um byte ou precisa da precisão?
Wizzwizz4
2
@ wizzwizz4 Obrigado! Eu tive o mesmo pensamento, mas Average () retorna um dobro. Se eu mudar meu tipo de retorno para flutuar, preciso explicitamente converter o dobro e obter 7 bytes nisso.
#
2

JavaScript (ES7), 38 32 bytes

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

Usando a fórmula do @ sp3000 (a versão anterior era uma solução recursiva). Versão ES6 para 34 bytes:

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

Explicação da fórmula: Considere o caso de N = 55. Se escrevermos os números binários (verticalmente para economizar espaço), obtemos:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

O tamanho desse retângulo é nl; portanto, a média é apenas l, mas precisamos excluir os espaços em branco. Cada linha de espaços em branco é duas vezes maior que a anterior, portanto o total é 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 l - 2.

Neil
fonte
2

J, 21 17 15 bytes

De 17 bytes a 15 bytes, graças a @Dennis.

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

Alguém pode me ajudar a jogar isso? ...

Versão ungolfed

range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
Freira Furada
fonte
Eu tentei uma abordagem alternativa, por stringifying a lista de números binários, e saiu com 25 bytes: %~>:@#@([:":10#.[:#:i.)-]. Sua solução está ótima.
Conor O'Brien
2

Perl 6 ,  34  32 bytes

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

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

Explicação:

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

Teste:

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
fonte
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
Adão
fonte
2

Clojure, 71 64 63 bytes

Parece que as proporções estão corretas de acordo com Quais formatos de número são aceitáveis ​​na saída?

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

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

ungolfed (e ligeiramente reescrito para facilitar a explicação)

(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

resposta antiga usada (float):

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

saída é como:

  • n = 1 => 1,0
  • n = 7 => 2,142857
marca
fonte
A questão de saber se frações ou proporções são aceitáveis ​​não havia sido levantada antes. Para esse desafio, aceitarei qualquer consenso alcançado sobre qual deve ser o padrão .
Trichoplax #
1

Tamanho 0.15 , 23 bytes

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

Experimente aqui!

Explicação

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.

Implementação bastante direta.

El'endia Starman
fonte
1

JavaScript ES5, 55 bytes

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

Explicação

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

Hoon , 71 bytes

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

... Tenho certeza de que esta é a primeira vez que usei os núcleos de ponto flutuante de Hoon. Na verdade, é uma implementação escrita em Hoon que é projetada para o SoftFloat, já que os únicos tipos de dados no Hoon são átomos e células.

Crie uma função que use um átomo r,. Crie uma lista de [0 .. (r - 1)], mapeie a lista usando o logaritmo binário do número e, em seguida, dobre essa lista com ++add. Converta a saída da dobra e rpara @rq(números de ponto flutuante de precisão quádrupla) com ++sun:rqe, em seguida, divida uma pela outra.

A coisa mais estranha nesse trecho é :.^rqo final. a:bem Hoon significa "avaliar a no contexto de b". ++rqé o núcleo que contém toda a implementação de precisão quádrupla, como uma biblioteca. Então, correr (sun 5):rqé a mesma coisa que fazer(sun:rq 5) .

Felizmente, os núcleos em Hoon são como bonecas; quando você avalia o braço ++rqpara obter o núcleo, ele adiciona todo o stdlib a ele, para manter o giro, o giro e o golfo e todas essas coisas divertidas, em vez de ficar preso apenas com os braços definidos ++rq. Infelizmente, rq redefine ++addcomo adição de ponto flutuante, além de não ter rem seu contexto. .(todo o contexto atual), no entanto.

Ao avaliar uma expressão em um contexto, o compilador procura primeiro a profundidade do membro. No nosso caso, a:[. rq]ele procuraria no contexto atual inteiro aantes de passar a procurar rq. Então add, procurará a função que funciona em átomos, em vez de números de ponto flutuante ... mas o fará div. Hoon também possui um recurso em que o uso ^nameignorará a primeira referência encontrada e procurará a segunda.

A partir daí, é simplesmente usar o açúcar sintático de a^bser igual para [a b]avaliar nosso snippet com o contexto atual e a biblioteca de flutuadores de precisão quádrupla, ignorando a div atômica em favor de ++div:rq.

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

Na verdade, 7 bytes:

;r♂├Σl/

Experimente online!

Explicação:

;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

Se não fosse por um bug que eu acabei de descobrir, esta solução funcionaria por 6 bytes:

r♂├♂læ

æ é o comando médio interno.

Mego
fonte
Isso não é 10 bytes? Eu verifiquei em bytesizematters.com.
M654
1
@ m654 Na verdade, não usa UTF-8, usa CP437 (ou algo parecido).
Alex A.
@AlexA. Oh, não sabia disso.
M654
1
@ m654 Bytesizematters utiliza uma codificação completamente inventada que não existe (e não pode ) existir na prática. Para UTF-8, use mothereff.in/byte-counter .
Dennis
@ Dennis Obrigado pela informação, vou manter isso em mente.
M654 26/05
1

Vitsy, 26 bytes

Esta é uma primeira tentativa, vou jogar mais isso e adicionar uma explicação mais tarde.

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

Experimente online!

Addison Crump
fonte
1

PowerShell v2 +, 64 bytes

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

Implementação muito direta das especificações. Loops de 0para $n-1com |%{...}. Cada iteração, [convert]nosso número de entrada $_para uma base de string2 e seu length. Nós acumulamos isso em $o. Após os loops, simplesmente nos dividimos $o/$n, deixando isso no pipeline, e a saída é implícita.

Desde que seja, é realmente mais curto que a fórmula que Sp e outros estão usando, desde [math]::Ceiling()e [math]::Log()são ridiculamente prolixo. A conversão de base no PowerShell está nojenta.

AdmBorkBork
fonte
1

Perl 5.10, 54 bytes

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

Muito simples. sprintf"%b"é uma maneira elegante de gerar um número em binário no Perl sem usar bibliotecas adicionais.

Experimente online!

Paul Picard
fonte
1

CJam, 13 12 11 bytes

Um byte salvo graças ao @ Sp3000 e outro graças ao @ jimmy23013

rd_,2fbs,\/

Experimente online!

Explicação

Direto. Aplica a definição.

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

Jolf, 10 bytes

/uΜr0xdlBH

Experimente aqui!

Explicação

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

Rápido, 72 bytes

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
John McDowall
fonte
2
Você não precisa chamar a função, deixando-a como uma função definida. Bom primeiro post.
Rɪᴋᴇʀ
1

J, 15 bytes

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

Este é um verbo monádico, usado da seguinte maneira:

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

Experimente aqui!

Explicação

Eu implementei a especificação do desafio literalmente. Existem outras abordagens, mas todas acabaram sendo mais longas.

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